7.9. Теория перечисления Пойа.

219

На D действует группа самосовмещешгй G= /с, а, а2}, где е={\ 2 3) ~~ тождественное совмещение, а j fj~поворотво-

круг оси на 120°, а2 ={ \ ? \ j — поворот на 240°.

Q = {х, у, х~1, у~1 и их произведения}— множество весов. S = VI/D-+R} — множество раскрасок. В треугольнике три вершины и каждую допускается окрашивать в любой из двух цветов R = {•> °}> следовательно, всего функций 23. Такое количество раскрасок будет, если треугольник сделать неподвижным (рис. 7.4). Если допустить вращение, то различные раскраски неподвижного треугольника становятся одинаковыми для вращающегося треугольника. Приведем пример трех раскрасок: f\,f2,fy /i : D -> Л,/3:Л-+Л,

ЛЦ) = »,fiidy)—,/]Ц) = =,

/i(rf2) = *,/2(2) = °.&«=»i

/,№) = ,/3<tf3> = °./з(з) = °-

*44

Очевидно, что для решаемой задачи раскраска/2 и/3 совпадают.

Назначим краскам Я = {♦, с} веса: -х и ш(°) =у.

• Замечание. Отметим, что назначенные веса элементов =х и ю (о) =у позволяют сравнивать признаки количественно, забывая, в какой— то степени, о качественном их содержании.

- Определение. Для каждой функции/еЖ определим вес

W(f)=\\<b(f{d)).

В нашем примере= ш(»М»)и>(о) =хху = х у,

W(/3 ) =ш(о)ю(.){о(о) =ху =хк2-

Определение. Группа G- действуя на Д индуцирует (наводит, создает, определяет) свое действие на множество функций S. Положим V/ еS Vg e.G gf=f(g{d)) это рассматривается

В нашем примере рассмотрим действие элемента а е G на fz zS.

f2(a2(dx))=f2(d3) = ° и./) = ",

АИШвШ** И /3(> = °-

Таким образом, элемент группы а переводит в/3 или, в принятых обозначениях, a2f2=f.

•Определение. Положим ft ~/2, если 3g е G VdeD fx(gd) = f2(d), Такие fx и /2 определяют одинаковые раскраски элементов rfe D.

Введенная эквивалентность функций есть от-

Аношение эквивалентности, которое порождает разбиение множества элементов/е S на непересекающиеся классы эквивалентности (рис. 7.5): * ... SKe S = SlvjSl...SNo,TyflJ2eSfl3g5Ggfx=f1 Рис. 7.5 И eSa eSV VgeGgfx*f2,S0*Sp, NG--количество классов эквивалентности. Каждый класс эквивалентности определяет отдельную раскраску элементов e D. Таким образом, количество различных раскрасок равно NG. Для определения NG воспользуемся леммой

7.7.1 Бернсайда: NG = г\- TJ\.\i(g) в данном случае

щт

y(g) = {fe S\gf=fwmf(gc=Ad)Vd е D).

Вернемся к нашему примеру на рис. 7.4 и найдем для него число NG. ц>(е) = {fe S\ е/=/удовлетворяют все/е S, откуда \ц/(е)\ = = 23 = 8. ч>(а) = {fe S\af=f)- это такие раскраски/вершин, которые допускают совмещение с эквивалентной из раскрасок вращением треугольника на 120°. Это возможно, если все вершины либо белые, либо черные. Итак, у(я) = 2. Подобным образом устанавливается, что и v(a2) = 2. Следовательно, NG =i(S + 2 + 2)=4.

•Утверждение 7.9.1. Если fx ~/2, то W{fx)=W(fl) ,т.е. эквивалентные функции имеют одинаковые веса. Доказателъство. D = {dx,d2, d3,...} и D - {gdxgd2, gd3,...} — верно e G, так как G действует на D и g j— это

L?tfi #<ъ s«i • i

7.9. Теория перечисления Пойа

221

подстановка. Теперь W(fl¥Yla<fi(d)) = IKfi(Sd))- Имеем

deDdeD

fx ~ f2. тогда G Vd e DnWgd)) -- v>{f2{dj). Отсюда

•Определение. Последнее утверждение позволяет определить вес каждого класса эквивалентности в разложении S - S{u

vjS2kj. . .u%, как W\S) = W(f)me / e I•. Определение корректно, так как каждый класс .У, состоит из эквивалентных функций f веса которых совпадают.

•Теорема 7.9.1 Пойа. £СШ • ra = Z(G,.K(ra1),ra2),...,ram)), где

число классов эквивалентности S = Sx и S2kj. . .uSN( с весом га e Q, Z{G,xl ,Х22,...,хтт ) — цикловой индекс группы G, действующей на множестве D={db db..., dm}. Отметим, что

гаеП

Доказательство. Пусть «А»- разбиение множества D на непересекающиеся подмножества:

D=Dn+Dn+...+Dlk +D2l +D22+...+D2ki+...+Dml+Dm2+...+Dmkm, ,-,-1- >.-v- -—-----

*,кгkm

где = \d = m, 1 • + 2- +... + т • =

Определение. Говорят,что/е подчинена разбиению«Д» множества Dи записывают/е Д. если/постоянна на каждом подмножестве Dy из разбиения: е Dy Ad) = гу, где ry е R. Функция/, подчиненная разбиению «Д», взаимно однозначно определяется набором (rnr12.. .rlkr21r22. .г2кг.. .rmlrm2. .гткт), где

Все такие наборы составляют множество:

S = SnxSi2x...xSlki xS2lxS22x...xS2k2X...xSml xSm2x..xSmkiii ,

> -v-1 --v--Si-

где Sy - R, i = l,m,j = l,kj. Полагая веса элементов Sy e равными (a(sy) = [ю(гу)]пвесs= (S[lsl2...slks2ls22...s2k2...smlsm2...smkJ 6 S