В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 32
Текст из файла (страница 32)
Пусть т, таща. Тогда т. (тзс) =т <с, (г) „с — 00 >. Обозначим с'г с, [г), г=1, 2, 3. 4. 5. Нсоолиуя введенные обозначения. т 'з получаем т (тзс)=т <с ь ... се>=<с'- О), ..., с', 151>= =<с, [т-, (г)1, ..., с, гт. [зП > <с( ),1[1... ..., с(, )-,15) >=(т.
З)с, т. е. условие (3.20) выполняется. Верне ке «схс;ачн с Г»ьян с шзеьт щсзз ь» ат нн н. М хеопс ео егегазон р д,вс мггганснз о г чх. г ын и Вернсаа» а ы г ! и — л и(с) — [и[в)+ифтл)+к[т я)+и( „)+ 101 0 +И(т з)1 Заметем, что вращение на угол 0 оставляет иа песте лю. бое раскрашнванне, а следояательно, Н (с) =) Х( =3'=243.
Вращение на угон Зя/5 оставляет ° а мщте раскрашввания, орк 3 которых буснна с номсрщ [ ге окрашена так же, как и г к г г бусапа с номером т'звз ([) 1=1, 2, 3, 4. 5, т. е. если с з х ге =аз=се с,=сз (все ЗУсним ш б) охран сны в один цвет). Оче. видно, чщ возможнм три тв" кик раскрашивания, а значит, р,с.
аа ИЬьш ) =3. Аналогично по. гас мучаем Д((тв зз ) =3, 1 2, 3, 4, н, следовазельио, Дг — (243+ 1 5 -1-4. 3) =283/3= 81. Пример 3.23. Пусть Я=(!. 2, ..., гф — множество номеров элементов некоторой фигуры Ф; )г — кояечное множества цветов, в которые могут быть окрашены элементы фигуры Ф; Х= =((сь ..., с„>)сгш)7, г=1, 2, ..., л) =й — множество раскрашиваний фигуры Ф. Пусть, далее. и — некоторая подстановка из б„(т. с. и; И О). Определим действие подстановки с на произвольное раскрашивавие ссяХ по формуле ос=о<со ..., с >=Со .,(г), ..., с,(„1 >.
(3.27) Выведем бюрмулу для йг(п) — числа раскрашнваняй, астающихси на месте ярн действии на них подстановни и. Разложим о в произведение независимых элементарных циклов о=оь..оз, (3.28) где й — количество циклов (в (3.28) учитываются и все циклы длины 1). Напомним, что каждому элементарному циклу (й гз ...! ) соответствует и-орбнта (гг. 8..... 1 ), и прн этом совокупность всех с-орбит является разбиением множества (1, 2,..., л). Пусть с— некоторое рвскрашнвание фигуры Ф, иоторое остается на месте врн действии на нега подстановк» и.
Для любого цикла пг= = (й Н ... 1 ), входяшего в разложение (3.28), имесм (1*), = (Ч...„= ( ), откуда, используя то обстоятельство, что с=ос, в силу (3.27) получаем с, =с,-,(г =с. =с,;8,1 =с, =...=с,— 821 =сг. * а следовательно, элементы фигуры Ф, входящие в одну и ту жс о-орбиту, должны быть окрашены одинаково. Поскольку о.орбшы попарно не пересекаются, то онн могут быть окрашены независимо друг от друга. Но тогда по правилу произведения 17(,г) ()7(з Пример 3.24. Составляются ожерелья из плоских бусин трех Цветов, окрашенных одинаково с обеих сторон. Каждое ожерелье ~остоит нз пяти бусин. Определим число М различных ожерелий.
По сравнению с примером 322 к группе вращений б фигуры, изображенаой на рис. ЗЗ,а, добавляются осевые преобразования симметрии. у этой фигуры, очевидно, пять осей симметрии: (ь (ь (ь 1». (ь где у1ев(1, 2, 3, 4, б) 1г — орямая, прохаюицая через г-ю бусину и центр окружности, на которой расгюложены бусины в ожерелье.
Тогда, например, преобразова. !о ° 151 нню симметрии относительно оси й соответствует подстановго о, (1)(2 5)(3 4). ИспользУЯ пРимеР 3.23, полУчаем АГ(ог) =Бе=27. Аналогично рассматриваются преобразования сим метрни относительно других осей. Но тогда в силу леммы Берд. сайда имеем йг= — (3'+4 3+5 Зз) =39. 1 10 3.2.Б.
Запас. Производящая фущщия запаса Иноммтео все лтеммк обыкгое е комбннаторнке часы наамнмет колосса. Пусть А — атлас, К вЂ” коммтгзщеное калым с еленина (нанон. мер, кольце ммкочленоз!. а и — отобразсенне нева мгА К. Булем м(к), гре ныА, кззмзать омом элементе о, а оюбрюкекне и — ессоеоа бущмье( сумма весен носк злемектон завеса А нззнззетсл лжнсмодкцай Фуюаркя сомме А к ороско естся Ю(А), т. о и'(А) П м(а!.
аыА Приведем примеры некоторых производящих функцнйг !. Пусть запас — множество всех подмножеств некоторого конечного множества Х, где )Х(=ц Поставим в соотщчсгвне каждому множеству Ущр (Х) все ю (У) =П, где й= ) У) . Так как число й-элементных подмножеств и-элементного множества рав.
вяется Сгю то йх(Р(Х))= 2 Сь.( илн с учетом утверждения 3.!О йг(Р(Х))= 2 С„! =()+!)ц С помощью полученной производящей функции можно выво. дить различные свойства чисел С" Положив, например, 1=), имеем л 2 Сь,=2". г о Заметим далее, что для любых натуральных щ, л выполняется цепочка равенств 2 С,„г П+1) =(1+1) (!+1) = г-о Г-е з-о *-о отнуда получаем тождество Коши Сч г Х С' С" „3=0,!,...,щ+л. 2. Пусть Х вЂ” конечное множество, (Х(=л, а запасом Я является совокупность различных разбиений множества Х на й 1ЗЗ под»щсжеств в предположения, что подмножеспи в квщаою разбвеннн рааюложснм в строго определенном порядке. Псстазкм в соогветствпе каждому раэбненню Хь ....
Х» множества Х (Х, ..., Х ): ю(Хг, ...,Х»)=1 ю(,щ. 1»„„где лг )Хг(, г'=1.2...., д. В этом случае, используя утвержленне 3.10. лля вронзводящей функкнн запаса А имеем бт(Д)= Х С ". "Г 1„" =(1+ +П)" ж+..+ * откуда, полагая, накрнмер, Г,=... П=!, позучаем тождество Е Сз,,з, д ю.~....+и =з 3. Пусть Х= (кь ..., х ]. Поставим в соответствие пронзвсльгюб неупорядоченной выборке с повторенняын абьема 2 нз множества Х вес Р.
Пусть также для «аждаго помере (ев(1, 2, ...,. л) имеются ограннчсння ва чнсло повторений элемента хг в вы.- борке, задаваемые рядом 2 сгг(г, г» гг „, 11. еслн в щэбарку могут еойтн ровно)элементов хо где оп= ] ] 0 — в противном случае. Очевгглва, что производящая функняя запаса воск допустимых сочетаний с повторениями равняется П 2 с»ПЩ 1» Напрпмер, еслн в вмборке допуспгма не более чем двукратное.
псвторепне каждого элемента хь то пронзвадяпгая фупккня яме= ет внд (1+1+С)д 3.2.0. Цякловой нгщекс группы, щйствующей на множестве Пусть С вЂ” кощчнзя группа. Х вЂ” «онечвое множество, где ]Х) = л. Пусть также т — аекоторая реалнзаппя группы С в 5(Х), определяющая действие группы С кз множестве Х (т. е. авда. ющая отображение (б, х) бх прямого пронзведеяия С)(Л в К, удовлетворяющее (3.19], (3 20)). для любого элемента бщС обозначим через (»(2) количество пеплов,»ляпы й' в раз- лсскепнп подстановка ещб(Х) в пРонзведенне незавнснмых 1ЭМ элеыентарных циклов, где 3=1, 2, ..., л.
Каждому элементу .Сена подставим в соответствие вес ыо(3)=<Р<г> 1,1 1а! <„1 <и> <З.а) (т. е. элемент кольца 2(<!.... !3). Тогда циклаиоа инде!с Р (6, Х, <!. - < ) группы 6, действующей на Х. есть многочлен от переменных 0, ..., <, определяемый формулой Р<С. Х. ть..., ! > ,<к> ' дч) г, 0(з> „п<5> 1„1.<д> <330) !'1аыа ' !'1ажб ' Пример 3.25. Пусть Х=(1, 2, ..., 10), 6 — группа, лействую. эцая на Х, и для некоторого элемента йща выполпясгся равен.
ство <1 З З ! 5 Е У З Э <О> те=<э а 1 з а 2 у!о 3 4!К Определим вес ы(й) по формуле (3 н). Имеем тт= = (193) (25) (4810) (5) (7), откуда еэо(й)=!!э<э!<ээ<эо., <!ос= = !ее<э<ее. Пример 3.2б. Пусть 6 — группа вращений на плоскости фигуры Ф (рпс. 3.7) вокруг центра этой фигуры, совмещающих ее с самой собой, Х (1, 2, 3, 4, 5) — мпожсст!ю номеров элементов фигуры. При 1 2 этом (как и в примере 3.22) под компо- зицией иО3 двук произвольных враще- 5 ний еь йеыа будем понимать враже. ние, являющееся результатом лослсдователыю применяемых к фигуре <р вращеняй р, о !(т. е.
сначала выполняется прищепке !>, а затем к полученной в результате вращения (> фигуре применяется вращение о). Очевидно, что группа 6 <чж. Зг состоит из четырех элементов — враще. ний (против часовой стрелки) ма углы лэп74, э=б, 1, 2, 3. Обозначим элементы группы 6 величинами соответствующих углов. Поставим в саотвпгствие каждому вращению вша подстановку т,щ5 (Х) =5э такую, что для любого !тщХ т. <П будет номером 1-го элемента фигуры, полученной в результате вращения о, относительно нсхолного положения фигуры. Тогда то=с, т„п = (1 4 3 2)(5), т, — (! 3)[2 4)[5).
'э л= (1 2 3 4)(5). Заметим, по по о ределеыао щнпоэнина зраженнд О и отоараженни Е, ГРГПИМ б Е 5 Мнспиастеа ЮО, РЫС еэр т р. ОтКУДЕ СЛСДУС, 'етс опбраже не т:б 5о ст илиме со стет «л ло у элеммет> аыб поле ано «у т ы5, неэ ется гоном э)нэпом, т. а т — реллнэаж я труним С е 5(Х>. Прн этом е со тестстенн с (ааа> ннк оеоа имденс !руины б, деужтеумыеа еэ миожестпе Х. реево 1 ! Р<а, Х Ге ! а, а.а> — д' МО<з> — <М <О>+М <Н<т>+М 00+ !б! а !154 1 1 + М, (ЭПЕ»]] - — Р;+ГГ,+Ггй+ГГ) — ФЕЬ Ытстттр].
(3.3]У 3.2.7. 6-эквивалентные отображения Предположим, что сохраняются условия, описанные в равд. 3.2.б. Пусть, далее, ]2 — неиоторое коцечяае множество. Две фунюшю /к/тшйл будем называть О-эквивалентными и обозначать/г /в, если Я»ш(й УхщХ /, (х) =/т(йх), илп, что то же самое, соки Яйшбт УхепХ /г (х) /т (й 'х].
Очевидна, что введенное бинарное отношение на множестве Егд является эквнвплеитностью, а следовательно, оио поождает разбиение множества 1Р иа классы эквивалентности ш]ел/-. Пуст нвмдому клементу гмп предан иммтормй вес и (]ма; где К вЂ” паина мнсгочленов нкд П от иеиоюрмх пеосменнмх. Тоглв псс фумммг (мГ" есть, о оиредсмипм, м(/) П м Ц(к)].
полн /, /ь то оче мпм, «м» что мр] м(й], постону конно опредслкть мс класса тквнввлектпомн а(Е). где Емп 1/м «вк «и Ф) юнаш момента /мЕ. Прамер 3.27. Пусть ]с= (красный, голубой) — множество шмтов, Х= (1, 2, 3, 4, б) — множества элементов фигуры Ф, рассмотренной в примере 3.26. Тогда любое отображение /:»-ь](' можно рассматрввать как раскрашивание элементов фигуры Ф е паста нз ](. Прндаднм красному цвету вес а, а голубому— все Ь (замстим, чта а, Ь вЂ” клементы мальца 2(а, Ь)). Тогда„ например, любое раснрашиваине / такое, что два элемента фигуры Ф окрашены в красный цвет, а остальные три элемснта— и голубой, имеет вес и (/) =а'ЬЦ Пусть далее нв множестве Х действует группа О, взятая из примера 3.23.
Тогда в соответствии с введенным выше определением раскрашивания /„ /, являются эквивалентными, если Защб: Инп» /г(1)=/т(а-и), т. е. если найдется такое вращение ашб, что при совмещении фигуры Ф с раскрагниванием /, с фигурой, получаемой из фшуры Ф с раскрашиванием /, вращением на угол а (против чвсо- а/ рис. 55 155 вой стрелки), совмещенные друг с другом элементы будут ог.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
