Элементы комбинаторики. 
Теория вероятностей

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

Пусть Д (г = 1, 2, …, п) — элементы конечного множества. Сформулируем два важных правила, часто применяемых при решении комбинаторных задач.

Правило суммы. Если элемент А_х может быть выбран п_х способами, элемент А₂ — другими п₂ способами, Л₃ — отличными от первых двух п₃ способами и т. д., А_к — п_к способами, отличными от первых (к — 1), то выбор одного из элементов: или А_х, или Л₂, …, или А_к может быть осуществлен п_х + п₂+ …+ п_к способами.

|> Пример 1.3. В ящике 300 деталей. Известно, что 150 из них — 1-го сорта, 120 — 2-го, а остальные — 3-го сорта. Сколько существует способов извлечения из ящика одной детали 1-го или 2-го сорта?

Решение. Деталь 1-го сорта может быть извлечена п_х = 150 способами, 2-го сорта — п₂- 120 способами. По правилу суммы существует п_х + п₂ — 150 + 120 = 270 способов извлечения одной детали 1-го или 2-го сорта. ?

Правило произведения. Если элемент А_{ может быть выбран п_Л способами, после каждого такого выбора элемент А₂ может быть выбран п₂ способами и т. д., после каждого (k — 1) выбора элемент A_k может быть выбран n_k способами, то выбор всех элементов A_v А₂,…, A_k в указанном порядке может быть осуществлен п_Лп₂.щ способами.

[> Пример 1.4. В группе 30 человек. Необходимо выбрать старосту, его заместителя и профорга. Сколько существует способов это сделать?

Решение. Старостой может быть выбран любой из 30 учащихся, его заместителем — любой из оставшихся 29, а профоргом — любой из оставшихся 28 учащихся, т. е. щ = 30, п₂ = 29, п₃ = 28. По правилу произведения общее число способов выбора старосты, его заместителя и профорга равно ^пп₂п₃ = 30 • 29 • 28 = 24 360 способов. ?

Пусть дано множество из п различных элементов. Из этого множества могут быть образованы подмножества из т элементов (0 < т < п). Например, из 5 элементов а_у b, с*, d, е могут быть отобраны комбинации по 2 элемента — ab_y cd_y eby ba_y се и т. д., по 3 элемента — abc, cbd, cba_f ead и т. д.

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

или

где п равно произведению п первых чисел натурального ряда, т. е. п = 1 • 2…п.

> Пример 1.5. Расписание одного дня состоит из 5 уроков. Определить число вариантов расписания при выборе из 11 дисциплин.

Решение. Каждый вариант расписания представляет набор 5 дисциплин из И, отличающийся от других вариантов как составом дисциплин, так и порядком их следования (или и тем и другим), т. е. является размещением из И элементов по 5. Число вариантов расписаний, т. е. число размещений из 11 по 5, находим по формуле (1.6).

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

или

Так как по определению 0! = 1, то =1, С" = 1.

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

> Пример 1.6. В шахматном турнире участвуют 16 человек. Сколько партий должно быть сыграно в турнире, если между любыми двумя участниками должна быть сыграна одна партия?

Решение. Каждая партия играется двумя участниками из 16 и отличается от других только составом пар участников, т. е. представляет собой сочетание из 16 элементов по 2. Их число находим по формуле (1.8):

?

Если комбинации из п элементов отличаются только порядком расположения этих элементов, то их называют перестановками из п элементов. Число перестановок из п элементов равно.

> Пример 1.7. Порядок выступления 7 участников конкурса определяется жребием. Сколько различных вариантов жеребьевки при этом возможно?

Решение. Каждый вариант жеребьевки отличается только порядком участников конкурса, т. е. является перестановкой из 7 элементов. Их число по формуле (1.12): ?

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

Например, из 5 элементов а, h, с, d, е по 3 размещениями с повторениями будут abc, cha, bed, cdb, bbe, ebb, heb, ddd и т. д., сочетаниями с повторениями будут abc, bed, bbe, ddd и т. д.

Число размещений с повторениями из п элементов по т равно.

а число сочетаний с повторениями из п элементов по т равно где определяется по формуле (1.8) или (1.9).

О Пример 1.8. В конкурсе по 5 номинациям участвуют 10 кинофильмов. Сколько существует вариантов распределения призов, если по каждой номинации установлены: а) различные призы; 6) одинаковые призы?

Решение, а) Каждый из вариантов распределения призов представляет собой комбинацию 5 фильмов из 10, отличающуюся от других комбинаций как составом фильмов, так и их порядком по номинациям (или и тем и другим), причем одни и те же фильмы могут повторяться несколько раз^[1], т. е. представляет размещение с повторениями из 10 элементов по 5. Их число по формуле (1.13) равно.

• б) Если по каждой номинации установлены одинаковые призы, то порядок следования фильмов в комбинации 5 призеров значения не имеет, и число вариантов распределения призов представляет собой число сочетаний с повторениями из 10 элементов по 5, определяемое по формуле (1.14) с учетом равенства (1.8):
  • ?

Если в перестановках из общего числа п элементов есть к различных элементов, при этом 1-й элемент повторяется п_{ раз, 2-й элемент — п₂ раз, к-й элемент — щ раз, причем п_{ + п₂ +…+ Щ=п> то такие перестановки называют перестановками с повторениями из п элементов. Число перестановок с повторениями из п элементов равно.

[> Пример 1.9. Сколько существует семизначных чисел, состоящих из цифр 4, 5 и 6, в которых цифра 4 повторяется 3 раза, а цифры 5 и 6 — по 2 раза?

Решение. Каждое семизначное число отличается от другого порядком следования цифр (причем п_х — 3, п₂ = 2, п₃ = 2, а их сумма равна 7), т. е. является перестановкой с повторениями из 7 элементов. Их число по формуле (1.15):

• [1] Любой фильм может получить призы как по одной, гак и, но нескольким (включая всепять) номинациям.