Комбинаторика и вероятность

Комбинаторика изучает способы подсчета числа элементов в конечных множествах. Формулы комбинаторики, используют при непосредственном вычислении вероятностей.
Множества элементов, состоящие из одних и тех же различных элементов и отличающиеся друг от друга только их порядком, называются перестановками этих элементов. Число всевозможных перестановок из n элементов обозначают через $P_n$, и это число равно n! (читается "эн-факториал"):
\(P_n=n\)   (1.3.1)
где
$n!=1\cdot 2\cdot 3\cdot ... \cdot n$.    (1.3.2)

З а м е ч а н и е 1. Для пустого множества принимается соглашение: пустое множество можно упорядочить только одним способом; по определению полагают $0! = 1$.

Размещениями называют множества, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений определяется формулой
$A_n^m=n(n-1)(n-2)\cdot ... \cdot (n-m+1)$ .    (1.3.3)

Сочетаниями из n различных элементов по m называются множества, содержащие m элементов из числа n заданных, и которые отличаются хотя бы одним элементом. Число сочетаний из n элементов по m обозначают: $C_n^m$  или $(^n_m)$. Это число выражается формулой

$C_n^m=\displaystyle\frac{n!}{m!\cdot (n-m)!}$.    (1.3.4)

З а м е ч а н и е 2. По определению полагают $C_n^0=1$.

Для числа сочетаний справедливы равенства:
$C_n^m=C_n^{n-m}$ ,  $C_{n+1}^{m+1}=C_n^m+C_n^{m+1}$,  (1.3.5)
$C_n^{0}+C_n^1+C_n^2+...+C_n^{n-1}+C_n^n=2^2$.   (1.3.6)

Последнее равенство иногда формулируется в виде следующей теоремы о конечных множествах:
Число всех подмножеств множества, состоящего их n элементов, равно $2^n$.
Отметим, что числа перестановок, размещений и сочетаний связаны равенством

$C_n^m=\displaystyle\frac{A_n^m}{P_m}$

З а м е ч а н и е 3. Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае множества с повторениями вычисляют по другим формулам.

Например, если среди n элементов есть $n_1$ элементов одного вида, $n_2$ элементов другого вида и т .д., то число перестановок с повторениями определяется формулой
$P_n(n_1,n_2,...,n_k)=\displaystyle\frac{n!}{n_1!\cdot n_2!\cdot ... \cdot n_k!}$   (1.3.7)
где $n_1+n_2+...+n_k=n$ .

Число размещений по m элементов с повторениями из n элементов равно
$n^m$ , то есть
$(A_n^m)$_{с повт} $=n^m$   (1.3.8)
Число сочетаний с повторениями из n элементов по m элементов равно числу сочетаний без повторений из n + m - 1 элементов по m элементов, то есть
$(C_n^m)$ _{с повт} $=?_{n+m-1}^m$ .    (1.3.9)

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

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

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

Классическая схема подсчета вероятностей пригодна для решения ряда сугубо практических задач. Рассмотрим, например, некоторое множество элементов объема N. Это могут быть изделия, каждое из которых является годным или бракованным, или семена, каждое из которых может быть всхожим или нет. Подобного рода ситуации описываются урновой схемой: в урне имеется N шаров, из них М голубых, (N - M) красных.

Из урны, содержащей N шаров, в которой находится М голубых шаров, извлекается n шаров. Требуется определить вероятность того, что в выборке объема n будет обнаружено m голубых шаров. Обозначим через А событие "в выборке объема n имеется m голубых шаров", тогда
$P(A)=\displaystyle\frac{C_M^mC_{N-M}^{n-m}}{C_N^n}=P_{M,N}(m,n)$   (1.3.10)

Пример 1. Сколькими различными способами можно выбрать три лица на три различные должности из десяти кандидатов?

Решение. Воспользуемся формулой (1.3.3). При n = 10, m = 3 получаем
$A_{10}^3=10\cdot 9\cdot 8=720$.

Пример 2. Сколькими различными способами могут разместиться на скамейке 5 человек?

Решение. Согласно формуле (1.3.1) при n=5 находим
P₅ =5!=1·2·3·4·5=120.

