Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 99
Текст из файла (страница 99)
Из предыдущего примера следует, что производящая функция, используемая для нахождения количества способов разбиения числа и на группы, содержащие и или менее различных чисел, имеет вид (1+ х)(1+ х')(1+ х') ". (1+ х") . Но гь (1+ х~) = так что (1 + х)(1 + х )(1 + х ) (1 + х ) 1 — х 1 — х 1 — х 1 — х 1 — х г 4 б в ш 1 — х 1 — хз 1 — хз 1 — ха 1 — ха Но к-ый член в числителе сокращается с 2Й-ым членом в знаменателе, а в зна- менателе остается только (2й + 1)-ый член.
Поэтому имеем (1 + х)(1 + х )(1 + х ) (1 + х ) г з ь что является производящей функцией, используемой для определения количества способов разбиения числа п на группы, содержащие и или менее нечетных чисел, сумма которых равна и. П Следующая цель — описать количество способов разложения п неразличимых предметов по к неразличимым ящикам. Для этого понадобится простой, но удобный метод, состоящий в использовании так называемых диаграмм Ферре. Будем использовать одну из модифицикаций этого метода, где простоте отдается предпочтение над строгим алгебраическим описанием.
В данной версии начнем с описания распределения предметов по ящикам, используя строки возрастающей длины. Например, распределение 12 предметов по 4 ящикам можно изобразить так, как показано на рис. !3.1. ° ° ° ° ° ° ° ° ° ° ° Рис. 13.1 546 ГЛАВА 13. Производящие функции Если судить по строкам, то видно, что в первый ящик помещен 1 предмет, во второй — 3 предмета, в третий ящик — 4 предмета и в четвертый — 4 предмета.
Если же судить по столбцам, то в первом ящике находится 4 предмета, во втором — 3 предмета, в третьем — 3 предмета и в четвертом — два предмета. В столбцах ящики расположены в порядке убывания их размера. Но это несущественно, т.к. ящики неразличимы. В частности, легко заметить, что каждому распределению по строкам соответствует некоторое распределение по столбцам, и наоборот. Следовательно, существует взаимно однозначное соответствие между распределениями по строкам, содержащим ящики возрастающего размера, и распределениями по столбцам, содержащим ящики уменьшающегося размера. Рассмотрим произвольное распределение 12 предметов по 4-м ящикам. Допустим, что в первом ящике — 1 предмет, во втором — 2 предмета, 4 предмета — в третьем ящике и 6 предметов — в четвертом ящике.
Соответствующая диаграмма Ферре приведена на рис. 13.2. ° ° ° ° ° ° ° ° че ° ° ° Рис. /3.2 Если теперь посмотреть на распределение предметов по столбцам, то можно увидеть, что в первом ящике находятся 4 предмета, во втором ящике — 3 предмета, в третьем и четвертом ящиках — по 2 предмета и по 1 предмету — в пятом и шестом ящиках. Однако, поскольку в распределении по строкам с самого начала использовались 4 ящика, то в распределении по столбцам нельзя поместить в каждый ящик более 4 предметов.
И наоборот, если в распределении по столбцам класть в каждый ящик не более 4-х предметов, то при переходе к строкам понадобятся не более четырех ящиков. Более того, в распределении по строкам 4 непустых ящика будут только тогда, когда в распределении по столбцам будет один ящик, содержащий в точности 4 предмета. Таким образом, существует взаимно однозначное соответствие между распределениями 12 предметов по 4 ящикам, где некоторые пусты, и такими распределениями 12 предметов, когда в каждом ящике находятся не более 4 предметов.
Кроме того, существует взаимно однозначное соответствие между распределениями 12 предметов по 4 ящикам, при которых в каждый ящик попадает хотя бы один предмет, и такими распределениями 12 предметов, при которых хотя бы 1 ящик содержит 4 предмета. Такие же рассуждения с и предметами и Й ящиками приводят к следующей теореме. ТЕОРЕМА 13.18. Количество способов размещения и предметов в к ящиках при условии, что некоторые ящики могут быть пустыми, равно количеству размещений и предметов по ящикам при условии, что в каждом ящике будет находится не более й предметов.
Кроме того, количество способов размещения зз предметов в 1с ящиках, где ни один ящик не может быть пустым, равно количеству размещений и предметов по ящикам при условии, что в каждом ящике может находиться не более й предметов и хотя бы один ящик содержит к предметов. РАЗДЕЛ 13.4. Разбиения 547 ег + 2ез + Зез + .
+ Йеь = и, то производящая функция имеет вид (1+з+х + )(1+х +х + ..)(1+х +з + ) . (1+к +з + ) или 1 1 1 1 1 — х 1 †1 †1 — з" ТЕОРЕМА 13.20. Производящая функция, описывающая количество способов разбиения числа п на группы из Й или менее неотрицательных целых чисел, имееет вид (1+х+х + ..)(1+к +х +.. )(1+т +х + ..) (1+х +х + ) или 1 1 1 1 — х" з 1,з Теперь сформулируем эквивалентную неразличимых объектов. ТЕОРЕМА 13.21.
Производящая функция, размещения и неразличимых объектов по Й из ящиков пустые, имеет вид теорему в терминах распределения описывающая количество способов ящикам при условии, что некоторые (1 Ч 2 Ч )(1 2 4 )(1 3 В ) (1 ь 2ь ) 1 1 1 1 или 1 — х" .г 1 з Теперь рассмотрим случай с количеством способов разбиения числа п на группы из Й чисел, сумма которых равна и. По теореме 13.19 это есть количество способов разбиения числа п на группы из п или менее неотрицательных целых чисел, когда наибольшее число в каждой группе равно Й. В этом случае производящая функция имеет вид (1+л+х +. )(1+к +х +.
)(1+к +х + ) ° (х +х™+ ), Сформулируем эквивалентную теорему в терминах разбиений числа п. ТЕОРЕМА 13.19. Количество способов разбиения числа и на группы, содержащие Й или менее чисел, равно количеству способов разбиения числа и на группы, содержащие и или менее чисел, при которых ни одно число из группы не превышает Й. Кроме того, количество способов разбиения числа п на группы, содержащие ровно Й чисел, равно количеству способов разбиения числа и на группы, содержащие и или менее неотрицательных целых чисел, когда наибольшее число в каждой группе равно Й.
Поскольку количество способов разбиения числа и на группы, содержащие и или менее чисел при условии, что никакое число в группе не превышает Й, равно количеству неотрицательных целочисленных решений уравнения 548 ГЛАВА 13. Лроиэеооящие функции что равно хь(1+х+х + )(1+х +хе+ )(1«-хз+х + ) г1+х+хгк+ ) или г1 .И1 .гИ1 .з)... г1 к) Этот результат можно получить иначе, воспользовавшись производящей функ цией, описывающей количество способов разбиения числа и на группы из к или менее чисел, сумма которых равна п, и вычесть из нее производящую функцию, описывающую количество способов разбиения числа и на группы из к — 1 или менее чисел, сумма которых равна п. В результате получим производящую функцию, где число п разбито на группы, содержащие ровно и чисел, сумма которых равна и.
Исходя из вышеизложенного, имеем (1+х+х +. -)(1+х +х +. ) (1+х +х 1 1+ ..)(1+х -~-х + . ) = -(1+х+х + )(1+х +х + ). ~1+ ь-г + г<ь-Ы + = (1+х+хг+ )(1+хг+х4+ ) (1+ хк г + хг~ь г1 Ч- .. )И1+ хь + хгь + ) — 1) = (1+х+х +...)(1+х +х +...) (1+ хь-1 + ха(/с-1) +... )Их/с + хай + ) Таким образом, мы получили следующую теорему. ТЕОРЕМА 13.22. Производящая функция, описывающая количество способов разбиения числа и на группы, содержащие ровно к неотрицательных целых чисел, сумма которых равна и, имеет вид х (1+х+х + )(1+х +х + .И1+х +х + ). (1+х+х + ) или х (1 — х)(1 — хг)(1 — хз) . (1 — х") Следующая теорема содержит равносильное утверждение.
ТЕОРЕМА 13.23. Производящая функция, описывающая количество способов размещения и неразличимых предметов в к ящиках таким образом, что никакой из ящиков не будет пустым, равна х (1+х+х +. )(1+х +х +. И1+х +х +..) .(1+х +х + . ) или (1 хп1 хгн1-хз)...(1 хь) РЯЗДЕЛ 13.5. Экспоненциальные производящие функции 649 ° УПРАЖНЕНИЯ 1. Найдите количество разбиений числа 7. 2. Найдите количество разбиений числа 5. 3. Найдите производящую функцию, описывающую количество способов размещения 10 неразличимых объектов в 6 неразличимых ящиках. 4. Найдите производящую функцию, описывающую количество способов разбиения числа п на различные нечетные числа. 5.
Найдите производящую функцию, описывающую количество способов разбиения числа и на различные четные числа. 6. Предположим, что атлет участвует в соревнованиях по 3 видам спорта. В каждом из состязаний он может выиграть 1, 2, 3, 4 или 5 очков. Найдите производящую функцию, показывающую, сколько существует различных способов набрать п очков. 7.
При помощи диаграммы Ферре покажите, что количество разбиений числа на четные части равно количеству разбиений этого числа на части так, что каждая часть присутствует четное количество раз. 8. При помощи диаграммы Ферре покажите, что количество разбиений числа и на 3 части равно количеству разбиений числа 2и на 3 части меньшего размера, чем п. Что можно сказать о количестве разбиений числа и на 4 части и числа Зп на 4 части меньшего размера, чем и? Можно ли это утверждение обобщить? 9. При помощи диаграммы Ферре покажите, что число разбиений числа и равно количеству разбиений числа 2п на и частей. 10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
