Разбиения множеств

Пусть [math]\displaystyle{ S = \{s_1, s_2, ..., s_m\} }[/math] — произвольное множество из $m$ элементов.

Рассмотрим такие разбиения множества $S$ на подмножества $S_1, S_2, ..., S_k$, что каждое $S_i$ содержит $\alpha_i$ элементов.

Очевидно, что $m = \alpha_1+\alpha_2 + ... + \alpha_k$. Отметим, что некоторые $S_i$ могут быть пустыми, если соответствующее $\alpha_i=0$.

Пусть $S$ — множество мощности $m$. Пусть $\alpha_i$ — известные неотрицательные целые числа, $i=\overline{1,k}$, и $m = \alpha_1+\alpha_2 + ... + \alpha_k$. Число разбиений множества $S$ на $k$ подмножеств: $S=S_1\cup S_2\cup ...\cup S_k; S_i\cap S_j=\varnothing, i \neq j; |S_i|=\alpha_i, i=\overline{1,k}$, равно мультиномиальному коэффициенту $\binom{m}{\alpha_1, \alpha_2, ..., \alpha_k}$.

Выберем элементы для множества $S_1$. Это можно сделать $\binom{m}{\alpha_1}$ способами.

Далее, независимо от того, какие элементы мы выбрали для множества $S_1$, существует ровно $\binom{m-\alpha_1}{\alpha_2}$ способов выбрать элементы для множества $S_2$, $\binom{m-\alpha_1-\alpha_2}{\alpha_3}$ — для множества $S_3$, и так далее.

Поскольку количество вариантов выбора элементов для каждого множества не зависит от того, какие элементы выбраны для предыдущих, мы можем перемножить эти числа, чтобы получить общее количество различных разбиений, удовлетворяющих нашим условиям: $\binom{m}{\alpha_1} \cdot \binom{m-\alpha_1}{\alpha_2}\cdot \binom{m-\alpha_1 - \alpha_2}{\alpha_3} \cdot ... \cdot \binom{m-\alpha_1 - ... - \alpha_{k-1}}{\alpha_k}= $ $= \frac{m!}{\alpha_1!(m-\alpha_1)!}\cdot \frac{(m-\alpha_1)!}{\alpha_2!(m-\alpha_1-\alpha_2)!}\cdot \frac{(m-\alpha_1 - \alpha_2)!}{\alpha_3!(m-\alpha_1-\alpha_2-\alpha_3)!}\cdot \frac{(m-\alpha_1-\alpha_2-...-\alpha_{k-1})!} {\alpha_k!(m-\alpha_1-\alpha_2-...-\alpha_{k-1}-\alpha_k)!}=$ $\frac{m!}{\alpha_1!\alpha_2!...\alpha_k!} = \binom{m}{\alpha_1, \alpha_2, ..., \alpha_k}$.

Пусть имеется $m$ шаров с различными номерами на них и имеется $k$ коробок: $B_1$, $B_2$, ..., $B_k$. Сколькими способами можно разложить эти $m$ шаров по $k$ коробкам таким образом, чтобы в коробке $B_i$ оказалось ровно $\alpha_i$ шаров, $i=\overline{1,k}$? Согласно утверждению это можно сделать $\binom{m}{\alpha_1, \alpha_2, ..., \alpha_k}$ способами.

Итак, в комбинаторном смысле мультиномиальный коэффициент $\binom{m}{\alpha_1, \alpha_2, ..., \alpha_k}$ равен числу упорядоченных разбиений $m$-элементного множества на $k$ подмножеств мощностей $\alpha_1$, $\alpha_2$, ..., $\alpha_k$ соответственно.

Рис. 1. Четыре элемента раскладываются по трём различимым частям размерами [math]\displaystyle{ 2 }[/math], [math]\displaystyle{ 1 }[/math], [math]\displaystyle{ 1 }[/math]. Число способов равно [math]\displaystyle{ C(4,2)\cdot C(2,1)\cdot C(1,1)=12=4!/(2!1!1!) }[/math].