Пример 3. Сколькими способами можно выбрать три лица на три одинаковые должности из десяти кандидатов?

Решение. В соответствии с формулой (1.3.4) находим
$C_{10}^3=\displaystyle\frac{10!}{3!\cdot(10-3)!}=\frac{10!}{3!7!}=\frac{10\cdot 9\cdot 8}{1\cdot 2\cdot 3}=120$

Пример 4.  Сколько различных шестизначных чисел можно записать с помощью цифр 1; 1; 1; 2; 2; 2?

Решение. Здесь нужно найти число перестановок с повторениями, которое определяется формулой (1.3.7). При k =2, n₁ = 3, n₂ = 3, n=6 по этой формуле получаем
$P_6(3;3)=\displaystyle\frac{6!}{3!3!}=\frac{1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6}{1\cdot 2\cdot 3\cdot 1\cdot 2\cdot 3}=20$

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

Решение. В слове замок все буквы различны, всего их пять. В соответствии с формулой (1.3.1) получаем P₅ = 5! = 1·2·3·4·5 = 120. В слове ротор, состоящем из пяти букв, буквы p и o повторяются дважды. Для подсчета различных перестановок применяем формулу (1.3.7). При n = 5, n₁ = 2, n₂= 2 по этой формуле находим

$P_5(2;2)=\displaystyle\frac{5!}{2!2!}=\frac{1\cdot 2\cdot 3\cdot 4\cdot 5}{1\cdot 2\cdot 1\cdot 2}=30$

В слове топор буква о повторяется дважды, поэтому
$P_5(2)=\displaystyle\frac{5!}{2!}=\frac{1\cdot 2\cdot 3\cdot 4\cdot 5}{1\cdot 2}=60$

В слове колокол, состоящем из семи букв, буква к встречается дважды, буква о - трижды, буква л - дважды. В соответствии с формулой (13.7) при n = 7, n₁= 2, n₂= 3, n_з = 2 получаем
$P_7(2;3;2)=\displaystyle\frac{7!}{2!3!2!}=210$

Пример 6. На пяти одинаковых карточках написаны буквы И, К, М, Н, С. Карточки перемешиваются и наугад раскладываются в ряд. Какова вероятность того, что получится слово МИНСК?

Решение. Из пяти различных элементов можно составить Р5 перестановок:
$P_5=1\cdot 2\cdot 3\cdot 4\cdot 5=120$. Значит, всего равно возможных исходов будет 120, а благоприятствующих данному событию - только один. Следовательно,
$P=\frac{1}{120}$

Пример 7.  Из букв слова ротор, составленного с помощью разрезной азбуки, наудачу последовательно извлекаются 3 буквы и складываются в ряд. Какова вероятность того, что получится слово тор?

Решение. Чтобы отличить одинаковые буквы друг от друга, снабдим их номерами: p₁, p₂, 0₁, 0₂. Общее число элементарных исходов равно: $A_5^3=5\cdot 4\cdot 3=60$. Слово ротор получится в $1\cdot 2\cdot 2=4$ случаях (то₁р₁, то₁р₂, то₂р₁, то₂р₂). Искомая вероятность равна $P=\frac{4}{60}=\frac{1}{15}$

При подсчете числа благоприятных случаев здесь воспользовались правилом произведения: букву m можно выбрать одним способом, букву о - двумя, букву р - двумя способами.

Пример 8. На шести одинаковых по форме и размеру карточках написаны буквы слова талант - по одной букве на каждой карточке. Карточки тщательно перемешаны. их вынимают наудачу и располагают на столе одна за другой. Какова вероятность снова получить слово талант?

Решение. Занумеруем карточки с буквами:

1	2	3	4	5	6
а	а	л	н	т	т

Слово т а л а н т (513246) не изменится, если буквы а переставить местами, но по расположению карточек получится иная комбинация: т а л а н т (523146). Если в каждой из этих двух комбинаций то же проделать с буквой т, то получим еще 2 различные комбинации карточек со словом талант. Значит, появлению слова талант благоприятствуют 4 элементарных исхода. Общее число равно возможных элементарных исходов равна числу перестановок из 6 элементов: n = 6! = 720. Следовательно, искомая вероятность

