Раздел 5. Основы комбинаторики

5.1. Основные принципы комбинаторики.

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

Принцип умножения: если действие 1 можно выполнить n способами, а действие 2 можно выполнить m способами, то сложное действие, состоящее в выполнении обоих действий 1 И 2 (одновременно или последовательно) можно выполнить nm способами.

Принцип сложения: если действие 1 можно выполнить n способами, а действие 2 можно выполнить m способами, то сложное действие, состоящее в выполнении одного из действий 1 ИЛИ 2 (но не обоих), можно выполнить n+m способами.

Разложение сложных действий на простейшие: для упрощения подсчета сложные действия всегда разлагают на простейшие, а дальше используют подходящий принцип подсчета (умножения или сложения).

Факториалы: n!=n(n-1)(n-2)...1 Факториалы ассоциируются со стандартным действием - перестановкой n элементов (точнее - перестановкой n элементов на n местах - каждый элемент занимает строго одно место).

Размещения: перестановка n элементов на k местах k>n. Это "недоделанный факториал": n(n-1)(n-2)...(n-k+1)

Вероятность - мера уверенности в том, что некоторое событие произойдет (измеряется числом от 0 до 1)

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

5.2. Разбиения на группы.

Количество способов, которым можно разбить множество из n предметов на k различимых групп, содержащих соответственно n(1), n(2), ... , n(k) предметов, равно n/[n(1)! n(2)! ... n(k)!]

Типовая задача: размещение предметов по ящикам (ячейкам); как располагаются друг относительно друга предметы, попавшие в один ящик, нас не интересует. Например, нам нужно подсчитать, сколько существует способов разместить 7 шаров по 7 ящикам таким образом, что в первом ящике находится 3 предмета, во втором и третьем - по два предмета, остальные, разумеется, пусты. Обратите внимание, что группы различимы (у них свой номер), а как лежат шары, попавшие в один ящик, нас не интересует (они не нумерованы). Ответ 7!/[3!2!2!] (тут можно конечно приписать в знаменателе четыре раза 0! для пустых ячеек, но по определению 0! равен 1).

Другая ситуация, полностью сводимая к предыдущей: составление слова из нескольких букв, которые могут повторяться. В этом случае на группы фактически разбиваются занумерованные места для букв. Например, можно подсчитать, каковы шансы случайно составить из набора букв ММ ААА ТТ Е И К слово "МАТЕМАТИКА". Такое слово только одно (так что в числителе при вычислении вероятности будет 1) . А всего из этих букв можно слепить столько же слов, скольким числом способов можно разбить занумерованные 10 мест на 6 групп, в первой из которых (численностью 2) будут буквы М, во второй (численностью 3) - буквы А, и т.д. Всего таких способов в соответствии с общей формулой 10!/[2!3!2!1!1!1!] - это знаменатель для вычисленной вероятности.

В последней задаче можно использовать также вместо общей формулы интересный способ рассуждения, основанный на том, что нумеруются не места, а сами буквы. Всего букв (занумерованных в произвольном порядке) 10. Поскольку они занумерованы, они различны, их можно переставлять 10! способами. Но перестановка двух букв Т будет незаметна, поэтому 10! нужно уменьшить в 2! раз, перестановка трех Т также незаметна, то есть результат надо еще уменьшить в 3! раз, и т.д. Конечно, дело вкуса, но кажется, так считать проще, а главное, не надо запоминать формулу.

Третий еще более простой способ решения этой задачи, основанные на идее последовательного выбора, мы увидим, когда пройдем сочетания (см. в конце лекции).

Двухэтапные разбиения.

