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

Пусть имеется n множеств ..., содержащих по , ,..., элементов каждое. Выбирается по одному элементу из каждого множества и составляется еще одно множество. Число способов, которыми можно выбрать по одному элементу из каждого множества, равно произведению ... .

В этом и состоит основной принцип комбинаторики.

В задачах теории вероятностей часто встречаются различные соединения (комбинации) из множества n элементов по k элементов (k £ n).

Ниже будем рассматривать соединения без повторений, т.е. каждый элемент данного множества может входить в соединения не более одного раза.

Рассмотрим три вида соединений: 1) размещения, 2) перестановки,
3) сочетания.

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

чается и равно

= n (n -1)... (n – (k -1)).

Доказательство. Для того, чтобы расположить k элементов в определенном порядке, выберем один из них и будем считать его «первым». Это можно сделать n способами. Оставшееся множество содержит n -1 элементов. Из него выберем один и назовем его «вторым». Для выбора второго элемента имеются n -1 способов. Осталось множество из n -2 элементов. Продолжив процесс отбора, последний k -ый элемент можно выбрать n – (k -1) способами. Согласно основному правилу комбинаторики число всех способов, которыми можно составить размещения, т.е. число размещений равно

= n (n -1)... (n – (k -1))= ,

где n! – произведение n первых целых чисел (читается эн-факториал).

Пример. Определить, сколько трехзначных чисел можно составить из множества цифр 1,2,3,4,5 без повторения.

Решение. Имеем n =5, k =3, = 5×4×3 = 60.

Определение. Перестановками из данных n элементов называются множества из n элементов, различающиеся только порядком.

Перестановки – это частный случай размещений, k = n. Поэтому

= n (n -1)... (n – (k -1))... 1 = = n!

По определению принимается = 0! = 1.

Пример 1. К кассе за получением (или уплатой) денег подошли одновременно 5 человек. Сколькими способами они могут выстроиться в очередь?

Решение. Очередь состоит из пяти различных лиц, поэтому в каждом способе составления очереди учитывается порядок их расположения. Таким образом, имеют место перестановки из пяти человек, их число равно

=1·2·3·4·5=120.

Определение. Сочетаниями, содержащими k элементов, выбранных из n элементов заданного множества, называются всевозможные множества, различающиеся хотя бы одним элементом. Число сочетаний из n элементов по k обозначают или .

Число сочетаний из n элементов по k вычисляется по формуле

= .

Доказательство. Рассмотрим размещения из n элементов по k. Их число . Если не считаться с порядком элементов в перестановке из k элементов, то существует k! перестановок, которые нельзя отличить от первоначальной перестановки. Поэтому число всех сочетаний в k!раз меньше числа всех размещений, т.е. = / = .

Пример. Сколькими способами можно выбрать двух студентов в студенческий совет из 20 студентов?

Решение. Имеем n= 20, k =2. Способы отбора считаются различными, если каждая отобранная пара различается хотя бы одним студентом, а это

190.

Вопросы для самопроверки.

1. Что является предметом изучения теории вероятностей?

2. Какое явление называется случайным?

3. Какие модели используются для описания социальных и экономических явлений?

4. Приведите формулу вычисления числа размещений из n элементов по k.

5. Приведите формулу для вычисления числа перестановок из n элементов.

6. Приведите формулу для вычисления числа сочетаний из n элементов по k.

Задачи.

1.1. Басня Крылова: «проказница мартышка, осел, козел да косолапый мишка надумали сыграть квартет...». Сколькими способами они садились?

1.2. Встретились пять человек и обменялись рукопожатиями, а после беседы визитными карточками. Сколько было рукопожатий и визитных карточек?

1.3. К кассе одновременно подошли за получением (или уплатой) денег шесть человек. Сколькими способами они могут выстроиться в очередь?

1.4. Из 20 студентов отбираются 8 человек для стажировки в США. Определить число групп, если шансы быть включенными в группу у всех студентов одинаковы. Сколькими способами можно выбрать из этих восьми человек руководителя группы и его заместителя?

1.5. В соревновании участвуют десять команд. Сколько существует различных возможностей среди этих команд занять призовое (I, II, III) место?