Элементы комбинаторики. В теории вероятностей часто используют размещения, перестановки и сочетания

В теории вероятностей часто используют размещения, перестановки и сочетания.

Пусть дано множество . Размещением из n элементов по k называется любое упорядоченное подмножество k элементов множества А. Таким образом, размещения отличаются либо самими элементами, либо их порядком. Размещения из n элементов по n элементов (т.е. при k=n ) называются перестановками. Сочетанием из n элементов по k называется любое подмножество k элементов множества А. Различные сочетания отличаются хотя бы одним элементом.

Пусть, например, дано множество . Размещениями из 3 элементов этого множества по 2 будут . Сочетаниями из 3 элементов по 2 являются: . Перестановки из 3 элементов: .

Число перестановок из n элементов вычисляется по формуле ; число размещений из n элементов по k - по формуле ; число сочетаний из n элементов по k - по формуле . Отметим, что .

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

1. Число способов, которыми можно рассадить за столы по 2 студента группу в 20 человек, равно .

2. Число способов распределения 5 должностей между 5 лицами равно .

3. Число партий шахматной игры среди 12 участников чемпионата (если каждый участник играет только одну партию друг с другом) равно .

4. Число способов, которыми можно выбрать делегацию в состав 15 человек из группы в 20 человек, равно .

Пример 1. В цехе работают 6 мужчин и 4 женщины. По табельным номерам наугад отобраны 7 человек. Найти вероятность того, что среди отобранных лиц окажутся 3 женщины.

Решение. Требуется найти вероятность события A={среди отобранных лиц - 3 женщины}. В данной задаче элементарное событие - набор из 7 человек. Так как последовательность, в которой они отбираются, несущественна, число всех таких наборов есть число сочетаний из 10 элементов по 7: . По условию все элементарные события равновозможны. Поэтому можно использовать классический способ вычисления вероятности. Найдем число элементарных исходов, благоприятствующих событию A. Это будет число наборов, в которых 3 человека выбраны из 4 женщин, а 4 человека - из 6 мужчин. Из 4 женщин троих можно выбрать способами, а из 6 мужчин четверых - способами. Благоприятствующие событию A исходы получаются, когда набор из 3 женщин дополняется 4 мужчинами. Число таких способов будет равно . По классическому определению вероятности получим .

Пример 2. 2 студента условились встретиться в определенном месте между 18 и 19 часами. Пришедший первым ждет второго в течение 15 мин, после чего уходит. Определить вероятность встречи, если время прихода каждого студента независимо и равновозможно в течение указанного часа.

Решение. Пусть x и y - моменты прихода первого и второго студентов соответственно. Пространство элементарных событий можно записать в виде точек квадрата
W={(x,y):0£x£60, 0£y£60}.
Событие A={встреча состоялась} по условию задачи имеет вид A={(x,y):|x-y|<15} (рис.1). Данная область лежит между прямыми x-y=15 и
x-y=-15 (на рисунке заштрихована). Меры (площади) указанных областей равны пл.W=60², пл.А=60²-(60-15)². Искомая вероятность, если воспользоваться геометрическим определением, равна .