Бывают ситуации, когда важен не номер (или содержание) группы, а только число элементов в ней. Например, нам нужно подсчитать, сколько существует способов разложить 7 шаров по 7 ящикам таким образом, что в каком-то одном из ящиков окажется 3 шара, в каких-то двух - по два, а остальные будут пусты. Отличие от ситуации в начале лекции - в том, что ящики теперь не нумерованы. Можно свести задачу к уже решенной, но сначала нужно разбить ящики на группы - выбрать один (присвоим ему номер 1) для трех шаров, два (с номерами 2 и 3) для двух шаров, остальные номера 4-7 достаются пустым ящикам. Это стандартная задача разбиения 7 предметов (ящиков) на 3 группы численностью 1, 2 и 4. Число разбиений равно 7!/[1!2!4!]. Полученный результат по принципу умножения нужно умножить на результат из первой типовой задачи лекции. Ответ:( 7!/[1!2!4!])(7!/[3!2!2!] ).

Выбор. Сочетания.

Выбор - это ситуация разбиения на две группы (выбранные - оставшиеся). Поэтому число способов выбрать k элементов из n равно числу разбиений n элементов на две группы по k и n-k элементов, то есть n!/k!( n-k)!. Это число ввиду стандартности и широкой распространенности задачи выбора носит специальное название - число сочетаний из n элементов по k, и обозначается

.

Обычно для вычислений используется наряду с основной

используется также упрощенная формула (которая особенно удобна, когдаk мало по сравнению с n:

Поскольку выбранные и оставшиеся с точки зрения разбиения на группы равноправны (все равно, какой список составлять, тех кого приглашать на день рождения, или наоборот, кого не приглашать – результат будет тот же – придут приглашенные), то

Сложная выборка.

СовокупностьN элементов, из которой производится выборка, обычно бывает неоднородна, при этом только часть элементов (M)обладает определенным свойством, остальные N–M им не обладают. Поэтому и в выборке из n элементов только часть m элементов будет обладать нужным свойством. Ясно, что для получения такого элемента и выбирать нужно из числа тех, которые им обладают (девочку надо выбирать из девочек, а мальчика из мальчиков – и никакие бантики потом не помогут). Поэтому вероятность того, что в выборке из n элементов только m элементов будет обладать нужным свойством, равна

Кстати, в числителе здесь происходит разбиение на 2 группы, поэтому возвращаясь к самой первой задаче лекции можно дать новый метод для подсчета количества способов, которым можно разбить множество из n предметов на k различимых групп, содержащих соответственно n(1), n(2), ... , n(k) предметов

Прямым подсчетом можно убедиться, что это равно прежней величине с факториалами

Например, количество способов разложить 7 шаров по 7 ячейкам так, чтобы в первой ячейке лежало 3 шара, во второй и третьей по 2 шара, а остальные ячейки были пусты, равно

Ясно, что последнее сочетание можно не писать, так что ответ еще проще

После этого можно вообще забыть про жуткие формулы с факториалами.

Статистическая оценка параметров. Принцип максимума правдоподобия.

Выборку обычно производят для того, чтобы оценить, как устроена исходная большая совокупность. Так на последних выборах президента постоянно опрашивали небольшую часть населения при выходе с избирательных участков, и на сайте http://www.26marta.com/ можно было постоянно видеть ход голосования. Выборка обычно представляет только малую часть совокупности, тем не менее она дает правдоподобные результаты. Хотелось бы, чтобы это правдоподобие было максимальным. Пусть число M (количество элементов совокупности, обладающих нужным свойством) неизвестно. Обозначим его через X. Потребуем, чтобы вероятность получения той выборки, которая у нас уже есть,

была наибольшей. Это и называется принципом максимума правдоподобия.

Практически, чтобы найти здесь точку максимума, не используют производных, а вместо этого исследуют отношение

Очевидно, что сначала это отношение больше 1, потом меньше 1, так что, нужно найти момент, когда оно максимально близко к 1. Расписав факториалы, которые практически полностью сокращаются, решаем уравнение

.

Аналогично можно оценивать величину N (общее число элементов совокупности), предварительно обеспечив, чтобы часть элементов M обладала некоторым свойством (на лекции мы красили некоторое количество белых медведей).