$P=\frac{m}{n}=\frac{4}{720}=\frac{1}{180}$.

З а м е ч а н и е. Эту вероятность можно найти и с помощью формулы (1.3.7), которая при n = 6, n₁ = 1, n₂ = 1, n_з = 2, n₄ = 2 принимает вид:

$P_6(1;1;2;2)=\displaystyle\frac{6!}{1!\cdot 1!\cdot 2!\cdot 2!}=180$. Таким образом, Р = 1/180.

Пример 9.  На пяти одинаковых карточках написаны буквы: на двух карточках л, на остальных трех и. Выкладывают наудачу эти карточки в
ряд. Какова вероятность того, что при этом получится слово лилии?

Решение. Найдем число перестановок из этих пяти букв с повторениями.
По формуле (1.3.7) при n = 5, n₁ = 2, n₂ = 3 получаем
$P_5(2;3)=\displaystyle\frac{5!}{2!\cdot 3!}=10$
Это общее число равновозможных исходов опыта, данному событию А - "появление слова лилии" благоприятствует один. В соответствиис формулой (1.2.1) получаем

$P(A)=\frac{1}{10}=0,1$

Пример 10. В партии из 10 деталей 7 стандартных. Найти вероятность
того, что среди 6 взятых наудачу деталей 4 стандартных.

Решение. Общее число возможныIx элементарных исходов испытания равно числу способов, которыми можно извлечь 6 деталей из 10, то есть числу сочетаний из 10 элементов по 6 элементов ( $C_{10}^6$).

Определяем число исходов, благоприятствующих событию А - "среди 6 взятых деталей 4 стандартных". Четыре стандартные детали из семи стандартных можно взять $C_7^4$ способами, при этом остальные 6 - 4 = 2 детали должны быть нестандартными; взять же 2 нестандартные детали из 10 - 7 = 3 нестандартных деталей можно $C_3^2$ способами. Следовательно, число благоприятных исходов равно $C_7^4\cdot C_3^2$.

Искомая вероятность равна отношению числа исходов, благоприятствующих событию, к числу всех элементарных исходов:
$P(A)=\displaystyle\frac{C_7^4\cdot C_3^2}{C_{10}^6}=0,5$

З а м е ч а н и е. Последняя формула является частным случаем формулы (1.3.10): N= 10, М= 7, n = 6, m = 4.

Пример 11. Среди 25 студентов группы, в которой 10 девушек, разыгрывается 5 билетов. Найти вероятность того, что среди обладателей билетов окажутся 2 девушки.

Решение. Число всех равновозможных случаев распределения 5 билетов среди 25 студентов равно числу сочетаний из 25 элементов по 5, то есть  $C_{25}^5$. Число групп по трое юношей из 15, которые могут получить билеты, равно $C_{15}^{3}$. Каждая такая тройка может сочетаться с любой парой из десяти девушек, а число таких пар равно $C_{10}^2$.Следовательно, число групп по 5 студентов, образованных из группы в 25 студентов, в каждую из которых будут входить трое юношей и две девушки, равно произведению $?_{15}^3\cdot C_{10}^2$. Это произведение равно числу благоприятствующих случаев распределения пяти билетов среди студентов группы так, чтобы три билета получили юноши и два билета - девушки. В соответствии с формулой (1.2.1) находим искомую вероятность

$P(A)=\displaystyle\frac{C_{15}^3\cdot C_{10}^2}{C_{25}^5}=\frac{195}{506}$

З а м е ч а н и е. Последняя формула является частным случаем формулы (1.3.10): N= 25, М= 15,n = 5, m = 3.

Пример 12. В ящике находятся 15 красных, 9 голубых и 6 зеленых шаров. Наудачу вынимают 6 шаров. Какова вероятность того, что вынуты 1 зеленый, 2 голубых и 3 красных шара (событие А)?

