Основные формулы комбинаторики

Этот материал не относится непосредственно к теории вероятности и математической статистике, однако необходим в дальнейшем при расчетах вероятностей. Комбинаторика происходит от латинского слова «combinatio» – соединение.

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

Перестановками называются комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок где Иногда удобно рассматривать 0!, полагая по определению, 0!=1.

Пример 2.1. Менеджер ежедневно просматривает 6 изданий экономического содержания. Если порядок просмотра случаен, то сколько существует способов его осуществления?

Способы просмотра изданий различаются только порядком, так как число, а значит, и состав изданий при каждом способе неизменны. Следовательно, при решении этой задачи необходимо вычислить число перестановок:

Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений

Пример 2.2. Правление банка выбирает из 10 кандидатов 3 человека на различные должности (все 10 кандидатов имеют равные шансы). Сколько всевозможных групп по 3 человека можно составить из 10 кандидатов?

Необходимо рассчитать число комбинаций из 10 элементов по 3. Так как группы по 3 человека могут отличаться и составом претендентов, и заполняемыми ими вакансиями (они все разные), т. е. порядком, то для ответа необходимо вычислить число размещений из 10 элементов по 3: Можно составить 720 групп.

Сочетаниями называются комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементов. Число сочетаний

Свойства сочетаний

Пример 2.3. Правление банка выбирает из 10 кандидатов 3 человека на одинаковые должности (все 10 кандидатов имеют равные шансы). Сколько всевозможных групп по 3 человека можно составить из 10 кандидатов?

Состав различных групп должен отличаться по крайней мере хотя бы одним кандидатом и порядок выбора кандидата не имеет значения (все вакансии одинаковы), следовательно, этот вид комбинаций представляет собой сочетания

Можно составить 120 групп из 10 человек по 3.

Следует различать сочетания от размещений. Например, если в группе 20 студентов и 7 человек из них, выйдя из аудитории на перерыв, стоят вместе и беседуют, то порядок, в котором они стоят, не существенен. Число всех возможных групп из 20 человек по 7 в данном случае – сочетания. Если же студенты отправились на перерыве в буфет или в кассу за стипендией, то тогда существенно, в каком порядке они стали, т. е. кто из них первый, кто второй и т. д. В этой ситуации при подсчете возможных групп из 20 человек по 7 необходимо составлять размещения.

Отметим, что числа перестановок, размещений и сочетаний связаны равенством

При решении задач комбинаторики используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m+n способами.

Правило произведения. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана способами.