1.8. Перестановки с повторениями, мультимножества

Задача формулируется следующим образом. Имеются предме-

ты k различных видов. Сколько существует перестановок из пх элементов первого типа, элементов второго типа и т. д., и* элементов Л:-го типа? Рассмотрим, например, мультимножество М= [а, а, а,Ь, Ь, с, d, d, d, d), в котором содержатся 3 элемента а, 2элемента Ь, 1 элемент с и 4 элемента d. Мультимножество — это то же самое, что и множество, но в нем могут содержаться одинаковые элементы. Повторения элементов можно указать и другим способом: М= {3-а.2Ь, \ с.4 d). Таким образом, искомые перестановки с повторениями — это перестановки элементов мультимножества. Если бы мы рассматривали все элементы множества М как

различные, обозначив ихто полу-

чили бы 10! перестановок, но после отбрасывания индексов многие из них оказались бы одинаковыми. Фактически каждая перестановка множества М встретилась бы ровнопоскольку в любой перестановке Миндексы при буквах а можно расставить 3! способами, при Ъ — 2! способами, при с — одним способом, а при d — соответственно 4! способами. Поэтому число перестановок множества Мравно . В применении к общему случаю те же рассуждения показывают, что число перестановок любого мультимножества (перестановки с повторениями) равно полиномиальному коэффициенту

где я = пj + /?2 + ... + "к — общее число элементов.

Перестановки с повторениями имеют тесную связь с сочетаниями. Определим количество этих перестановок следующим образом. Из всех п мест перестановки место занимают элементы первого типа. Выбор мест для них можно сделать способами. Из оставшихся п — щ мест элементы второго типа занимают п2 места, которые можно выбрать С"/п способами. Те же рассуждения показывают, что элементы А>го типа можно расположить в перестановке С* Л п п способами. Согласно правилу прямо-

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

**....."«>-vw,=,v

Задача. Сколько существует различныгх перестановок из букв слова «Уссури»?*

Решение. /(2 v.lj],!p,2c)---—=180

2MMI-2!

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

Подсчитаемчислоразбиенийконечного множества где \S\=n,

на к различныгх подмножеств = S\j S\ и ... иЗк, попарно не пере-

к

секающихся, \%\ щ, i= 1, 2,..., к л =п . Последовательность

щ

последовательность подмножеств. При формировании упорядоченной Sb последовательности на первое место подмножество можно выбрать способами, на второе место подмножество можно выбрать из оставшихся п — щ элементов C"l способами и т. д., на

последнее место множество Sk можно выбрать из оставшихся пк у элементов п п способами. По правилу

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

"л ~~n-n1" п-п1-...-пк 1 и \„ f и i1

"1 .Jt......К

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

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

Замечание 2. Упорядоченные разбиения множества S на попарно непересекающиеся подмножества S2 и ... и Sk = допускают интерпретацию в терминах «корзин» и «шаров». Обозначим элементы исходного множества S \ = п «шарами». Под разбиением исходного множества, теперь множества шаров, на различные S упорядоченные подмножества будем понимать разложение шаров по различным корзинам (упорядоченные

шаров положить в корзину шаров положить в корзину и т. шаров положить в корзину где п1+п2 + ... +пк = п. Как установлено, число таких разложений С"1 С"2 С"к"!

" п-п, " п-п,-...-пи , «л,1

равно

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

может быть проведено такое голосование?

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

iy j 3 25!

таких разложений определяется выражением C2J5 -Cg -С§ =у~- •

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

Подсчитаем, сколькими способами можно разбить множество S, где S = п, на подмножества, среди которых для каждого < == 1, 2;,.., п имеется > О подмножеств с элементами. Тогда верно,

п

что YJ-Щ =п. Данное разбиение позволяет представить исход-f=i

ное множество следующим образом:

7=17=1 i=lj=l

где .Уу попарно не пересекаются и =\Sf\-... = ISim \ =/для каждого / = 1,2,..., п. Порядок подмножеств в разбиении не является существенным. Так, например, разбиения множества2, 3,

4, 5} вида