Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 96
Текст из файла (страница 96)
+ апХп (1 — ах) при а = -4 и а = 1, получаем 1+ 4х = 1+ ( — 4)х+ ( — 4)2хз+ ( 4)зхЗ + + ( — 4)пап+ 1 = 1+х+х +х + . +хо+ (1 — х) так что — 5 3 + = -5(1+( — 4)х+(-4) х +(-4) хз+ 2 2 3 3 1+4х 1 — х +( — 4)пхп+ )+3(1+х+х +х + +хе+. ) = = — 2+ 23х — 77хз + 323хз + + ( — 5( — 4)п + 3)хо +.... В дальнейшем нам понадобится еше одна теорема о производящих функциях. .пе1 ТЕОРЕМА 13.3. При всех и > 0 имеем = 1+х+хз+х +. +х".
1 — х РАЗдЕП 13.2. Производящие функЧии и рекуррентные отношения 529 ДОКАЗАТЕЛЬСТВО. (1-х" ') = (1-х" ')(1+х+х'+... +х" + ..) = 1 1 — х =(1И1+х+х'+" +х" + ")-х"+'(1+х+х +...+х +...) = (1+х+хз+...+х" +х" ьз+. ) — гх +~+х -ьз „хо+а ) = 1+х+х +х + .. +х". Теперь рассмотрим применение производящих функций для решения рекуррентных отношений. Сначала проиллюстрируем метод на простом примере. Рассмотрим рекуррентное отношение а„= За„~ или а„— За„з = О.
Пусть у(х) = ао+ азх+ азх + азх +... +аох" + Умножим обе части равенства на Зх, помня о том, что умножение на х сдвигает каждый элемент последовательности вправо, так что Зх~(х) = Заох+Загх~+Зазх +Зазх + +За„~х" + За„х"+ + Вычитая Зх11х) из 1(х), получаем Дх) — ЗхДх) = ао+ (а~ — Зао)х+ (аз — За~)х + + (аз — Заз)х + . + (а„— За„-д)х" + Но а„— За„~ = О при всех п > 1, поэтому Дх) — ЗхХ(х) = ао Таким образом, (1 — ЗхЩх) = ао П*) = (, "Зх) = =по(1+Зх+З~х~+З~х'+ .
+3"хо+ ) = = ао + Заох + Ззаохз + Ззаохз + . + 3 аох" + Следовательно, а„= 3"ао. Заметим, что мы умножали обе части равенства на Зх, поэтому, вычитая, должны получить а„— За„з. Но, по определению данного рекуррентного отношения, это выражение равно О. ПРИМЕР 13.4. Найдем функцию, заданную рекуррентными отношениями ао = 5; аь = аь з + 3. Второе уравнение можно переписать в виде аь — аь з — 3 = О. 630 ГЛАВА 13. Производящие функции Снова положим Лх) = ао+агх+азх~+азхз+.
+а„х" +... Поскольку коэффициент при аь г равен 1, то теперь требуется найти хДх) = аох+агх~+азх +азх + +а„х"+'+ .. Кроме того, нам потребуется производящая функция, у которой при каждом члене стоит коэффициент 3, т.е. 3 311+ х+хз+хз+ +хо+ 1 — х = 3+ Зх+ Зх + Зхз + .. + Зх" + Теперь 3 Дх) — хУ(х) — = ао — 3+ (аг — ао — 3)х+ 1 — х + (аз — аг — З)х + . + (а„— а„г — 3) + Но аь — аь г — 3 = 0 при всех й > 1, так что 3 1'(х) — хДх) — — = ао — 3 = 2. 1 — х Решая это уравнение относительно Дх), получаем 3 2 Х(х) = + — = (1 — х)з 1 — х = 3(1+ 2х + Зх'+ " + (и + 1) х" + " .
)+ +2(1+х+х~+ +х" + ) = = 5+ 8х + 11х + 14хз + + (Зп + 5)х" + так что а„= Зп+ 5. ПРИМЕР 13.6. Найдем функцию, заданную рекуррентными отношениями ао=1; а~ =4; аь =аь г+баь з. Как и ранее, положим ~(х) = ао + а~х + азх + азхз + + а„х" + . Поскольку коэффициент при аь г равен 1 и коэффициент при аь з равен б, нужно найти х~(х) = аох + азха + азх~ + азх4 + + а„х" ьг + РАЗДЕЛ 13.2. Произеооящие функции и рекуррентные отношения 631 Ох~1"(х) =баохз+6азх~+баях +6азх + +ба„х"+з+ Поэтому 1'(х) — х1(х) — бх~1(х) = ао+ (аг — ао)х+ (аз — аз — Бао)хз + + (аз — аз — баг)х + ..
+ (а„— а„~ — бая а)х" + Но а„х" — а„з — ба„з = 0 для всех и ) 1, так что 1'(х) — х1(х) — бх 1(х) = ао+ (аз — ао)х = 1+Зх. Решая уравнение относительно Дх), получаем 1+Зх 1 + Зх У( )— 1 — х — 6хз (1 — Зх)(1+ 2х) Полагая 1+ Зх а Ь (1 — Зх) (1 + 2х) (1 — Зх) (1 + 2х) и умножая обе части равенства на (1 — Зх)(1+ 2х), получаем 1 + Зх = а(1 + 2х) + Ь(1 — Зх). 1 Полагая х = — —, получаем 2' 1+ -- =а 1+2 -- +Ь 1 — 3 1 1 так что Ь = — —. Полагая х = —, получаем 5 3' 1+1=а 1+2 — +Ь 1 — 3 6 так что а = †.
Следовательно, имеем 5 5 (1 — Зх) (1+ 2х) 6'з — ) (1+Зх+Ззхз+Ззхз+ . +3"х" + )— 5) — 1+ ( — 2)х+ ( — 2)~х~ + ( — 2)зхз + . + ( — 2)"х" + 1,5/ так что а„= ( -) (6. (3)" — ( — 2)"). /1'1 1,5) 1 = (1+4х+4~х~+4~хз+ +4"х" + ) (1 — 4х) это даст 4"х".
Поэтому 1 Дх) — ЗхДх)— (1 — 4х) = ао — 1+ (ад — Зао — 4)х + (аз — Зад — 4 )х~+ + (аз — Заз — 4 )х + . + (а„— а„д — 4")х" + Поскольку а„— Заь д — 4" = 0 при всех и > 1, имеем 1 1 (х) — Зх1'(х)— =ао — 1=0. (1 — 4х) Решая уравнение относительно г'(х), имеем Пусть 1 а Ь (1 — 4х) (1 — Зх) (1 — 4х) (1 — Зх) Умножая обе части равенства на (1 — 4х)(1 — Зх), имеем 1 = (1 — Зх)а+ (1 — 4х)Ь. 1 Полагая х = —, получаем 3' 1= 1 — 3 — а+ 1 — 4 — Ь, 1 Полагая х = —, имеем 4' 1= 1 — 3 — а+ 1 — 4.— Ь, так что Ь = — 3 532 ГЛАВА тЗ. Произеооящие функции ПРИМЕР 43.6. Найдем функцию, заданную рекуррентными отношениями оо аь=Заь д+4".
Как и ранее, пусть д(х) =ао+а,х+азх +азх +. +а„х" +.. Поскольку коэффициент при аь д = 3, найдем ЗхДх) = Заох + Задх + Зазх + Зазх + + За„х"~~ + Так как Рлздел 13.2. производящие функции и рекуррентные отношения 633 поэтому а = 4. Следовательно, имеем Пх) = 4 3 (1 — 4х) (1 — Зх) =4(1+4х+4гхг+4зхз+.- +4"х" + ..)— — 3(1+ Зх+ Згхг+ 3 х + ..
+3"х" + поэтому а„= 4 4" — 3 3" = 4" ь' — 3"+' ПРИМЕР 13.7. Найдем функцию, заданную рекуррентными отношениями ао = 3' а„= 2а„г + а. Второе уравнение также можно переписать в виде а„— 2а„г — и = О. Опять положим з(х) = ао+а~х+агх + азх + -.. + а„х" + Поскольку коэффициент при ак г равен — 2, найдем 2хДх) = 2аох + 2агх + 2агхз + 2азх4 + + 2а„х" ь~ + Кроме того, нам нужна производящая функция, каждый член которой имеет мно- жителем а, но это есть = х(1 + 2х + Зхг + ..
+ пх" + ) = (1 — х)г =х+2х +Зхз+ +ах" + Теперь х Дх) — 2х1" (х) — = ао + (а~ — 2ао — 1)х + (1 — х)г + (аг — 2аг — 2)х + ... + (а„ вЂ” 2а„ г — и) + Но аь — 2аь ~ — к = О для всех к ) 1, поэтому Й(х) 2хПх) г ао 3 (1,)г Решая уравнение относительно г'(х), получаем х 3 3 — 5х+ Зхг Пх)— + (1 — 2х)(1 — х)г (1 — 2х) (1 — 2х)(1 — х)г А В С + (1 — х) (1 — х)г (1 — 2х) ' + 534 ГЛАВА 13. Производящие функции так что 3 — 5х + Зхг = А(1 — х)(1 — 2х) + В(1 — 2х) + С(1 — х)г = = А(1 — Зх + 2хг) + В(1 — 2х) + С(1 — 2х + хг). Приравнивая коэффициенты при хг, х и 1, получаем соответственно 3 = 2А+С; -5 = -ЗА — 2 — 2С; 3=А+В+С.
Решая эти уравнения, получаем А = — 1, В = — 1 и С = 5. Следовательно, а„= — и — 2+ 5(2"). ° УПРАЖНЕНИЯ 1. Выразите приведенные ниже дроби 1 а) (х + 4)(х + 3) ' хг+2х+3 в) (х — 1)г(х — 2) ' Зхг + 1 д) (х — 1)г(х — 2)г 2. Выразите приведенные ниже дроби 2х+1 а) (х — 4)(х+ 2) ха +2х+3 в) (х+ 1Нх — 2)' ' Зх +1 цз ' 3. Найдите разложения приведенных 1 а) х+4' 1 в) цз Зхг+ 1 д) (х — 1)г(х — 2) через элементарные дроби: 2х — 3 (х — 2)(х — 3) ' г) (х — 1)(х — 2)(х — 3) ' через элементарные дроби: 2х — 3 (х — 2)(х + 4) ' хг г) (х — 1)(х+ З)(х — 5) ' ниже производяших функций: 1 (х — 2)г ' г) (х — 1)(х — 2) ' — 1 1 5 Дх) = (1 х) (1 х)г (1 2х) + = — (1+х+х + +х" + .) — (1+2х+Зх + ...
+ (и+ 1)х" + ) + 5(1+ 2х + (2х) + + (2х)" ). РАЗДЕЛ 73.3. Производящие функции и комбинаторные подсчеты 535 иже производящих функций: б) (х — 1)г ' г) (х+ 1)(х — 2Их+ 3) ' 4. Найдите разложения приведенных н 1 а) х — 3 в) цз 2хг+ 6 (х — 1)г(х + 2)г 5.
Используя производящие функции, шения: а) по=1; а„= 2а„1+ 3" при и > О. в) ао =8; а1 = 16; а„ = 2а„ 1 + За„ г при и > 1. д) по=4; а„= 2а„1 — 3 при и > О. 6. Используя производящие функции, щения; а) ао=1; а„= 2а„1 при и > О. в) ао=1; аз =3; а„= 5а„г — 6а„г при и > 1.
д) ао= 1; а„= 2а„1+ и — 1 при и > О. 7. Используя производящие функции, шения: а) ао =1; а„= а„1+ и при и > О. в) ао=1; а„= 2а„1+ 2" при и > О. решите следующие рекуррентные отно- б) ао 2; За„1+ и при и > О. 1; 0; 4а„ 1 — 4а„ г при и > 1. а„ г) ао а1 а„ решите следующие рекуррентные отно- б) ао= 3; а„= 4а„1+ 2и при и > О. г) ао =1; а1=3; а„ = 7а„ 1 — 10а„ г при и > 1. решите следующие рекуррентные отно- б) ао 2; За„1 + 2" при и > О.
1; а„ г) ао 8; ба„1 — 9а„г + 2" при и > 1. а1 ан 13.3. ПРОИЗВОДЯЩИЕ ФУНКЦИИ И КОМБИНАТОРНЫЕ ПОДСЧЕТЫ В настоящем разделе речь пойдет о применении производящих функций для комбинаторных подсчетов. Это превосходный метод, который оценит каждый, кто столкнется с его использованием. Ранее мы рассматривали производящие функции как формальные ряды, не касаясь таких понятий анализа, как сходимость, ряды Тейлора, интегрирование и дифференцирование. 636 ГЛАВА 13. Проиэеодящие функции Для начала рассмотрим функцию (1+ х)". Известно, что по формуле бинома Ньютона (1+ х)" = (о)х + (,)х + (2)х + + ( )х", так что коэффициент при х" равен количеству способов выбора к объектов из и объектов без учета порядка.
Следовательно, производящая функция вида (1+х)" является производяшей функцией для числа сочетаний из и объектов по к. По теореме 13.2 = 1+ (™)х+ (™ггь )х + ("з )х + + ( )х" + поэтому коэффициент при х" есть число сочетаний из т объектов по к с повторениями. Следовательно, производящая функция, ' „, является производящей функцией, которая применяется для определения числа сочетаний из т объектов по Й с повторениями.
Теперь рассмотрим произведение (1, + х,) (1Ь + хь) (1, + х, + ха И1а + ха + хг), где нижние индексы отслеживают только "происхождение" каждого х и никак не влияют на его значение. Таким образом, х„хь, х, и ха — это х, где нижний индекс — просто метка. Если положить хо = 1, при ! = а, Ь,с и !1 и рассмотреть слагаемое х4, то мы увидим, что оно представляет собой сумму хахьхсха + хахьх,ха + х, хьх,ха + хахьхс1ха + оогг о!г! 1ог! !!г о + ХаХЬХсХа + ХаХЬХсХа + ХаХЬХсХа + ХаХЬХста О 1 1 2 1 О 1 2 1 1 О 2 1 1 1 1 Сумма степеней в каждом слагаемом равна четырем, значит, имеются все воз- можные решения уравнения е, +еь+е,+е1= 4 при О < е, < 1, О < еь < 1, О < е, < 2 и О < еа < 2, В обшем случае, при О < г < 6 коэффициент при х" равен количеству решений уравнения е + еь + е, + еа = г при О < е < 1, О < еь < 1, О < е, < 2 и О < еа < 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
