4. Разбиения и полиномиальная теорема

Разбиением множества A на k частей называется семейство его подмножеств, такое, что

1) при ;

2) .

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

Теорема 8. Число упорядоченных разбиений множества мощности n на k частей мощностей равно .

Д о к а з а т е л ь с т в о . Первую часть разбиения можно выбрать способами. После этого в остается элементов и из них вторую часть можно выбрать способами и т. д. По обобщенному правилу произведения, общее число разбиений равно . Используя формулу для числа сочетаний, приходим, после сокращений, к окончательному ответу . 

Величина обозначается через и называется полиномиальным коэффициентом.

Задача 2. Найти число слов в алфавите , в которых буква встречается раз, , .

Р е ш е н и е. Занумеруем позиции букв в слове слева направо числами от 1 до n. Пусть – множество номеров всех тех позиций, в которых находится буква , . Семейство множеств является упорядоченным разбиением множества и однозначно определяет слово. Таким образом, имеется взаимно однозначное соответствие между словами, число которых требуется подсчитать, и разбиениями, о которых говорится в теореме 8. Поэтому искомое число равно .

Теорема9. .

Д о к а з а т е л ь с т в о. Запишем левую часть в виде произведения n сомножителей: . Раскроем скобки, не группируя одинаковые сомножители в виде степени и не приводя подобные. Очевидно множество слагаемых, полученных таким образом в результате раскрытия скобок, образует множество всех слов длины n в алфавите . После группировки одинаковых сомножителей слагаемые этой суммы примут вид , где , причем такое слагаемое встретится столько раз, сколько имеется слов, в которых буква встречается раз, буква – раз, . . . , буква – раз. Применяя решение задачи 2, видим, что после приведения подобных коэффициент при будет равен . 

Задачи

1. Сколько различных слов можно составить, переставляя буквы в слове “математика”?

2. Каким числом способов можно разбить 14 человек на 7 пар?

3. Каким числом способов можно разместить 7 студентов в трех комнатах общежития  одно-, двух- и четырехместной?

4. Код замка состоит из пяти десятичных цифр. Известно, что среди них один раз встречается цифра 0 и дважды  цифра 3. Сколько комбинаций нужно перебрать, чтобы наверняка открыть замок?

5. Чему равен коэффициент при в разложении ?