1.9. Упорядоченные разбиения множества

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

что совпадает с числом перестановок с повторениями.

Замечание 1. Установим взаимно однозначное соответствие между упорядоченными разбиениями множества и перестановками с повторениями. Каждой перестановке с повторениями можно поставить в соответствие упорядоченное разбиение множества номеров элементов в перестановке на подмножества где множество номеров элементов типа в перестановке. Очевидно, что данное соответствие между перестановками с повторениями и разбиениями является взаимно однозначным.

Замечание 2. Упорядоченные разбиения множества на попарно непересекающиеся подмножества допускают интерпретацию в терминах «корзин» и «шаров». Обозначим элементы исходного множества «шарами». Под разбиением исходного множества, теперь множества шаров, на различные упорядоченные подмножества будем понимать разложение шаров по k различным корзинам (упорядоченные подмножества): шаров положить в корзину шаров положить в корзину шаров положить в корзину где Как установлено, число таких разложений равно

Задача. В студенческой группе, состоящей из 25 человек, при выборе старосты за выдвинутую кандидатуру проголосовали 19 человек, против — 3, воздержались — 3. Сколькими способами может быть проведено такое голосование?

Решение. Имеем три различные корзины: «за», «против», «воздержались», в которые необходимо разложить 25 шаров, соответственно 19 — в первую, 3 — во вторую, 3 — в третью. Количество таких разложений определяется выражением