§ 5. Число всевозможных разбиений конечного множества. Полиномиальная теорема

Пусть А множество с n элементами и подмножества $B_1,B_2,...,B_k (B_i⊂A, 1≤i≤k)$образуют разбиение множества А, т.е.

Вi≠∅, 1≤ i≤ k;

Вi∩Вj=∅, если i ≠ j;

А=В1∪В2∪…∪Вk.

Положим, что подмножество Вi содержит ni элементов, 1≤ i≤ k. При этом считаем, что В1, В2,…, Вk – упорядоченная последовательность подмножеств. Выясним, сколькими способами можно осуществить разбиение А на подмножества В1,В2,…,Вk так, чтобы n(Вi)=ni, 1≤ i≤ k.

Выбор подмножества В1 с n1 элементами из n элементного множества А можно осуществить $C_n^{n1}$ способами.

Выбор подмножества В2 из оставшегося множества можно осуществить $C_{n-n1}^{n2}$ способами и т. д.

Подмножество Вk можно, очевидно, выбрать $C_{n-\sum_{i=1}^{k-1}n_j}^{n_k}$

Применяя теперь обобщенное правило произведения, получим, что искомое число разбиений множества А равно

$P(n,n_1,n_2,...,n_k)=$ $C_n^{n1}C_{n-n1}^{n2}...C_{n-\sum_{i=1}^{k-1}n_j}^{nk}=$ $\frac{n!}{n_1!(n-n_1)!} \frac{n-n_1}{n_2!(n-n_1-n_2)!}...$ $...\frac{(n-\sum_{i=1}^{k-1}n_i)!}{n_k(n-\sum_{i=1}^{k}n_i)!}$=$\frac{n!}{n_1!n_2!...n_k!}$

Итак, имеем:

$P(n,n_1,n_2,...,n_k)=$ $\frac{n!}{n_1!n_2!...n_k!}$

Используя полученную формулу, легко доказать следующее равенство, которое называется полиномиальной теоремой:

$(x_1+x_2+...+x_k)^n = \sum{n!}{n_1!n_2!...n_k!}x_1^{n1} x_2^{n2} ... x_k^{nk}$

Рассмотрим два примера. 1. Сколькими способами можно поселить 10 студентов в три комнаты: 5- местную, 3- и 2- местные? Число вариантов поселения, как легко видеть, равно числу возможных разбиений 10 - элементного множества на подмножества с 5, 3 и с 2 элементами. Следовательно, искомое число равно:

$P(10,5,3,2) = \frac{10!}{5!3!2!} = \frac{6⋅7⋅8⋅9⋅10}{2⋅3⋅2} = 2520$

2. Чему равно число различных расположений пяти букв А,А,В,В,В? Это число определяем, как число возможных разбиений 5-ти элементного множества на подмножества с 2 и с 3 элементами. Следовательно, искомое число равно:

$P(5,3,2)=\frac{5!}{3!2!}=10$