Решение. В ящике всего 30 шаров. При данном испьпании число всех равновозможных элементарных исходов будет $C_{30}^6$. Подсчитаем число элементарных исходов, благоприятствующих событию А. Три красных шара из 15 можно выбрать $C_{15}^3$ способами, два голубых шара из 9 можно выбрать $C_9^2$ споcобами, один зеленый из 6 - $C_6^1$ способами.
Следовательно (в силу принципа произведения в комбинаторике), число исходов, благоприятствующих событию А, будет $m=C_{15}^3\cdot C_9^2\cdot C_6^1$ . По формуле (1.2.1) находим искомую вероятность
$P(A)=\displaystyle\frac{C_{15}^3\cdot C_9^2\cdot C_6^1}{C_{30}^6}=\frac{24}{145}$

Пример 13. В ящике 15 шаров, из которых 5 голубых и 10 красных. Наугад выбирают 6 шаров. Найти вероятность того, что среди вынутых шаров 2 голубых.

Решение. Общее число элементарных исходов данного опыта равно числу сочетаний из 15 по 6, то есть
$C_{15}^6=\frac{15!}{6!\cdot 9!}=5005$
Число благоприятных исходов равно произведению
$C_5^2\cdot C_{10}^4=2100$
Искомая вероятность определяется формулой (1.3.10):
$P=\displaystyle\frac{C_5^2\cdot C_{10}^4}{C_{15}^6}=\frac{2100}{5005}$

Пример 14. Игральный кубик подбрасывают 10 раз. Какова вероятность того, что при этом грани 1, 2, 3, 4, 5, 6 выпадут соответственно 2, 3, 1, 1, 1, 2 раза (событие А)?

Решение. Число исходов, благоприятных для события А, подсчитаем по формуле (1.3.7):
$m=\displaystyle\frac{(2+3+1+1+1+2)!}{2!\cdot 3!\cdot 1!\cdot 1!\cdot 1!\cdot 2!}=2\cdot 3\cdot 5\cdot 7\cdot 8\cdot 9\cdot 10$
Число всех элементарных исходов в данном опыте n = 6¹⁰, поэтому
$P(A)=\displaystyle\frac{2\cdot 3\cdot 5\cdot 7\cdot 8\cdot 9\cdot 10}{6^{10}}=\frac{700}{6^7}$

Задачи
1. На 5 одинаковых карточках написаны буквы Б, Е, Р, С, Т. Эти карточки наудачу разложены в ряд. Какова вероятность того, что получится слово БРЕСТ?
2. В ящике 4 голубых и 5 красных шаров. Из ящика наугад вынимают 2 шара. Найдите вероятность того, что эти шары разного цвета.
3. В бригаде 4 женщины и 3 мужчины. Среди членов бригады разыгрываются 4 билета в театр. Какова вероятность того, что среди обладателей билетов окажется 2 женщины и 2 мужчины?
4. В ящике 10 шаров, из которых 2 белых, 3 красных и 5 голубых.Наудачу извлечены 3 шара. Найдите вероятность того, что все 3 шара разного цвета.
5. На пяти одинаковых карточках написаны буквы л, м, о, о, т. Какова вероятность того, что извлекая карточки по одной наугад, получим в порядке их выхода слово молот?
6. Из партии, содержащей 10 изделий, среди которых 3 бракованных, наудачу извлекают 3 изделия. Найдите вероятность того, что в полученной выборке одно изделие бракованное.
7. Из десяти билетов выигрышными являются два. Чему равна вероятность того, что среди взятых наудачу пяти билетов один выигрышный?

Ответы
1.1/120. 2. 5/9. 3. 18/35.  4 . 0,25. 5. 1/60. 6. 21/40. 7. 5/9.

Вопросы
1. Что назьrвают перестановками?
2. По какой форме вычисляют число перестановок из n различных элементов?
3. Что называют размещениями?
4. По какой формуле вычисляют число размещений из n различных элементов по m элементов?
5. Что называют сочетаниями?
6. По какой формуле вы исляют число сочетаний из n элементов по m элементов?
7. Каким равенством связаны числа перестановок, размещений и сочетаний?
8. По какой формуле вычисляется число перестановок из n элементов, если некоторые элементы повторяются?
9. Какой формулой определяется число размещений по m элементов с повторениями из n элементов?
10. Какой формулой определяется число сочетаний с повторениями из n элементов по m элементов?