Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 98
Текст из файла (страница 98)
Найдите производящую функцию, которая используется для нахождения количества способов разложения к различных типов шоколадок в 6 коробок, если в первую коробку помещать четное количество шоколадок, во вторую— нечетное количество, не менее 3 шоколадок помещать в третью коробку, не более 3 — в четвертую коробку и любое их количество — в оставшиеся две коробки. 9.
Подбрасывание к игральных кубиков дает в сумме и. Используйте производящую функцию для определения количества способов подбрасывания. 10. Найдите коэффициент при хт в разложении производящей функции ~гх)=(х+х +х ) . 11. Найдите коэффициент при х1о в разложении производящей функции 12. Найдите коэффициент при хгт в разложении производящей функции х4 Пх) = 13. Найдите коэффициент при х'е в разложении производящей функции 4 7( ) 1 .5 14.
Найдите коэффициент при хго в разложении производящей функции дх)=(х +х +хе+ ). 15. Найдите коэффициент при х'г в разложении производящей функции 1(х) =(х +х +х + ) . 16. Найдите коэффициент при х~о в разложении производящей функции ~(х) = (х +х +х + х )(х+х +х' ). 17. Найдите коэффициент при х'г в разложении производящей функции г"(х) = 2х+ хг 18. Найдите коэффициент при х'г в разложении производящей функции хз Зхг Х(х) = (1 )4 542 ГЛАВА 13. Производящие функции !9. Найдите коэффициент при хга в разложении 1(х) = (1 — Зх) 4.
20. Найдите коэффициент при хга в разложении производящей функции 1 (1 .3)4 21. Используйте производящую функцию для нахождения количества способов выбора 10 шаров из 20 красных, 20 белых и 20 синих шаров, если а) следует выбрать не менее одного шара каждого цвета; б) следует выбрать четное количество красных шаров и четное количество синих шаров. 22. Используя производящую функцию, определите, сколько существует способов распределения 15 игрушек между 5 детьми, если ни один ребенок не может получить более 4 игрушек? 23.
Используя производящую функцию, определите, сколькими способами можно разложить в коробки шестнадцать конфет, если имеется 4 вида конфет и нужно выбирать не более 4 конфет каждого из первых трех видов. 24. Используя производящую функцию, определите, сколько имеется способов раскладывания 16 одинаковых предметов в 5 различных ящиков, если каждый ящик может содержать не менее 2 и не более 6 предметов? 25.
Пусть л (х) — производящая функция, коэффициенты которой являются числами Фибоначчи. Используя рекуррентное отношение для Р(х), покажите, что с'(х) = (1 — (х+ ха)) Используя это выражение, постройте разложение производящей функции х (х). Покажите, что коэффициент при х"к ' равен поэтому Фиб(п+1) = + + +...
13.4. РАЗБИЕНИЯ В этом разделе при помощи производящих функций описывается число распределений множества, содержащего п неразличимых объектов, по заданному числу неразличимых ящиков. Это эквивалентно описанию количества способов разбиения положительного целого числа и на группы, содержащие заданное количество положительных целых чисел, сумма которых равна и; при этом группы, которые отличаются только порядком элементов, являются неразличимыми. Если противное не оговорено, то под числом в этом разделе мы будем подразумевать положительное целое число.
РАДЕЛ 13.4. Разбиения 543 Например, число 3 можно выразить как сумму 1+1+1 и как 1+2. Число 4 можно выразить как 1+1+1+1, 1+1+2, 1+3, 2+2 и 4. Способы выражения числа 4 в виде суммы двух чисел сводятся к 1+ 3 и 2+ 2. Таких способов два, поэтому существует два способа разложить 4 неразличимых объекта по двум неразличимым ящикам так, чтобы ни один ящик не был пустым. Способы выражения числа 4 в виде суммы двух или менее чисел таковы; 1+ 3, 2+ 2 и 4. Таких способов три, поэтому существует три способа разложить 4 неразличимых объекта по 2 неразличимым ящикам, так что некоторые из этих ящиков могут быть пустыми. Сначала рассмотрим количество способов, благодаря которым п неразличимых объектов раскладывается по п ящикам при условии, что некоторые ящики могут быть пустыми.
Это то же самое, что искать число способов разбиения числа и на группы из и или менее чисел, сумма которых равна и. Последнее представляет собой число неотрицательных целочисленных решений уравнения ег + 2ег + Зез + + пе„ = и. Если и фиксировано, то количество решений находится как коэффициент при х" в разложении производящей функции (1 — х)(1 — хг)(1 — хз) . (1 — х") Последний пример предыдущего раздела показывает, что количество решений эквивалентно нахождению количества способов выбора и объектов при условии, что объекты первого типа выбираются по одному, объекты второго типа— по два, объекты третьего типа — по три и т.д. Именно это то мы и делаем, поскольку каждая выбранная единица вносит в сумму показателей степеней 1, и эти единицы суммируются вплоть до и ах"; каждая выбранная двойка вносит в сумму степеней 2, и эти двойки суммируются вплоть до и и т.д. По мере увеличения п требуется все больше членов в произведении.
Поскольку мы хотим, чтобы наша производящая функция описывала число решений для всех п, то искомая производящая функция имеет вид (1 — хИ1 — хгИ1 — хз) (1 — х") .. в результате приходим к следующей теореме. ТЕОРЕМА 13.14. Производящая функция, и-ый коэффициент которой равен количеству способов, которыми можно разложить п неразличимых объектов по и ящикам при условии, что некоторые ящики могут быть пустыми, или, что эквивалентно, равен количеству разбиений числа и на группы, содержащие и или менее чисел, сумма которых равна и, имеет вид г1 И1 .ги1 .з) г1 .ь) ПРИМЕР 13.15.
Покажем, что любое число можно выразить следующим образом 2о + 2' + 2г + 2з + ... + 2" 644 ГЛАВА 13. Производящие функции Из данного выражения следует, что любое число можно записать в двоичной системе счисления, что является весьма важным моментом при использовании целых чисел в компьютерных приложениях. (а) Убедимся сначала, что для всех и (1 — х)(1 + х)(1 + х') (1 + х' ) " = (1 — хз" И1+ а" Н1+ 3"+'И1+ 2" '), Используем метод индукции по п. Вполне очевидно, что утверждение справедливо при п = О.
Предположим, что оно выполняется для п = к, так что (1 — х)(1+х)(1+х ) (1+х~ ) . = (1 — х~ )(1+х~ )(1+х~ )(1+х~ ) но (1-*'"Н1+*'") = (1- х'"") Отсюда (1 — х)(1+ х)(1+ х ) (1+ х ) = (1 — хз 'Н1+ хз" ')(1+ хз"") поэтому утверждение справедливо для п = й+ 1 и для всех и. (б) Покажем далее, что (1 — х)(1+х)(1+ ха). (1 — хз ) .. = 1. Согласно части (а) для любого й > 1 в левой части равенства коэффициент при х" равен О. Поэтому производящая функция 1+ Ох + Охз +. = 1. (в) Согласно части (б) получаем, что (1+х)(1+х ) (1+х ) = = 1+х+х +х + (г) Левая часть равенства в части (в) есть производящая функция последовательности, состоящей из степеней числа 2, где каждая степень появляется только раз.
Правая часть равенства представляет собой производящую функцию множества всех положительных целых чисел. Следовательно, любое число есть сумма степеней числа 2. П ПРИМЕР 13.16. Рассмотрим количество способов разбиения числа и на группы, содержащие и или менее различных чисел. Таким образом, каждое число может войти в заданную сумму только один раз. Например, число 4 можно представить либо как 4, либо как 1+ 3.
В каждом представлении числа и в виде суммы различных чисел любое число, меньшее или равное п, может входить в сумму или не входить. Поэтому производящая функция имеет вид (1+ х)(1 + хз)(1 + хз) (1 + хь) ПРИМЕР 13.17. Количество способов разбиения числа и на группы, содержащие п или менее различных чисел, равно количеству способов разбиения числа и на группы, содержащие и или менее нечетных чисел, сумма которых равна и. РАЗДЕЛ 13.4. Разбоения 545 Сначала найдем производящую функцию, при помощи которой сможем определить количество способов разбиения числа п на группы, содержащие и или менее нечетных чисел, сумма которых равна и. Исходя из теоремы 13.14, находим, что производящая функция имеет вид (1 — х)(1 — хз)(1 — хз) . (1 — хз" ').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
