1.10. Неупорядоченные разбиения множества

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

где попарно не пересекаются и каждого Порядок подмножеств в разбиении не является существенным. Так, например, разбиения множества вида

считаются одинаковыми.

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

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

Заметим еще раз, что если выполнено упорядоченное разбиение числа на подмножества различной длины (мощности), то они совпадают с неупорядоченными разбиениями. В этом случае все

Задача. Сколькими способами из группы в 17 человек можно сформировать 6 коалиций по 2 человека и 1 коалицию из 5 человек?

Решение. Требуется разбить множество из 17 человек на непересекающиеся и неупорядоченные группы людей. Откуда искомое число равно

Задача. Сколькими способами можно разделить колоду из 36 карт пополам так, чтобы в каждой пачке было по два туза?

Решение. 4 туза можно разбить на различные коалиции по две карты в каждой (неупорядоченные разбиения), т.е. только 3 способами можно разделить тузы пополам. Далее, каждая половина любого из этих трех разбиений тузов выполняет роль различных двух «корзин», куда необходимо разложить пополам оставшиеся 32 карты. Разложение 32 оставшихся карт уже будет упорядоченным, так как «корзины» различные, число разложений равно Согласно правилу прямого произведения, общее число вариантов разделить колоду пополам равно