Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 57
Текст из файла (страница 57)
Например, подстановка ~ ' ' ' ) имеет тип (1, О, 1, О). Если С /1, 2, 3, 41 некоторая подгруппа группы Ян,то многочлен Ра = Ро(Н, .... 1„) = ~С~ г~ ~1~'... 1в;", лес где (Ьы ..., 6„) тип подстановки к, называется цикловым индек- сом группы С. Пусть С - группа подстановок на множестве Ял. Элементы а и 6 из г„называются С-эквивалентными (обозначение: и - 6), если существует подстановка к Е С такая, что ка = 6 (или, что то же самое, кЬ = а). Классы С-эквиввлентности называются транзнтивными .множествами или орбитами. Лемма Бернсайдв,.
Число орбит н(С) в множестве. Ян, опре- деляемых группой С, дастся равенством о(С) = ~С~ з ) 6|(к). лен Пусть М и Х конечные множества, а С и Н группы подстановок соответственно на М и Я. Ставленная группа Н~ сос- ')4. Теория Пойа 275 таит из всевозможных пар (к; о), где я б С, о Е Н, и действует на множестве йГм всех функций 1: М вЂ” ~ Дг. При этом по определению (я, о)Э"(х) = оДк(я)) для всех т е М и Э" б 1ч'м.
Пусть на множестве йГ заданавесоваяфункция ип Х вЂ” э (О, 1, ...) и ц„--число элементов веса и в Х. Производящая функция ®1) = ~ 9„1п назыо=о вается перечисчяючцим рядом для фигур. Все функции ф из Ям определяются равенством ю(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) = ~ ~р(п, Й)! -- соответствую1цая производящая функция. Показать, что: и — 1 ') "-"и(') = П('+ ') =о 2) р(в, Й) = р(п — 1, Й вЂ” 1) + (и — 1)р(п — 1, Й).
3 5. Асимптотические оценки и неравенства При оценке роста функций употребляются следующие обозначения. Запись !р(и) = 0(ар(и)) при т е Х означает, что существует константа с такая, что рр(и)~ ( с~у!(и)~ для и Е Х. Если !р(и) = = 0(1р(т)) и ф1(и) = О(!р(т)) при и Е Х, то пишут !р(х) ~ф(т) при и Е Х. Запись 1р(и) = о(ф(и)) при л — э а означает, что Нп! = О. и — аа ф(я) 278 Гл. 1Ш. Элементы комбииатиорики Говорят, что функции у(х) и ф(х) асимптотически равны (обозначение: ~р(х) уз!х)) при х — ! а, если у(х) = ф(х) + о(ф(х)) при х — ) а. При разного рода оценках полезна формула Стирлинго и! '— чг2яп пас Лля более точных оценок используются неравенства ъ'2япп" ехр( — и+ —, ~ < и! <,(2япп" ехр( — и+ ~.
12) 5.1. Локазать неравенства.*): 1) пп~з < и! < ( — ) при и > 2; 2) !2п)! < !и!и+ 1))п; 3) (1+ — ) <3! 4) ( — ) <и!; 5) (~!)~ < ( ), >1; 8) (2п — 1)!! < и"., и > 1; 9) и! > е "и" 10) (1+ о)о > (1+ ап) при — 1 < а, и, > 1; ( —;".',)и". ( — ".') 5.2. Локазать неравенства: 1)(2 — ) <( )< — ( — ), п>й>1; 2) ( — ) <( )<,, п>й>0; 5.3. Используя формулу Стирлинга, показать, что при и — ~ со справедливы асимптотические равенства: 1) (2п — 1)0 — у'2!2п)пе "; 2) ! ) — 4"; п l з/ппп п! 2„ГЗ Зп ([ — )!) (п — 2[ — ))! (т+1)(т+2)...(т+п) 14 4) ' ' ' ' — ', и'" для целых неотрицательных Й и т; (2п) !! /и (2п — Ц!! Ч 2 ") Символом !2п — 1)0 обозначается число 1.
3. б .... (2п — Ц, а (2п)!! = 2 4. 6.... (2п). 279 у" Ь. Асннптогпнчесние оценка и неравенство 5.4. Показать, что при и — ~ оо справедливы следующие асимптотические равенства: о г 1)~ 1 (и) 2 2)~( п ) 1 2о я=1 е 3) ~ ~( )о'гян †„ « + о)", О < г < и; и 4) г Ь( ) — ~.4". такие числа, что О < а~ < Ья < сь < 1. 5.5. Пусть Ье, Ьг, ..., Ь, Выяснить, верно ли, что: 1) «~а)" <~н©Ь.<«+ )"; я=о и 2) «с)п<~;( 1) (п)Ь,<«а)п 5.6.
1) Показать неравенство Чебышева в следующей форме. 1 Пусть А = (аы аг, ..., ап) совокупность чисел, а = — у аг, п о г=г Ргг = — гг (аг — а) . Тогда доля Ьг тех а„для которых )аг — и~ > 1, г=г не превышает Ра,ге~. 2) Используя неравенство Чебышева, показать, что (п) Е (1) ' — ') 0<ь<пгг — г нгг ог'гьг;/о<я<о 3) Показать, что ~ — ( ) 2 ЬЫ я=г 5.7. С помощью формулы Стирлинга показать, что: 1) если к — — = о(ггг1~) при п — г оо, то 2 ()- "" п') 2"г' — ггь — ~'Пг г "/ нг2яп 2*) если а > О и й — — = о(пгрз) при п — г со, то а -~- 1 п1 г„.
«В- а)"г' 1 (й(а+ Ц вЂ” ап)г 1 () = )а ехр г— г х ъ'2гг па 1 2 ап х (1+ Р(1+ (й('+ ') 'и) )) 280 1"л. 1гЖ. Эаементы комбинаторики 3 ) если а>0, й<т, Ь=, ил=(й — — )6, тт= и а-Ь1 р на ,/агг а г- 1 (- ) т — ~й, ть — ~со, т„,й-+О, т — Й вЂ” ~ос при и-+оо, то а -~- 1 ) ~и (.) . (. Е"' (е ~л* е=ь 4) если а > О, х — л оо и х = о1п~ге) при и — > оо, то )а' е ' ~ 11+а)и. оа геа и> -~-г ~-1 а-~-1 5.8. Пусть 0 < Л < 1, Л„целое, р = 1 — Л, и пусть С1п, Л) = Л-л — о . С помощью формул 11) и 12) показать, что: 1г л,г22кХри 1) (Л ) С1п, Л) при п — ~ оо; 2) С1га Л) ехр ( — ) < ( „) < С1п, Л); 3) — С1п, Л) < ( ) при гг > 2; '( ) к©.
(") "."- л=.ли 5) ~ ( )<Л л"р "" при Л>-; л=ло, б) ~~~ ( )<Л л"р ои при Л< —. о<ь<ла 5.9. ПУсть й и и натУРальныо числа 1й < п). Показатли что: оо й — 1 1) 1п)л = пл ехр и=г г=г 2) если /с = о1~/й) при п -+ со, то 1п)ь — и"; 3) если й = оЯ при и — л оо, то для всякого т, > 1 е е 1п)л, = п~ ехр — ~~~ + 0( ) ,,И +Ц кг бе 4) при п — ~ со и й = о1пз'4) 1п)ь = и" ехр — — — — +о11) 2" биг 5.10. 1) Пусть й = й1гг) и е = е1п) таковы, что при и — > оо е = о1лг%). Показать, что (". ')/©-(-.")о 281 2) Показать, что если в = о(й"1<'ва!), то 5.11. Пусть в = в(н) и й = й(н) целочисленные неотрицательные функции натурального аргумента. Показать, что: 1) если в+ Й = о(пз7~) при н — з сю, то (.— )И-и) [-"- ""[ 2) если хз + !сз = о(п) при и -+ оо, то ( .')/©-' и р[ —" — '— ", — ',) (",")/(!),(-'— '), н) й+2в.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
