Дискретная математика

109 § 5. Число всевозможных разбиений конечного множества. Полиномиальная теорема Пусть А множество с п элементами и подмножества В;, В2>.:, Вь (Sj сг А, 1^ г < k) образуют разбиение множества А, т.е. l<i<k; B,nBj=0, если i A=BjuB2U...uBk- Положим, что подмножество 5,- содержит и,- элементов, 1.2" iS к. При этом считаем, что В;, В/. - упорядоченная последовательность подмножеств. Выясним, сколькими способа.ми можно осуществить разбиение ^ на подмножества Й;,В2,...,В4 так, чтобы n{Bi)=ni, ]<i<k. Выбор подмножества В; с щ элементами из п элементного множества А молено осуществить способами. Выбор подмножества из оставшегося множества можно осуществить способами и т. д. Подмножество можно, очевидно, выбрать способами. Ы1 Применяя теперь обобщенное правило произведения, получим, что искомое число разбиений множества Л равно Р(п,п^,п2,...,пк)'^с1' = — — — '••• ' ni!(n-n,)! п2!(п-п, -Пт)! ^ г1,!п2!...Пк! Р(П,П/,П2,.-.,Пк)-- м Итак, имеем: Используя полученн}™ формулу, легко доказать следующее равенство, которое называется полиномиальной теорелюй'. {х,+Х,+ ...+Хк)"^ S nj>0.Ti2^0 „ , п}^ fij+n2-r =fi Рассмотрим два примера, 1. Сколькими способами можно поселить 10 студентов в три комнаты: 5- местную, 3- и 2- местные? Число вариантов