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

17

{1, 3}, {4}, {25}; {1, 3}, {25}, {4}; {25}, {1, 3}, {4}; {4}, {1, 3}, {25};

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

Обозначим число неупорядоченных разбиений множества S через N{mbm2,..., тп). Рассмотрим схему формирования упорядоченных разбиений для представления п =\-тх +2-т2+... + п-тп:

Воспользуемся интерпретацией формирования упорядочен-

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

различные. Однако при неупорядоченном разложении обмен шарами таких корзин можно рассматривать как соответствующую перестановку указанных корзин, что не приводит к новым разложениям. Если количество корзин с одинаковым числом шаров равно то неупорядоченных разложений будет в меньше, чем упорядоченных. Тогда общее число неупорядоченных разбиений будет в т\\т2\...тп\ раз меньше, чем упорядоченных. Следовательно,

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

Щ б{0,1}.

л!

й!

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

Решение. Требуется разбить множество из 17 человек на непересекающиеся и неупорядоченные группы людей. Откуда искомое число равно N(0 6 03,04,15,06,07,...,0 )= 17!

(2!)6(5!)16!1!

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

Решение. 4 туза можно разбить на JL - = 3 различные коалиции

(2!)22!

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

41 321 3-321

колоду пополам.

V. lb! It)! 11)! Ш

1.11. Полиномиальная формула

Формула

(*, +х1+...+хкГ = х. ,*№ <* о ИД)

называется полиномиальной, где суммирование выполняется по всем решениям уравнения + л2 + + "а = п в целых неотрицательных числах, я, 0, = 1, 2,..., к. Для доказательства выполним умножение

(.v, KV;+.. +.v. )(л-;-t-.v>-h.. +хк)...(х +

Чтобы привести подобные в полученном выражении, необходимо подсчитать количество одночленов видах"1 х"2.. .х"к каждо-

1 2К

го разбиения щ + п2 + ... +пк = п. Для получения же одночлена х"[хп22...х"кк необходимо выбрать щ в качестве множителя в щ

1.12.БиномНьютона 19

скобках при раскрытии выражения (xj + х2 + ... хк)п. Это можно сделать С1 способами. Из оставшихся п — л j не раскрытых скобок необходимо выбрать х2 в качестве множителя в п2 скобках. Это можно сделать Спп1п способами и т. д. Тогда количество одночленов х"1х"1.. .х"к при раскрытии выражения

(х, +х2+...+хк)(х1 + х2+...+хк)...(х{ +х2+...+хк)

п

Сбудет равно числу Qс- ...С\ , --- — упорядо-

1 i. " к

ченных разбиений.

1.12. Бином Ньютона

Частный вид полиномиальной формулы (1.11.1):

ia + Ь)" =ТС,какЬ"-(1.12.1)

называется биномом Ньютона.

Рассмотрим несколько задач, в основе решения которых лежит бином Ньютона.

п

Задача 1. Доказать тождество £с* =2".

Ш

Решение. Воспользуемся формулой (1.12.1) бинома Ньютона,

в которой положим а = 1 и Ъ = 1, тогда (1+1)" = УСк -1* -1"-*.

(И

и

Задача 2. Доказать тождество £С* (/и-1)"-*= /и".

Решение. Воспользуемся формулой (1.12.1), где положим а = 1 иЬ=т — 1.

111 ги

Задача 3. Доказать тождество YCn = £ с« =2 *

Решение. Воспользуемся формулой (1.12.1), в которой положим а=1и* = тогда 0-1)" = У(-1>А С* =0. Группируя положите-

льные и отрицательные члены равенства, установим