Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 95
Текст из файла (страница 95)
Рис. 12.28 Рис. 12.29 7. Найдите ладейный полином для доски, изображенной на рис. 12.30. 8. Найдите ладейный полином для доски, изображенной на рис. 12.31. Рис. 12.30 Р-. 12.21 520 ГЛКВА 12. Сноеэ о конлбинэторнгнх подочетак 9. Найдите ладейный долином для доски, изобраккенной на рис. 12 32. 10. Найдите ладейной долино л для доски. итоги1ак~енной нз оиг. 12 лй РАЗДЕЛ 12.4. Ладейные попиномы и зепреизенные позиции 621 Рис.
12.38 17. Для заданной доски, изображенной на рис. 12.40, где заштрихованная об- ласть А — запрещенная зона, найдите количество допустимых размещений. 18. Для заданной доски, изображенной на рис. !2.41, где заштрихованная область А — запрещенная зона, найдите количество допустимых размещений. Рис. 12.40 Рис. !2.41 19. Найдите количество допустимых перестановок на доске размером 4х 4, когда запрещенные позиции — клетки вдоль обеих диагоналей. 20. В футбольной команде, состоящей из шести игроков, игрок А не может играть на позициях 1 и 3, игрок  — на позициях 2 и 4, игрок С вЂ” на позиции 6, игрок Р не может играть на позициях 5 и 6, игрок Е не может играть на позициях 5 и 6, а игрок Г не может играть на позициях 1 и 3. Найдите количество возможных способов заполнить все позиции игроками.
21. Шестеро мужчин арендуют дом с шестью спальнями. Первый мужчина не хочет спать в спальнях 4 и 6. Второй не хочет спать в спальнях 4, 5 и 6. Третий мужчина не может спать в спальне 3. Четвертому мужчине не подходят спальни 1 и 2. Пятый не хочет спать в спальнях 1 и 2. Шестой мужчина не может спать в спальнях 1, 2 и 3. Сколькими способами жильцы могут распределить между собой спальни? 22. Футбольный тренер купил шесть новых автомобилей для шести лучших игроков. Он приобрел Чо!чо, Мегсебез, ВМ%, !.ехцз, !.!псо!п и Саг!П!ас. Первый игрок не хочет управлять СайПас илн !.!псо!и. Второй игрок не будет управлять СайПас или !.!псо!и.
Третий не будет управлять ! ехцз. Чевертый игрок не будет управлять Мегсебез. Пятый игрок не будет управлять Чо!чо или ВМчч'. Шестой не будет управлять Чо!чо или ВМЧ4. Сколькими способами тренер может раздать машины? 23. Латинский квадрат размером п х и — это квадратная таблица, в которой элементы каждой строки и элементы каждого столбца являются перестановкой первых и положительных целых чисел.
Таким образом, каждое число появляется один раз в каждой строке и в каждом столбце. Предположим, что первые две строки чисел латинского квадрата размером 4 х 4 имеют вид 1,4,3,2 и 4,1,2,3. Сколько можно образовать различных третьих строк? 522 ГЛАВА т2. Снова о хомбоналюрных лодсчвглэх Указание; в первой строке таблицы вычеркните позицию, на которой присутствует 1, и т.д.
24. Предположим, что первые две строки латинского квадрата размером 4 х 4 имеют вид 4, 3, 1, 2 и 3, 4, 2, 1. Сколько можно образовать различных третьих строк? 25. Предположим, что первые две строки латинского квадрата размером 5 х 5 имеют вид 1,3,2,4,5 и 2,1,3,5,4. Сколько можно образовать различных третьих строк? 26. Предположим, что первые две строки чисел латинского квадрата размером 5х5 имеют вид 1,2,3,4,5 и 3,4,5,2,1. Сколько можно образовать различных третьих строк? 27.
Предположим, что первые две строки чисел латинского квадрата размером 5 х 5 имеют вид 1, 2, 3, 4, 5 и 2, 3, 4, 5, 1. Сколько можно образовать различных третьих строк? 524 ГЛАВА 13. Производяи4ие функции х о (1, О, О, О, 0,...) = х о (х о (1, О, О, О, О, ,)) = = хи(0,0,1,0,0,...) = (0,0,0,1,0,...).
Методом индукции можно доказать, что х" о (1,0,0,0,0,...) — последовательность, в которой после й нулей стоит единица, а оставшаяся часть последовательности состоит из нулей. Поскольку (1,0,0,0,0,...) — это последовательность 1,0,0,0,..., ее можно отождествить с числом 1. Таким образом, х=х 1 =хо(1,0,0,0,0,...) =(0,1,0,0,0,...); хг =х 1=хго(1,0,0,0,0,...) =(0,0,1,0,0,...); х = ха 1 =х о(1,000,0,...) = (О 00,1,00,...); х4 = х' 1 = х о(1,0,0,0,0,...) = (0,0,0,0,1,0,0,...), и х" = х"о (1,0,0,0,0,...) — последовательность, в которой после й нулей стоит единица, а оставшаяся часть последовательности состоит из нулей. Понятно, что (ао,ам аз, аз,а4,0,0,0, О,...) = ао о (1,0,0,0,0, О,...)+ + аг о (О, 1,0,0,0,0,...)+ + аз о(0,0,1,0,0,0,...)+ + аз о (0,0,0, 1, 0,0,...)+ + а4 о (0,0,0,0,1,0,...) = = ао + а|х + агх + азха + а4х 2 3 4 (ао,аыаг,аз,...,а„,0,0,0,0,...) =ао+а|х+агх~+азх~+а4х +.
+а„х". В обшем случае (ао,аыаг,аз,а4,...,а„,...) = ао+а|х+агх +азх +а4х4+. +а„х" + Выражение по+ агх+агх +азха+а4х4+ +а„х" называется производящей функцией последовательности ао, аы аг, аз,... В разделе !3.5 используются производящие функции несколько иного типа, называемые экспоненциальными.
Для обычной производяшей функции (1, 1, 1, 1, 1, 1,...) = 1 + х + х + х + х + х + (ао,аы аг,аз,а4, .) = ао + а|х + агх + азх + а4х + .. г з (ао,аыаг,аз,...,а„,0,0,0,0,...) =ао+азх+азха+пах~+ +а„х", а для экспоненцнальной производящей функции мы полагаем х хг хЗ х4 ха ха (1,1,1, 1,1,1,...) = 1+ — + — + — + — + — + — + 1! 2! 3! 4! 5! 6! РАЗДЕЛ 13.2.
Производящие функции и рекуррентные отношения 525 Тогда 2 З 4 («10 «11 «12 «13 «14 ' ' ') «10+ "11 + «12 + «13 + «14 + ' ' 1! 21 3! 4! .2 3 .а (ао, а1, аз, аз, , а„, О, О, О, О,...) = ао + а1 — + аз в + аз — + ... + а„ вЂ” . 1! 2! 3! "пй« ' 13.2. ПРОИЗВОДЯЩИЕ ФУНКЦИИ И РЕКУРРЕНТНЫЕ ОТНОШЕНИЯ В этом разделе рассматривается использование производящей функции для решения рекуррентных отношений.
В следующих трех разделах рассматривается применение производящих функций для комбинаторных подсчетов. Назовем ао + агх + азхз + азх + а4х + .. + а„х" + " производящей функцией последовательности ао, а1, аз, аз, ... П) Пусть 1(х) и д(х) — многочлены. Определим отношение — как д(х) = «10 + «11х + «12х + азх + «14х + ' ' ' + а~х 1 (х) 2 3 4 о д(х) тогда и только тогда, когда 1(х) = д(х)(ао + а1х + азхз + азхз + а«х4 + . + а„х" . ).
ТЕОРЕМА 13.2. Для любого гп имеет место разложение =1+ ах+ ах + + а х +..+ а"х" + ДОКАЗАТЕЛЬСТВО. Используя метод индукции, покажем для гп = 1, что 1 =1+ах+а х +а х + .+а"х" + (1 — ах) что эквивалентно 1 = (1 — ах)(1 + ах + а х + а х + + а"х" + . ). 525 ГЛАВА 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 )а х + ( 3 )а х + .. + ("+")а"х" + ..) = (1+1) аХ + (1+2) а2Х2 + (Ь» 3)азХЗ + + (А+и) апХп (а Н1+(~1) +("2) +("3 ) +...+(" п)ап и+...) + (1+1)аХ+ (1+2)а2Х2 1 (к+3)азХЗ+ + (Ь+п)а»Хп ("+2)азХ3 ... ("»-и 1)а»Х» (й) аХ + (1+1) а2Х2 + (1+2) азХЗ + + (й+и — 1) а»Хп поскольку, согласно тождеству Паскаля, имеем lс+и — 1 1г+и — 1 к+п РАЗДЕЛ 23.2.
Производящие функции и рекуррентные отношения 527 так что /с+а !с+и †1+и †Следовательно, (1 — ах)"+'(1 + ( +,')ах + ( г )а х + ( з )а х + + ( +„")а"х" + ) = )ь(1 + (~) + ( +~) 2 2+ (~+2) зхз + + (~+~- ) о п + ) Но, по индуктивному предположению, (1 )ь(1 + (ь) + (ьч-1) 2 2 + (ьч-2) 3 3 + + (к+о-1) и и + что и требовалось доказать. Из доказанной теоремы следует, что 1 = 1 + 2ах + За х + 4азхз + + (гс+ 1)а" х" + (1 ах)г 1 г г з з !п + 1)(п + 2) и о =1+Зах+багхг+10азхз+ + ' '' )а"х" +. (1 — ах) з 2 Из математического анализа известно, что любая дробь вида Ах+В (1 — Сх)(1 — Рх)' где константы С и Р различны, равна а Ь + 1 — Сх 1 — Рх Ахг+ Вх+ С (1 — Рх)(1 — Ех)(1 — Ех) ' где константы Р, Е и Е различны, равна а Ь + + 1 — Рх 1 — Ех 1 для некоторых постоянных а, Ь и с.
Также, если константы Р и Е различны, то Ахг + Вх + С а + (1 — Рх)2(1 — Ех) 1 — Рх (1 — Рх) г 1 — Ех + для некоторых постоянных а и Ь. Такое представление называется разложением на элементарные дроби. Более того, любая дробь вида 528 ГЛАВА 13. Производящие функции для некоторых постоянных а„Ь и с, и если константы Е и Е различны, то Ах'+ Вхз+ Сх+ В а Ь с а (1 — Ех)3(1 — Ех) 1 — Ех (1 — Ех)2 (1 — Ех)3 1 — Ех + + + для некоторых постоянных а, Ь, с и а'.
Предположим, что требуется найти разложение производящей функции 15х 15х 1 + Зх — 4хз (1 + 4х)(1 — х) Пусть 15х а Ь (1+4х)(1 — х) 1+4х 1 — х для некоторых а и Ь. Умножая обе части равенства на (1+ 4х)(1 — х), получаем 15х = а(1 — х) + 6(1 + 4х). Полагая х = 1, приходим к уравнению 15(1) = а(1 — 1) + 6(1 + 4), 1 решая которое, получаем Ь = 3. Полагая х = — —, приходим к уравнению 4' 1 1 1 15( — — ) = а(1 — — ) + 6(1 + 4( — — )), 4 4 4 решая которое, получаем а = — 5, поэтому 15х — 5 3 + (1+4х)(1 — х) 1+4х 1 — х Применяя формулу 1 ,1Х + а2Х2 + аЗХЗ +...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
