Комбинаторика
1. О чём речь
Комбинаторика — это особый раздел математики, занимающийся вопросами подсчёта количества объектов. Объекты, о которых идёт речь, — конечно же, не яблоки, не землекопы и не что-либо в таком духе. С яблоками ведь, как правило, всё просто: есть 10 ящиков по 20 яблок в каждом, сколько всего? Тут и пятиклассник справится. А если я спрошу, сколько есть способов взять из этих ящиков 40 яблок так, чтобы из каждого ящика было взято хотя бы одно яблоко? Расчёт сразу становится не таким уж простым, и тут на помощь и приходит комбинаторика.Зачем это нужно? Главным образом для расчёта вероятностей. Ну вот пример. Идёт игра в дурака; были сданы карты, и вы, делая первый ход, думаете: есть ли у вашего противника на руке хотя бы одна козырная карта? Если карты мешались как следует, этого, конечно, невозможно узнать наверняка. Однако шанс, или, говоря научным языком, вероятность того, что козырная карта есть, можно оценить!В самом деле. В вашей колоде 52 карты; одна из них уже выложена как козырь. Осталась 51 карта, из них 12 козырных (не 13, потому что одна козырная уже лежит отдельно). Из этих карт вы раздаёте шесть случайных себе и шесть случайных противнику. Пусть вам досталось два козыря (вместо двух можно взять сколько угодно — рассуждения останутся в силе, только числа немного поменяются); тогда, перед тем, как вы раздадите карты противнику, у вас в колоде остаётся 45 карт, из которых 10 козырных. И вот это уже комбинаторный вопрос совершенно в духе озвученного ранее: сколько существует способов выбрать шесть карт из 10 козырных и 35 обычных так, чтобы хотя бы одна выбранная была козырной, и сколько существует способов выбрать шесть карт из 45 всего?Если бы мы знали ответ, мы могли бы поделить первое число на второе, чтобы узнать долю «плохих» для нас комбинаций карт, которая в данном случае была бы не чем иным, как вероятностью «плохого» исхода событий. (Подробнее о вероятностях я расскажу в отдельной статье.)Прежде чем перейти, собственно, к комбинаторике, я скажу ответ. Число способов выбрать шесть карт из 45 равно 8 145 060 (просто перебором вариантов и не сосчитаешь, а?); число способов выбрать шесть карт, чтобы хоть одна была козырной, равно (в нашем случае) 6 521 900. Итого вероятность того, что у противника есть хотя бы одна козырная карта, равнаСоответственно, в привычных журналистам процентах получаем вероятность около 80%. Можно интерпретировать это как «козырная карта у противника есть почти наверняка».![]()
2. Перестановки
Путь к решению задач с картами мы начнём издалека, с самого простого комбинаторного объекта — перестановки. Название тут говорит само за себя. Чтобы получить всевозможные перестановки некой совокупности объектов, нужно просто по очереди выставлять их в ряд в любом возможном порядке. Разные порядки предметов в ряду и будут перестановками.В качестве примеров мы возьмём шары для бильярда.Итак, пусть у нас есть
Яркий жёлтый шар на этой картинке подсказывает нам, как получить всевозможные перестановки трёх шаров, зная всевозможные перестановки двух: взять каждую перестановку двух и «впихнуть» третий шар по очереди в каждую доступную позицию: в начало, в середину и в конец. Каждая перестановка из двух шаров таким образом «породит» три перестановки из трёх шаров, и несложно проверить, что получить одну и ту же перестановку несколько раз этим методом не получится. Значит, число перестановок из трёх шаров в три раза больше числа перестановок из двух:
(2.1)
Подставляя эту формулу в предыдущую, получаем![]()
Теперь раскроем в этой формуле![]()
Это число, равное произведению первых![]()
(Заметьте, что последний выбор оказывается «выбором» из одного варианта. Ну ничего страшного, голосование с одним кандидатом, как известно всем, пожившим в Советском Союзе, — тоже голосование.)Этот вариант рассуждения может показаться несколько умозрительнее, но такие умозрительные рассуждения, как водится, следует проводить с двойной осторожностью. (Особенно внимательно стоит следить за независимостью отдельных решений. Счесть зависимые события независимыми — одна из излюбленнейших ошибок при решении задач по теории вероятности.)![]()
Задача
Каждое утро вожатый выстраивает группу из 20 пионеров в шеренгу случайным образом.
Каков шанс трёх закадычных друзей, Пети, Васи и Егора, оказаться рядом в шеренге?Итак, чтобы найти эту вероятность, нам надо на общее количество вариантов расстановки
пионеров поделить число «хороших» вариантов, то есть вариантов, в которых Петя, Вася
и Егор оказываются рядом. Общее число перестановок 20 пионеров мы уже знаем — оно равно
. Значит, каждая
из найденных 6,5 квадриллионов перестановок может существовать в шести вариантах, и
всего «хороших» перестановок пионеров
. Что ж, теперь остаётся прикинуть искомую вероятность:
друзей
в группе из
пионеров искомая вероятность равна
Теперь давайте подумаем, как посчитать число «хороших» перестановок. В любой «хорошей» перестановке Петя, Вася и Егор стоят рядом — значит, при пересчёте можно считать их одним большим целым («сверхчеловеком», если хотите!). Число перестановок 17 пионеров и одного сверхпионера (итого 18 субъектов) нам тоже известно — оно равно![]()
Однако, Петя, Вася и Егор могут при этом размещаться произвольным образом относительно друг друга внутри своей «неделимой группы». Таких возможностей ровно![]()
Около 1,6%. Крепитесь, пионеры! (Впрочем, вероятность хоть раз оказаться рядом за 14 дней смены уже почти 20%! Но об этом — в статье о вероятностях.)Для тренировки абстрактного мышления можете проверить, что для![]()
3. Размещения
Пойдём дальше. (По пути усложнения, разумеется!) Пусть у нас по-прежнему естьОзвучить эту формулу можно так: «если, желая выбрать размещение![]()
Она отличается от (2.1) потому, что в данном случае нам пришлось остановиться раньше — ведь![]()
Эта величина называется убывающим факториалом из![]()
Вот мы заодно и увидели, что в комбинаторике можно не только умножать, но и делить. (Но только очень осторожно.)В завершение давайте испытаем нашу формулу на практике. Попробуем посчитать число размещений двух шаров из четырёх. Теоретически оно должно быть равно![]()
Сколько же их на деле, нам подскажут бильярдные шары.![]()
4. Сочетания
Заключительный номер базовой программы — сочетания. Будем всевозможными способами выбиратьЭта величина называется биномиальным коэффициентом из![]()
То есть способов выбрать из![]()
5. Бином Ньютона
Доказательство бинома Ньютона — традиционная задачка в курсе матанализа, дающая начинающим студентам представление о методе математической индукции. Сам бином выглядит так: если даны два вещественных слагаемых(БН)
Получилась всем известная формула квадрата суммы. Становится видна и главная проблема при раскрытии скобок «в лоб»: многие слагаемые одинаковы и их нужно собрать вместе — привести подобные, то есть подсчитать, сколько копий каждого слагаемого есть в итоговой сумме, и выписать в итоге только разные слагаемые с соответствующими множителями.Для пущей наглядности выпишем ещё вариант с![]()
Видно также, что все слагаемые имеют вид![]()
То есть слагаемых в выражении для![]()
Все слагаемые имеют вид![]()
Из каждой скобки берётся либо![]()
Остаётся их все сложить чудесным значком![]()
Точно такой же, как и было обещано в формуле (БН). (Аплодисменты.)Кстати, здесь можно увидеть вот какую штуку. Всего слагаемых было![]()
Вот так мы попутно ещё и доказали интересную формулу.![]()