Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 56
Текст из файла (страница 56)
270 Гл. $7Ы Элементы комбинаторики 5) 2 ~ (п+ 2е) (п -'е 2т — 2е Ч- 1) (2п -'с 2т, -'е 2) 6) ~ ~< — 1)" '4'( 2 ) =п,+1. л=а 3.13. Пусть А<1) и Е<1) являются соответственно обычной и экспоненциальной производящими функциями последовательности <о„). 1) Используя равенство и. '= /е 'х" е1х,показать,что о А<1) = ~е иЕ<хц) е1х. <4) о 2) Убедиться, что формула (4) справедлива для производящих функций А<1) = <1 — 1) з и Е<1) = ее последовательности аа = аз = =аз=...=1. 3) То же, что и в задаче 2), но для последовательности с общим членом О, п(у, <и), и >11 3.14.
1) Пусть <а)„= о<а — 1)... <а — п+ 1). Доказать, используя экспоненциальные производящие функции, что и <а + Ь) а = ~~~ ( „) <а) и ь <6) ы У к а з а н и е. Использовать тождество < 1 + 1) " ' е = < 1 + 1) ' < 1 + 1) е, 2) Пусть <а)„и = п<а — 6)... <а — 6<п — 1)).
Показать, что и <а+6)пь = ~ ( )<о)н — на<6)ьр. я=о 3.15. Пусть <и„), <Ьп) последовательности, Ь 1 = О, А<1) и В<1) -- соответствующие производящие функции. Показать, что; 1) если ап = ܄— Ьа м то А<1) = В<1)<1 — 1); 2) если аи = Ьпл 1 — 6„, то А<1) = ВЯ вЂ” ' — ьа1 1 — 1 3) если а = дал з+ Ьниз+..., оа = В<1), то А<1) = В<1) — ВП) 1 — 1 4) если ан = пЬ„, то А<1) = 1 — В<1); Ж 5) если а„= пзЬ„, то А<1) = 1 — (2 — В<1)); с~ б е1 41<, бе 6) если определить операцию ол <Ь > 0) над последовательностью <д„) с помощью соотношения В':<Ьп) = Ьп+ (') Ьи, +...
+ ("+'. ') Ь„, +... + ("+ ') Ьа и положить а„= За<ба), то А<1) = <1 — 4) ~В<1); у" Х Возвратные ноеледовотельноети, нроизводвтие ер1рнниии 271 7) если ао = Ьзю то А(1) = — (В(1112) + В( — 1172)); 8) если ао = Ьо + Ь, +... + Ьи 1, ао = О, то А(1) = В(1)1(1 — 1) 3.16.
Пусть А(1) и В(1) — производящие функции последователь- ностей (аи) и (Ь„) соответственно,и пусть А(1) В(1) = 1. Найти (Ьн) и В(1) по заданной последовательности (а„): 1) ао = ( ); 2) а„ = а"; 3) а„ = п + 1; 4) ао — — аз — — 1, а„=О при пФО,2; 5) а„= ( — 1)"; 6) ан = ( — 1)" ( )4 3.17. Пусть последовательность (а„) удовлетворяет рекуррент- ному соотношению анлз+ ра„ь1 + да„= О.
1) Показать, что А(1) = ао+ (а1+ рао)1 1 + ре -Ь о12 2) Пусть 1+ р1+ до~ = (1 — Л11)(1 — Л21), Л1 ф Лз. Показать, что Л7 — Л", Л вЂ” Л Л вЂ” Л 1 Л2 1 2 3) Выразить ао в случае, когда 1+ р1+ фз = (1 — Л1) . 3.18. Пусть "=к("") = к(гз) з=о 1=О и А(1), В(1) - — соответствующие производящие функции.
1) Показать, что а„и Ьо связаны соотношениями вида ап-~1 — — а„+ Ьие1, Ь 2-1 =б +а„во=1, .Ьо=О. 2) Показать, что А(1) и В(1) удовлетворяют системе уравнений А(1) — 1 = 1А(1) + В(1), В(1) = 1А(1) + СВ(С). 3) Найти А(1) и В(1). 4) Показать, что ( 2 ) 1+ьев ( 2 )" 1 1пп ( ) ао= 1нп ( ) Ь„= —. (3+ йб) "' 2йб ' (3+ ь25) " ьеб 3.19. Пусть члены последовательности (а„) удовлетворяют соот- ношению ан — иоан — 1 + а111н — 2 + ° + ап — 1ао ао 1) Показать, что производящая функция А(1) = ~ аоби удовлетп=о воряет равенству 1А2(1) = А(1) — ао, или, с учетом начального усло- 1 — ьеГ: 41 вия равенству А(1) = 21 272 Гл.
1711 Элелентег нолбинаторггки 2) Разлагая Агг) в ряд по степеням 1, показать, что ап= — ( ). 3) Найти последовательность (ап), члены которой удовлетворяют соотношениям аоип г + игал †+ . + ггп — гао = 2пап, ао = аг —— 1. 3.20. Вывести рекуррентное соотношение для последовательности чисел (ап) и разрешить это соотношение, если: 1) ап --- число способов разбиения выпуклого (гг+ 2)-угольника на треугольники диагоналями, не пересекающимися внутри этого многоугольника; 2) ап число таких способов расстановки скобок в выражении Ьг . Ьэ .,...
Ьплг, при которых получающиеся выражения имеют смысл. 3.21. Используя метод математической индукции, найти последовательность (ап) по рекуррентному соотношению и начальным условиям: 1) а„пг = (и -и 1)ап, ао = 1; 2) па„лг + ап = О, аг = 1; 3) (и + 2)(п + 1)апе.я — п ип, ао = О, аг = 1; 4) (гг + 2)~алла + ап = О, ао = 1, аг = 0; 5) паап,з + (и + 2)зап — — О, аг — — 1, аг — — 0; 6*) а~юг — апа пз — — ( — 1)п г, ао = 1, аг = 1.
3.22. Пусть А„гг) = ~ а(п, Ь)1' ь=о последовательности, удовлетворяющей соотношению а1гг, Й) = = а(п, Ь вЂ” 1) + а(п — 1, й) с начальными условиями а(п, 0) = 1, а(0, й) = 0 при й ) О. Показать, что: 1) 1 — 1)Апгг) = Ап г(1); 2) А„гг) = (1 — 1) 3) а(п, й) = ( ). 3.23. 1) Сколькими способами можно разменять 10-копеечную монету монетами в 1, 2, 3 и 5 копеек.
2) Та же задача, что и 1), при условии, что каждая из разменных монет присутствует в двух экземплярах. 3) Та же задача, что и 1), при условии, что имеются четыре копеечные монеты, три монеты достоинством 2 копейки, две трехкопеечные монеты и одна пятикопеечная.
3.24. Найти производящую функцию А(1) для последовательности (ип), где: 1) ап число решений в целых неотрицательных числах уравнения 2л+ 33 + 5з = гг; 273 14. Теория Пойа 2) а„число решений того же уравнения при условии, что и, у, я принимают значения 0 или 1; 3) ао — число решений в целых числах того же уравнения лри условии, что 0 < и < р, 0 < у < г, 0 < з < е. 3.25*.
По заданной производящей функции А(«) для последовательности (а„) найти о„; 1) А(«) = П (1 — Д" «): ~9~ < 1- ь.=о Указание. Показать, что А(«) = (1 — д«)А(9«), и сравнить коэффициенты лри «о в левой и правой частях этого равенства; 2) А(«) = П (1+ е««~ ). о=о Указание. Локазатзч что а„= д~", где б„число единиц в двоичном разложении числа п. и 3.26. Пусть Я(п. .й, «) = ~«( — 1)о' '( )(о+«)ь. Показать, что: =о 1) Б(п + 1, й, «) = Я(п, й, «+ 1) — о(п, й, «); 2) Я(п, й, «+ 1) = Я(г~,, й, «) — Я(п+ 1, й, 1); 3) Я(п, й+ 1, «) = (и+1)Я(п, й, «) + пЯ(п — 1, й, «); 4)Я(п,й,«)=0 при п>й; 5)Я(п,п,«)=п.'; 6)Я(п,й,«)>0 при п<й; 7) Я(п, й, «) возрастающая функция параметров й и «цри п < й; 8) Б(п, и+1, «) =~(й+«)йь, 9) Я(1, й,О)=1 нри 1<й. «=о 3.27. Пусть Я(п, й) = Я(п, й, 0) = ~~~ ( — 1)" '(п)и" и оо(«) оо Я(п, й)«~.
Показать, что цри ф < 1: а=о 1) оо(«) = (1 — «)(1 — 2«) ...(1 — пЦ ' о 2) о («) «~ ( 1)п — мй( )(1 й«)— 3 4. Теория Пойа Подспланоекой на множестве Яв = (1, 2, ..., п) называется отоб- / 1, 2, ..., п 1 ражение Л„на себя* ). Подстановку я = ( . ' . ' '''' . ) будем часто задавать строкой («з, «з, ...,!„). Подстановка называется Иик- *) Роль Я может играть любое множество из и элементов. 18 Г. П. Гаврилов, А. А. Сапожеико 274 Рл, УШ. Элементы комбинаторики лической' (или циклом), если некоторое число )з переводится ею в )э, )э — в уз и т.д., зь з переводится в у~,.
уя в )ы а все остальные числа остаются на месте. Такой цикл обозначается че- рез 0ы уз, уь). Число Ь называется длиной цикла. Произвольная подстановка может быть представлена в виде произведения циклов. Например, ) ' ' ',' 3) = (1, 2)(3, 4, 5). Цикл длины 2 называется /1,.2,3,4,51 транспозицисй. Всякая подстановка представима в виде произведе- ния (т.
е, последовательного выполнения) транспозиций. Подстановка, представимая в виде произведения четного (нечетного) числа транспо- зиций, называется четной (соответственно нечетной). Подста- новки на множестве У образуют группу относительно операции произведения. Операция произведения подстановок кг и кз состоит в 71, 2, 3, 41 последовательном их применении. Например, если кз = ) ' ' ' 1), /1.
2, 3., 41 /1,2,3,41 кз = ~1 4' 3' 2), то кзкэ = ~4' 2' 3' 1). Операция произведения обла- дает, как нетрудно проверить, свойством ассоциативности: к1от) = = (ко)т. Единичным элементом группы является тождественная /1,2,...,па / 1, 2, ..., п 1 подстановка ~ ' ' '''' ').
Подстановкой, обратной к ) ' ' ' ), 11,2,..., п)' 'чй,зм ...,1„)' /Н,Н,....,1„1 является подстановка . Группа подстановок на мно- жестве У„называется симмвхпрической группой и-й степени и обозна- чается через Яо. Порядок симметрической группы и-й степени (число ее элементов) равен и!. Если подстановка на множестве Х" представляется в виде про- изведения Ьз циклов длины 1, Ьз циклов длины 2 и т.д., Ь„ циклов длины и, то говорят, что подстановка имеет тип (Ьы Ьз,..., 6„).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
