Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 100
Текст из файла (страница 100)
При помощи диаграммы Ферре покажите, что число разбиений числа 2п+ й на и+ й частей одинаково для всех й. 11. Пусть несчастные случаи классифицированы в соответствии с днем недели, в который они произошли. Найдите производящую функцию, описывающую количество различных способов, которыми можно классифицировать и несчастных случаев.
13.5. ЭКСПОНЕНЦИАЛЬНЫЕ ПРОИЗВОДЯЩИЕ ФУНКЦИИ В данном разделе будут использованы производящие функции вида х хз хз х" ао+а,— +аз — +аз — + +а„—. 1! 2! 3! "п) Для начала положим х хз хз х4 х х 1! 2! 3! 4! 5! 6! Единственное свойство этой функции, которое нам понадобится, сформулировано в следующей теореме. Ее доказательство мы предоставляем читателю. ТЕОРЕМА 13.24. Для любого неотрицательного числа и справедливо (е*)" = е"*.
550 ГЛАВА 13. Произвооясцие функции Известно, что (1 + х)" = + х + х + ° + х", поэтому при использовании обычных производящих функций (1 + х)" является производящей функцией для числа сочетаний. Однако, (1 + х)" = + х + хг + + х" и.' и! п) + х+ х О! !п)! 11(п — 1)! 2!(и — 2)! и! и! х и! ха = — + + — + п! (и — 1)! 1! (и — 2)! 2! х хг = Р(п,О) + Р(п, 1) —, + Р(п,2) —, +. )с!1п — lс)1 01(п)! п! хь и! хо + — + +— (и — 1с)! к! О! и! .ь я + Р(п, 1с) — + + Р!п, п) —, й! ' и1 ' 12! 2!3!4!2! ' выражающее количество способов перегруппировки 2к, Зз, 4б и Зс.
Заметим, что, если вместо использования приведенного выше произведения производящих функций использовать 1+-,+ —,+ " —,+ — *, + — *,+ 1+-*,+ — *, +" — *, + — *, +, +... то вместо хгхзхсхз, как одного из сомножителей, дающих х'г, можно получить хг хз х4 хз хгг хзг 2! 3! 4! 3! 2!3!4!2! 2!3!4!2! 12! так что (1+ х)" является экспоненциальной производящей функцией, описывающей количество перестановок. Итак, коэффициенты экспоненциальной производящей функции не равны количеству сочетаний, как в случае обычной производящей функции, а равны количеству перестановок. Теперь переходим к подсчетам объектов с учетом их порядка.
Предположим, что имеется неограниченное количество красных, зеленых, белых и синих предметов. Известно, что производящая функция, описывающая количество способов выбора п предметов при условии, что необходимо выбрать хотя бы 2 зеленых и 3 синих предмета, имеет вид (1+х+х + )(х +х +х + )(1+х+х + .)(х +х +х + ). Например, если выбираются 12 предметов, то хгхзхсхз описывает выбор 2 красных, 3 зеленых, 4 белых и 3 синих предметов. Предположим, однако, что выбираются не красные, зеленые, белые и синие предметы, а буквы к, з, б и с, и спрашивается, сколько слов можно из них составить.
Нам нужно получить не один из возможных результатов — 2 к, Зз, 4 б и 3 с, а число РАЗДЕЛ 13.6 Экспоненциепьные произеоояитие функции 661 Коэффициент при — *,, равен ~зф4,з,. Таким образом, если требуется количество способов, которыми можно переупорядочить предметы, а не выбрать их, то вместо обычных производящих функций необходимо использовать экспоненциальные производящие функции. При использовании обычных производящих функций коэффициент при х" даст общее количество способов, которыми можно выбрать и предметов.
Если использовать экспоненциальную производящую функцию, то коэффициент при *— „, даст количество способов, которыми и предметов можно выбрать и переупорядочить. Напомним, что в разделе 8.6 приводилось равенство и Р(и; ты тз,, ть) = = С(и; т„тз,, тк), тт )тз! тк! определяющее количество перестановок и предметов при условии, что имеется т; предметов типа г, при этом тт+ то+ +те = и, и количество разбиений множества, содержащего и неразличимых предметов, по й неразличимым ящикам, когда т, предметов попадает в т-ый ящик, и т1 + т2 + + ть = и. Следовательно, экспоиенциальную производящую функцию можно использовать для решения задач обоих типов.
ПРИМЕР 13.25. Сколько последовательностей длины и можно сформировать из целых чисел 1,2,3 и 4, если должно быть не менее одной цифры 1, двух цифр 2, нечетное количество цифр 3 и четное количество цифр 4? Если бы мы просто выбирали объекты, производящая функция имела бы вид +. з+ з .)(ха+ ха+ х4+ )(х+лз+ха".)(лз+х4+хе+.,.). Учитывая, что требуется количество последовательностей, порядок элементов име- ет значение, поэтому соответствующая экспоненциальная функция имеет вид —, + —, + —, + —, + —, + —, + —, + —, + —, + —, + —, +. ПРИМЕР 13.26.
Найдем производящую функцию, описывающую количество способов размещения и человек в трех комнатах при условии, что в каждой комнате должно быть не менее двух и не более десяти человек. Используя основное свойство обычных экспоненциальных функций, определяем, что искомая экспоненциальная производящая функция имеет вид /хз лз лто~ /хз хз лто'~ /хз хз хто~ Дл)=~' + +..+ )~ + + + — )~' — + — +.+ 1, 2! 3! 10! ) ~ 2! 3! 10! ) 1, 2! 3! 10! у 552 ГПАВА 13. Производящие функции или ,г з ~о;3 Пх)=' + + ..+ 1 2! 3! 10! ) ПРИМЕР 13.27.
Из объектов п типов требуется найти количество различных перестановок !б объектов при условии, что имеется неограниченное количество объектов каждого типа. Из вышеизложенного исследования перестановок с неограниченным числом повторений известно, что ответом является число и" (см. раздел 8.7). Попытаемся применить экспоненциальную производящую функцию. В данном случае экспоненциальная производящая функция имеет вид Х Х2 Хз п 1(х) = 1+ — + — + — + 1! 2! 3! Но .2 3 4 5 .б в*=1+ — + — + — + — + — + — + 1! 2! 3! 4! 5! 6! так что х х х 2 3 (е*)" = 1+ — + — + — +" ), 1! 2! 3! и ( е)п ик 1 + + ( ) + ( ) + 1! 2! 3! х" а так что коэффициент при —, как и ожидалось, равен п'. М' П Доказательство следующей теоремы предоставляем читателю.
ТЕОРЕМА 13.28. 2 .3 а) е* — 1= — + — + — + 1! 2! 3! е*+ е хг х' х' б) 2 2! 4! 6! =1+ — + — + — +...; Ек Е-з Х Хз Х5 Хт в) = — + — + — + — + 2 1! 3! 5! 7! ПРИМЕР 13.29. Найдем экспоненциальную функцию для описания количества способов размещения и гостей в трех комнатах при условии, что в первой комнате находится хотя бы один гость, нечетное количество гостей находится во второй комнате и четное количество — в третьей комнате. Производящая функция задается выражением + Е е Егк Е 2~ = (е* — 1) .
= (е* — 1) 2 2 4 1 (ВЗк В-е бге ! В-ге) 4 хи поэтому коэффициент при — равен — ((3)" — ( — 1)" — (2)" + ( — 2)") . П и! 4 РАЗДЕЛ 13.5. Зкспоненциапьные проиэеоонщие функции 553 Теперь имеются средства для нахождения количества способов размещения п различимых объектов в 1с различимых ящиках при условии, что ни один из ящиков не будет пустым, и количество способов размещения и различимых объектов в к неразличимых ящиках, когда ни один из ящиков не будет пустым.
ТЕОРЕМА 13.30. Количество способов размещения и различимых объектов в й различимых ящиках при условии, что ни один из ящиков не будет пустым и 1 < Й < и, равно т,'"'=~(-ц ( )о-ц". г з У(*) = ~-+ — + — + 1, 1! 2! 3! Но с х х х г з — + — + — +...) = (е* — 1) 1! 2. '3! ~(")(,г,(-)* ~=1 по теореме 13.28 по формуле бинома Ньютона. По определению, (ь )х (тс )гхг (ь )3 3 ~~ (1с )и и е '*=1+ 1! 2! 3! тд и=о так что пц-г.(')(-) г."",* =г.*-;з.(")(-и «- г, с=1 и=о и=в т=1 х и коэффициент при — равен и! т,'"'=г ( )(-1го — ц". с=1 Теперь мы готовы доказать следующую теорему. ТЕОРЕМА 13.31.
Количество способов размещения п различимых объектов в й неразличимых ящиках при условии, что ни один из ящиков не будет пустым и 1 < Й < п, равно к!"' =-„', Е(-1т(,)( — г, и=1 где 1о„: 0 < 1с < п1 — множество чисел Стирлинга второго рода. (и) ДОКАЗАТЕЛЬСТВО. Экспоненциальная производящая функция, описывающая ко- личество размещений и различимых объектов в и различимых ящиках при усло- вии, что ни один из ящиков не будет пустым, имеет вид 554 ГЛАВА 1з.
Производящие функции ДОКАЗАТЕЛЬСТВО. Поскольку Т„" равно количеству способов размещения и неразличимых объектов в )г различимых ящиков, то при переходе от множества с различимыми объектами ко множеству с неразличимыми объектами приходится делить на )г), т.к. все й! перестановок )с ящиков тождественны. Следовательно, ° УПРАЖНЕНИЯ 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
