Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 55
Текст из файла (страница 55)
Найти производящую функцию А(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 (ят) = уз(я) для всех т Е М.
Если 71 и (з эквивалентны, то они имеют одинаковый вес. Поэтому можно определить вес ю(Р) класса эквивалентности Р как вес л|обого элемента 7" из Р. Пусть Зов --. число классов эквивалентности веса к' в Ям. Производящая функция Ф(1) = ~ Зоягь называется перечисляющим в=о рядом для функций (или пвречисляючцим рядом для конфигураций). Т е01зем а (П. Пойа) Ф(1) = Рс(СЯ, О(й ), ..., Ю(1")), где п = )С(, Ро(йы гг, ..., 1„) цикловой индекс группы С, а Я(гь) подставляетгя в Ргэ на место пергменнои Хь (к.
= 1, 2, ..., и). 4.1. Найти тип подстановки я; 1) я = (2, 3, 4, 1); 2) и = (4, 2, 3, 1); 3) я = (3, 4, 5, 6, 1, 2); 4) я = (8, 2, 1, 7., 4, 6, 3, 5). 4.2. Представить подстановки из предьгдущей зада чи в виде произведения транспозиций. 4.3. Найти цикловой индекс группы С, где: 1) С группа подстановок вершин квадрата, получающихся при вращениях квадрата в плоскости; 2) С группа подстановок вершин квадрата, получающихся при вращении квадрата в пространстве; 3) С группа подстановок вершин тетраэдра, получающихся при его вращениях; 4) С .- группа подстановок ребер тетраэдра, получающихся при ого вращениях; 5) С .
группа подстановок граней тетраэдра, получающихся при его вращениях; 6) С=Яз; 7) С = А4, где Ач — знакопеременная группа степени 4, т.е, подгруппа группы Яч, состоящая из подстановок, представимых произведениями четного числа транспозиций; 8) С группа подстановок граней куба, получающихся при вращениях; 9) С группа подстановок вершин октаэдра. 18* 276 Га.
РНЬ Элементы комбинаторики 4.4. 1) Доказать, что группа С, определеннал в задаче 4.3, 1), задает на множестве Я4 одну орбиту. 2) Найти число орбит в множестве Х»., определяемых группой С, образованной перестановками; яг = (1, 2, 3, 4), яг = (1, 2, 4, 3), яз = (2, 1, 3, 4), яа = (2, 1, 4, 3). 4.5. Доказать лемму Бернсайда. 4.6. Пусть Ь = (Ьг, Ьз, ..., Ь„) вектор., соответствующий разбиению числа и, для которого Ьг + 2Ьз +... + аЬ„= в, где Ья целые неотрицательные числа (1 ( й ( и).
Через Н(Ь) обозначим множество всех таких подстановок симметрической группы Я„, у которых тип совпадает с Ь, и пусть Ь(Ь) = ~Н(Ь)~. и ,,— 1 1) Доказать, что Й(Ь) = и) ( П й ' Ьь!) а=1 2) Доказать, что Рз (гг, 1з, ..., 1а) = — г~ Ь®П 1ь". ' ь /с=1 3) Доказать, что цикловой индекс Рз„равен коэффициенту при та в разложении функции я' я" ехр(1гт+ 1з — +... + Гь — +... ) 2 Ь в ряд по степеням х. 4.7.
Пусть А„-. знакопеременная группа степени и, т. е. подгруппа группы Яа, состоящая из всех ее подстановок, представляемых в видо произведения четного числа транспозиций. Доказать, что Ря (гг, ..., 1в) = Рж,(1г, ..., 1,) + Рз„(1г, — 1з, ..., ( — 1)" т). 4.8. Пусть С вЂ” группа подстановок множества Х, Н вЂ” группа подстановок множества У, Х П У = И, Произвольной паре подстановок я Е С, о Е Н поставим в соответствие подстановку я х о множества Х 0 У, определенную так: з †> як при з е Х, з -э ох при з Е У. 1) Показать, что подстановки я хо образуют группу порядка ~С~ ~Н~, Эта группа называется произведением групп С и Н и обозначается С х Н. 2) Показать, что если подстановки я Е С, о Е Н имеют соответственно типы (Ьы ...., Ьа) и (сы ..., са), то я х и имеет тип (Ьг + сг, ..., Ьа + са).
3) Доказать, что Рс,н = Рс х Рн. 4.9. 1) Найти число ожерелий, которые можно составить из бусин двух цветов, если каждое ожерелье содержит семь бусин. Ожерелья считаются одинаковыми, если одно из другого получаются поворотом (зеркальные повороты не допускаются). 2) С помощью теоремы Пойа найти количество ожерелий из бусин й цветов, если каждое ожерелье состоит из п бусин (и простое число). Ожерелья считаются одинаковыми, если одно из другого получается поворотом без отражений. 277 5 5.
Асилитоеиические оценки и неравенства 4.10. 1) Найти число различных окрасок вершин тетраэдра в два цвета. Лве окраски считаются различными, если нельзя добиться совпадения цветов вершин вращениями тетраэдра. 2) Найти число различных окрасок вершин октаэдра в три цвета. 3) Найти число различных окрасок граней куба таких, что три грани окрашены в красный цвет, две в синий и одна в белый. 4.11. Пусть С группа подстановок множества Я„, а Е единичная группа, действующая на множестве 1у и переводящая каждый элемент и Е 111 в себя. Найти число орбит, определяемых степенной группой Ьо на множестве 1ч ~" . 4.12.
Пусть Т1. число попарно неизоморфных корневых деревьев с и вершинами, а Т(х) = ~Теть производящая функция для 1=! последовательности (Тг). Показать, что Т(х) = я~ Р5„(Т(л), ..., Т(ли)). и —.— 1 4.13. Пусть ди число попарно неизоморфных графов с п вершинами, 1и число попарно неизоморфных связных графов с и вершинами. Пусть д(!) = ~ ~ди!", 1(!) = ~ 1и1" и=1 и=1 суть соответствующие производящие функции. Показать, что Я(!) — ~ Р5 (1(!) ... 1(! )) и=1 4.14. Пусть р(п,, к) — число подстановок группы Яи, состоящих из й циклов, а ор„(с) = ~ ~р(п, Й)! -- соответствую1цая производящая функция.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
