Основное правило комбинаторики
Число размещений с возвращением
Число сочетаний без возвращений
Комбинаторика является одним из разделов математики, изучающая задачи расположения, сочетания, выбора объектов в различных ситуациях (условиях).
Иногда обсуждение "перестановок и сочетаний" начинается с вопроса, подобного следующему:
Сколькими способами может одеться человек, комбинируя три рубашки, два галстука и две пары ботинок?
Пусть первая координата указывает вариант выбора рубашки, вторая - галстука, а третья - ботинок.
Запишем:
(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.
Итак, сформулируем общее утверждение:
Пусть необходимо несколько раз произвести выбор. Существует m1 вариантов при первом выборе, m2 - при втором, m3 - при третьем и т.д.
Если каждый раз выбор производится без всяких ограничений, тогда общее число возможностей для всей последовательности выборов равно:
m1 ∙ m2 ∙ m3 ∙ ...
Теперь познакомимся с основными стандартными методами вычислений, используемыми при решении комбинаторных задач.
Рассуждения будем приводить на основе следующего примера:
Пусть урна содержит m различных шаров с номерами от 1 до m. Из неё извлекаются n шаров при соблюдении некоторых условий на способ извлечения. Для каждой модели вычисляются количества всех возможных исходов.
Шары извлекаются наудачу один за другим, причем каждый вынутый шар возвращается назад в урну прежде, чем будет извлечен следующий. При этом записываются номера шаров в порядке их появления.
Таким образом, мы имеем дело с упорядоченными наборами (a1,...,an), в которых каждое aj может принимать любое значение от 1 до m.
Основное правило сразу приводит к ответу mn для полного числа исходов.
Шары извлекаются наудачу один за другим, однако в данной модели они не возвращаются обратно в урну. Мы снова имеем дело с упорядоченными наборами (a1,...,an), но уже с ограничением, что в них все aj различны. Конечно, должно выполняться неравенство n меньше или равно m. Основное правило напрямую не применимо. Тем не менее, принимая во внимание, что на каждом шаге число шаров в урне становится на один меньше, можем записать:
m ∙ (m-1) ∙ (m-2) ∙ ... ∙ (m - (n-1)) = (m)n
Данная модель имеет важный частный случай - модель перестановок.
Рассмотрим модель 1.2 при m = n.
Тогда все m шаров извлекаются один за другим без возвращений. Результатом выбора является набор из m занумерованных шаров, расставленных в некотором порядке. Полное количество возможностей совпадает с числом всех расположений элементов множества {1,2,..,m}. Это число называется факториалом от m и обозначается
m! = (m)m = m ∙ (m-1) ∙ ... ∙ 2 ∙ 1
Модель подразумевает, что порядок номеров вытянутых шаров не фиксируется. В отличие от модели размещений, наборы, отличающиеся только порядком следования элементов, считаются одинаковыми.
Итак, вынутые шары не возвращаются назад в урну, а также не фиксируется порядок их номеров в процессе извлечения.
Другими словами, можно представить себе, что все n шаров вынимаются сразу за одно извлечение.
Следовательно, мы имеем дело с выбором произвольного подмножества размера n из множества размера m.
Из предыдущих рассуждений понятно, что упорядоченная выборка размера n порождает n! неупорядоченных, по каждой из которых можно однозначно восстановить исходную.
Из обсуждения модели 1.2 известно, что количество последовательных наборов размера n равно (m)n.
Обозначим за x искомое число исходов (подмножеств размера n). Проведенные выше рассуждения показывают, что
n! ∙ x = (m)n
Отсюда получаем искомый ответ:
Если умножить числитель и знаменатель на (m-n)!, получим:
(*)
Выражение (*) называется биномиальным коэффициентом и играет важную роль в теории вероятностей.
Заметьте, что верно тождество
Допустим,что у нас есть m1 шаров цвета номер 1, m2 шаров цвета номер 2, ... mr шаров цвета номер r. Цвета различаются, а шары одного цвета - нет.
Конечно, m1 + m2 +... + mr = m. Сколько существует отличающихся перестановок таких шаров?
Используя рассуждения из 1.2.a. для каждой первоначальной перестановки без различения шаров одного цвета в силу основного правила существует
m1! ∙ m2! ∙ ... ∙ mr!
новых способов размещения с учетом нумерации.
Рассуждения аналогичные проведенным для модели 2.1 показывают, что искомое число ненумерованных перестановок равно частному:
Число называется мультиномиальным (или полиномиальным) коэффициентов. Когда r=2, коэффициент сводится к биномиальному.
Из урны извлекаются один за другим n шаров, каждый вынутый шар возвращается назад прежде, чем будет извлечен следующий.
При этом (возможно, повторяющиеся) номера всех вынутых шаров регистрируются в виде неупорядоченного набора (группы), т.е. без обращения внимания на порядок их появления.
К.Л. Чжун, Ф. АитСахлиа. Элементарный курс теории вероятностей. Стохастические процессы и финансовая математика. Перевод с английского М.Б. Лагутина, М.: БИНОМ. Лаборатория знаний, 2007
Скачать
Актуальные курсы