В студенческой группе, состоящей из 25 человек, при выборе профорга за выбранную кандидатуру проголосовало 12 человек, против — 10, воздержалось — 3. Сколькими способами могло быть проведено такое голосование? Пусть $S$ — множество студентов группы, $S_1$ — множество студентов, проголосовавших за выдвинутую кандидатуру, $S_2$ — множество проголосовавших против, $S_3$ — множество воздержавшихся. Тогда $|S| = 25$, $|S_1| = 12$, $|S_2| = 10$, $|S_3| = 3$, $S = S_1\cup S_2\cup S_3$, $S_i\cap S_j=\varnothing$, $i\neq j$. Следовательно, искомое число равно $\binom{25}{12,10,3} = \frac{25!}{12!10!3!} = 1 487 285 800.$

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

Пусть дано множество $S$ мощности $m$ и числа $n_1$, $n_2$, ..., $n_m$ таковы, что $\sum_{i=1}^{m} n_i \cdot i = m$. Рассмотрим такие разбиения множества $S$ на подмножества, что среди множеств разбиения ровно $n_i$ множеств мощности $i$ для каждого $i=\overline{1,m}$, причем порядок множеств разбиения не важен. Обозначим число таких разбиений за $N_m(n_1, n_2, ..., n_m)$.

Замечание. По сути вектор $n_i$ задает тут мультимножество на множестве $S$ мощности $k$, где $k$ — число подмножеств в разбиении.

Пусть $m\in\mathbb{N}$ и $n_1, n_2, ..., n_m\in \mathbb{N}_0$ — такие числа, что $\sum_{i=1}^{m} n_i \cdot i = m$. Тогда $N_m(n_1, n_2, ..., n_m)=\frac{m!}{n_1! n_2! \cdots n_m! (1!)^{n_1} (2!)^{n_2}\cdots (m!)^{n_m}}$.

Каждое неупорядоченное разбиение, заданное числами $n_1, ..., n_m$ в условиях выше,можно упорядочить, расставив подмножества по возрастанию мощности и как-нибудь упорядочив подмножества одинаковой мощности. Подсчитаем, сколькими способами это можно сделать.

Множества мощности $1$ можно расставить $n_1!$ способами, множества мощности $2$ — $n_2!$ способами, и так далее до множеств мощности $m$. Таким образом, каждому неупорядоченному разбиению из условий этого утверждения можно однозначно сопоставить набор из $n_1! n_2! \cdot ... \cdot n_m!$ упорядоченных разбиений, заданных вектором $(\alpha_1, ..., \alpha_k) = ( \underbrace{1,...,1}_{n_1}, \underbrace{2,...,2}_{n_2}, ... \underbrace{m,...,m}_{n_m} ) $

Таким образом, каждому из $N_m(n_1,...,n_m)$ неупорядоченных разбиений сопоставлены ровно $n_1! n_2! \cdot ... \cdot n_m!$ упорядоченных разбиений из утверждения \ref{claim:04_multi_coeff_combin}. То есть упорядоченных разбиений в $n_1! n_2! \cdot ... \cdot n_m!$ раз больше и можно записать $N_m(n_1, n_2, ..., n_m) \cdot n_1! n_2! \cdot ... \cdot n_m! = \frac{m!}{(1!)^{n_1}, (2!)^{n_2},..., (m!)^{n_m}}$, или $N_m(n_1, n_2, ..., n_m) = \frac{m!}{(1!)^{n_1}, (2!)^{n_2},..., (m!)^{n_m}\cdot n_1! n_2! \cdot ... \cdot n_m!}$.

Сколькими способами можно разбить множество из десяти элементов на четыре подмножества (порядок подмножеств не важен), чтобы в одном из подмножеств был один элемент, в двух — по два элемента и в одном — пять элементов? Ответ: $N_{10} (1,2,0,0,1,0,0,0,0,0) = \frac{10!} {1! 2! 1! (1!)^1 (2!)^2 (5!)^1 } = \frac{10!}{2\cdot 4\cdot 5!} = 3780 $

Сколькими способами из группы в 20 человек можно сформировать 4 коалиции по 5 человек? Пусть $S$ множество людей в группе, $n_i$ — число коалиций по $i$ человек, $i=\overline{1,20}$. Тогда ответ: $N_{20}(0,0,0,0,4,0,...,0) = \frac{20!}{4!(5!)^4}$

Конспект: Дискретная математика