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

Раздел 5. ОСНОВЫ КОМБИНАТОРИКИ

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

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

Принцип умножения: если действие 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)

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

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

Количество способов, которым можно разбить множество из 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! раз, и т.д. Конечно, дело вкуса, но кажется, так считать проще, а главное, не надо запоминать формулу.