Комбинаторика

Основное правило комбинаторики

Размещение

Число размещений с возвращением

Перестановка из m различимых шаров

Число размещений без возвращений

Сочетание

Число сочетаний без возвращений

Перестановка из m шаров, неразличимых внутри групп

Число сочетаний с возвращением

Комбинаторика является одним из разделов математики, изучающая задачи расположения, сочетания, выбора объектов в различных ситуациях (условиях).

Иногда обсуждение "перестановок и сочетаний" начинается с вопроса, подобного следующему:

Сколькими способами может одеться человек, комбинируя три рубашки, два галстука и две пары ботинок?

Пусть первая координата указывает вариант выбора рубашки, вторая - галстука, а третья - ботинок.

Запишем:

(1,1,1) (1,1,2) (1,2,1) (1,2,2) для комбинации с первой рубашкой

(2,1,1) (2,1,2) (2,2,1) (2,2,2) для комбинации со второй рубашкой

(3,1,1) (3,1,2) (3,2,1) (3,2,2) для комбинации с третьей рубашкой

Эта совокупность является множеством всех упорядоченных пар.

Теперь понятно, что правильным ответом служит число 3 ∙ 2 ∙ 2 = 12.

Итак, сформулируем общее утверждение:

Основное правило комбинаторики

Пусть необходимо несколько раз произвести выбор. Существует m₁ вариантов при первом выборе, m₂ - при втором, m₃ - при третьем и т.д.

Если каждый раз выбор производится без всяких ограничений, тогда общее число возможностей для всей последовательности выборов равно:

m₁ ∙ m₂ ∙ m₃ ∙ ...

Теперь познакомимся с основными стандартными методами вычислений, используемыми при решении комбинаторных задач.

Рассуждения будем приводить на основе следующего примера:

Пусть урна содержит m различных шаров с номерами от 1 до m. Из неё извлекаются n шаров при соблюдении некоторых условий на способ извлечения. Для каждой модели вычисляются количества всех возможных исходов.

1. Размещение (или упорядоченный выбор)

1.1 Число размещений с возвращением

Шары извлекаются наудачу один за другим, причем каждый вынутый шар возвращается назад в урну прежде, чем будет извлечен следующий. При этом записываются номера шаров в порядке их появления.

Таким образом, мы имеем дело с упорядоченными наборами (a₁,...,a_n), в которых каждое a_j может принимать любое значение от 1 до m.

Основное правило сразу приводит к ответу mⁿ для полного числа исходов.

1.2 Число размещений без возвращения

Шары извлекаются наудачу один за другим, однако в данной модели они не возвращаются обратно в урну. Мы снова имеем дело с упорядоченными наборами (a₁,...,a_n), но уже с ограничением, что в них все a_j различны. Конечно, должно выполняться неравенство n меньше или равно m. Основное правило напрямую не применимо. Тем не менее, принимая во внимание, что на каждом шаге число шаров в урне становится на один меньше, можем записать:

m ∙ (m-1) ∙ (m-2) ∙ ... ∙ (m - (n-1)) = (m)_n

Данная модель имеет важный частный случай - модель перестановок.

1.2 a. Перестановка из m различимых шаров

Рассмотрим модель 1.2 при m = n.

Тогда все m шаров извлекаются один за другим без возвращений. Результатом выбора является набор из m занумерованных шаров, расставленных в некотором порядке. Полное количество возможностей совпадает с числом всех расположений элементов множества {1,2,..,m}. Это число называется факториалом от m и обозначается

m! = (m)_m = m ∙ (m-1) ∙ ... ∙ 2 ∙ 1

2. Сочетание (или неупорядоченный выбор)

Модель подразумевает, что порядок номеров вытянутых шаров не фиксируется. В отличие от модели размещений, наборы, отличающиеся только порядком следования элементов, считаются одинаковыми.

2.1 Число сочетаний без возвращения

Итак, вынутые шары не возвращаются назад в урну, а также не фиксируется порядок их номеров в процессе извлечения.

Другими словами, можно представить себе, что все n шаров вынимаются сразу за одно извлечение.

Следовательно, мы имеем дело с выбором произвольного подмножества размера n из множества размера m.

Из предыдущих рассуждений понятно, что упорядоченная выборка размера n порождает n! неупорядоченных, по каждой из которых можно однозначно восстановить исходную.

Из обсуждения модели 1.2 известно, что количество последовательных наборов размера n равно (m)_n.

Обозначим за x искомое число исходов (подмножеств размера n). Проведенные выше рассуждения показывают, что

n! ∙ x = (m)_n

Отсюда получаем искомый ответ:

Если умножить числитель и знаменатель на (m-n)!, получим:

       (*)

Выражение (*) называется биномиальным коэффициентом и играет важную роль в теории вероятностей.

Заметьте, что верно тождество

2.1.a. Перестановка из m шаров, неразличимых внутри групп

Допустим,что у нас есть m₁ шаров цвета номер 1, m₂ шаров цвета номер 2, ... m_r шаров цвета номер r. Цвета различаются, а шары одного цвета - нет.

Конечно, m₁ + m₂ +... + m_r = m. Сколько существует отличающихся перестановок таких шаров?

Используя рассуждения из 1.2.a. для каждой первоначальной перестановки без различения шаров одного цвета в силу основного правила существует

m₁! ∙ m₂! ∙ ... ∙ m_r!

новых способов размещения с учетом нумерации.

Рассуждения аналогичные проведенным для модели 2.1 показывают, что искомое число ненумерованных перестановок равно частному:

Число называется мультиномиальным (или полиномиальным) коэффициентов. Когда r=2, коэффициент сводится к биномиальному.

2.2 Число сочетаний с возвращением

Из урны извлекаются один за другим n шаров, каждый вынутый шар возвращается назад прежде, чем будет извлечен следующий.

При этом (возможно, повторяющиеся) номера всех вынутых шаров регистрируются в виде неупорядоченного набора (группы), т.е. без обращения внимания на порядок их появления.

Литература

К.Л. Чжун, Ф. АитСахлиа. Элементарный курс теории вероятностей. Стохастические процессы и финансовая математика. Перевод с английского М.Б. Лагутина, М.: БИНОМ. Лаборатория знаний, 2007

В начало

Содержание портала