Разбиения. Пусть М – множество мощности n, {M1,M2,,Mk} – разбиение множества М на k подмножеств, |Mi| = mi, m1 + m2 +

Пусть М – множество мощности n, {M₁,M₂,...,M_k} – разбиение множества М на k подмножеств, |M_i| = m_i, m₁ + m₂ +... + m_k = n. Кортеж (M_1,…,M_k) называется упорядоченным разбиением множества М.

Число разбиений R(m₁,m₂) равно С_n^m1 = С_n^m2. Таким образом,

Число R(n,k) упорядоченных разбиений на k подмножеств вычисляется по формуле

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

Пример: Сколькими способами из группы в 25 человек можно сформировать 5 коалиций по 5 человек?

Пусть Х – множество людей в группе, m_i – число коалиций по i человек, где i = 1,…,25. Тогда по условиям задачи |М| = 25, m₅ = 5, m_i =0, i {1,2,…,25} \ {5}, и, следовательно, искомое число будет равно