Комбинаторика

     Поясним сказанное на примере. Пусть в  урне имеется 4 шара, окрашенные: один —  в красный цвет (А), один — в  синий цвет (В), один — в черный цвет (С) и один — во все эти три цвета (АВС). Чему равна вероятность того, что извлеченный из урны шар имеет красный цвет?

     Так как из четырех шаров два имеют  красный цвет, то Р(А) = 2 / 4 = 1 / 2. Рассуждая  аналогично, найдем Р (В) = 1 / 2, Р (С) = 1/ 2. Допустим теперь, что взятый шар имеет синий цвет, т. е. событие В уже произошло. Изменится ли вероятность того, что извлеченный шар имеет красный цвет, т. е. изменится ли вероятность события А? Из двух шаров, имеющих синий цвет, один шар имеет и красный цвет, поэтому вероятность события А по-прежнему равна 1 / 2. Другими словами, условная вероятность события А, вычисленная в предположении, что наступило событие В, равна его безусловной вероятности. Следовательно, события А и В независимы. Аналогично придем к выводу, что события A и С, В и С независимы. Итак, события А, В и С попарно независимы.

     Независимы  ли эти события в совокупности? Оказывается, нет. Действительно, пусть  извлеченный шар имеет два  цвета, например синий и черный. Чему равна вероятность того, что этот шар имеет и красный цвет? Лишь один шар окрашен во все три цвета, поэтому взятый шар имеет и красный цвет. Таким образом, допустив, что события В и С произошли, приходим к выводу, что событие А обязательно наступит. Следовательно, это событие достоверное и вероятность его равна единице. Другими словами, условная вероятность Р_BC (A)= 1 события А не равна его безусловной вероятности Р (А) = 1 / 2. Итак, попарно независимые события А, В, С не являются независимыми в совокупности.

     Приведем  теперь следствие из теоремы умножения.

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

     Р (А₁А₂ ... А_n) = Р (А₁) Р (А₂) ... Р (А_n).

     Доказательство:

     Рассмотрим  три события: А, В и С. Совмещение событий А, В и С равносильно  совмещению событий АВ и С, поэтому

     Р (AВС) = Р (АВ * С). 

     Так как события А, В и С независимы в совокупности, то независимы, в  частности, события АВ и С, а также  А и В. По теореме умножения для двух независимых событий имеем:

     Р (АВ * С) = Р (АВ) Р (С) и Р (АВ) = Р (А) Р (В). 

     Итак, окончательно получим

     Р (AВС) = Р (А) Р (В) Р (С). 

     Для произвольного n доказательство проводится методом математической индукции. 

     З а м е ч а н и е. Если события А₁, А₂, ..., А_n независимы в совокупности, то и противоположные им события

     также независимы в совокупности. 

     Пусть в результате испытания могут  появиться n событий, независимых в совокупности, либо некоторые из них (в частности, только одно или ни одного), причем вероятности появления каждого из событий известны. Как найти вероятность того, что наступит хотя бы одно из этих событий? Например, если в результате испытания могут появиться три события, то появление хотя бы одного из этих событий означает наступление либо одного, либо двух, либо трех событий. Ответ на поставленный вопрос дает следующая теорема.

     Теорема. Вероятность появления хотя бы одного из событий А₁ , А₂ , ..., А_n , независимых в совокупности, равна разности между единицей и произведением вероятностей противоположных событий 

     Р (A) = 1 — q₁q₂ ... q_n.(*) 

     Доказательство:

     Обозначим через А событие, состоящее в  появлении хотя бы одного из событий  А₁,А₂, ...,A_n. События А и

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

     Отсюда, пользуясь теоремой умножения, получим

     или

     Ч а с т н ы й   с л у ч а й. Если события А₁ , А₂ , ..., А_n имеют одинаковую вероятность, равную р, то вероятность появления хотя бы одного из этих событий

     P (A) = l — qⁿ. (**)

      Заключение

      Перечисленные подзадачи в программировании обычно рассматривают для следующих  комбинаторных конфигураций: перестановки элементов множества, подмножества множества, сочетания из n элементов множества по k элементов (k-элементные подмножества множества, состоящего из n³k элементов), размещения (упорядоченные подмножества множества, то есть отличающиеся не только составом элементов, но и порядком элементов в них), разбиения множества (множество разбивается на подмножества произвольного размера так, что каждый элемент исходного множества содержится ровно в одном подмножестве), разбиения натуральных чисел на слагаемые, правильные скобочные последовательности (различные правильные взаимные расположения n пар открывающихся и закрывающихся скобок).

      Большинство указанных конфигураций были подробно рассмотрены в [1-3]. Однако при генерации  различных конфигураций использовались в основном нерекурсивные алгоритмы. Опытные же участники олимпиад в  подобных случаях при программировании используют в основном именно рекурсию, с помощью которой решение рассматриваемых задач зачастую можно записать более кратко и прозрачно. Поэтому для полноты изложения данной темы приведем ряд рекурсивных комбинаторных алгоритмов и рассмотрим особенности применения рекурсии в комбинаторике.

       Список литературы 

1. Окулов  С.М. Перестановки. “Информатика”, №7, 2000.
2. Окулов С.M. Комбинаторные задачи. “Информатика”, №10, 13, 2000.
3. Усов Б.Б. Комбинаторные задачи. “Информатика”, №39, 2000.
4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.
5. Брудно A.Л., Каплан Л.И. Московские олимпиады по программированию. М.: Наука, 1990.
6. Кнут Д. Конкретная математика. Основание информатики. М.: “Мир”, 1998.
7. Липский В. Комбинаторика для программистов. М.: “Мир”, 1988.
8. Андреева Е.В. Еще раз о задачах на полный перебор вариантов. “Информатика”, №45, 2000.