Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 55
Текст из файла (страница 55)
<а — п+ 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л+ Зу + 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„). Например, подстановка ~ ' ' ' ) имеет тип (1, О, 1, О). Если С /1, 2, 3, 41 некоторая подгруппа группы Ян,то многочлен Ра = Ро(Н, .... 1„) = ~С~ г~ ~1~'... 1в;", лес где (Ьы ..., 6„) тип подстановки к, называется цикловым индек- сом группы С.
Пусть С - группа подстановок на множестве Ял. Элементы а и 6 из г„называются С-эквивалентными (обозначение: и - 6), если существует подстановка к Е С такая, что ка = 6 (или, что то же самое, кЬ = а). Классы С-эквиввлентности называются транзнтивными .множествами или орбитами. Лемма Бернсайдв,. Число орбит н(С) в множестве. Ян, опре- делаемых группой С, дастся равенством о(С) = ~С~ з ) 6|(к).
лен Пусть М и Х конечные множества, а С и Н группы подстановок соответственно на М и Я. Степенная группа Н~ сос- ')4. Теория Пойа 275 таит из всевозможных пар (к; о), где я б С, о Е Н, и действует на множестве йГм всех функций 1: М вЂ” ~ Дг. При этом по определению (я, о)Э"(х) = оДк(т)) для всех т е М и Э" б 1ч'м.
Пусть на множестве йГ задана весовая функция ю: Х вЂ” э (О, 1, ... ) и ц„-- число элементов веса и в Х. Производящая функция ®1) = ~ 9„1п назыо=о вается перечисчяючцим рядом для фигур. Все функции 7'из Ям определяются равенством ю(7) = ~ ~ю(7'(х)). грункпии (з и уг из Хм налем зыввются эквивалентными (обозначение: 71 Я., если существует элемент я й С такой, что 71 (ят) = уз(я) для всех т Е М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
