новая папка 1 / 287765

Выведем формулу для числа N(s) раскрашиваний, остающихся на месте при действии s. Разложим подстановку s в произведение независимых циклов: s = s1 ::: sk, причем учитываются и циклы длины 1. Каждому циклу (i1; :::; il) соответствует hsi-орбита fi1; :::; ilg, и при этом совокупность всех hsi-ор- бит является разбиением множества M. Пусть f некоторое раскрашивание фигуры W, которое сохраняется при действии на него подстановки s. Как легко понять, для любого цик-

ла sj = (i1; :::; il) имеем f(i1) = f(i2) = ::: = f(il). Поскольку
h	s	быть окрашены неза-
		i-орбиты не пересекаются, они могут	k	.
висимо друг от друга, а тогда N(s) = jRj
		Пример 6.2. Вычислим, сколькими способами можно рас-

красить вершины правильного тетраэдра в q различных цветов. Группа G движений правильного тетраэдра найдена в примере 4.5. Эта группа действует на множестве f1; 2; 3; 4g вершин тетраэдра и состоит в точности из четных подстановок. Она содержит элемент e = (1)(2)(3)(4), восемь элементов ви-

да s = (1)(234) и три элемента вида t = (12)(34). Согласно доказанному выше имеем N(e) = q4; N(s) = q2; N(t) = q2. Теперь

можно применить лемму Бернсайда, и мы получаем формулу для числа N раскрашиваний:

1					q2
N =		(q4	+ 8q2	+ 3q2) =		(q2	+ 11):	(6:2)
12				12

Решенную задачу можно трактовать таким образом: имеются атомы q различных элементов. Молекула вещества состоит из четырех атомов, расположенных в вершинах правильного тетраэдра. Сколько может существовать различных типов молекул, составленных из атомов данных элементов? Ответ дает формула (6.2).

7. ТЕОРЕМА ПОЙА

Цикловой индекс группы. Пусть M конечное множество, jMj = n и G конечная группа, действующая на M. Эту группу можно отождествить с некоторой подгруппой в Sn.

Для любого элемента g 2 G обозначим через jk(g) число циклов длины k в разложении подстановки g в произведение

21

независимых циклов. Каждому элементу g 2 Sn поставим в соответствие вес

wG(g) = tj11(g) ::: tjnn(g):

Это многочлен от переменных t1; :::; tn с целыми коэффициентами. Цикловым индексом группы G, действующей на M, называют многочлен P (G; M; t1; :::; tn), определяемый формулой

P (M; G; t1; :::; tn) =	1	X	wG(g) =	1	X	t1j1(g)
	jGj g2G			jGj g2G

::: tjnn(g):

Пример 7.1. Пусть G группа движений правильной четырехугольной пирамиды (см. пример 4.3). Как мы знаем,

G C циклическая группа порядка 4, порожденная поворо-

= 4

том s на угол p=2. При отождествлении G с подгруппой в S5

имеем s = (1)(2345), s2 = (1)(24)(35); s3 = (1)(2543). Цикловой индекс группы, действующей на множестве M = f1; 2; 3; 4; 5g вершин пирамиды, равен

1 X

P (M; G; t1; t2; t3; t4; t5) = jGj g2G wG(g) =

= 14(wG(e) + wG(s) + wG(s2) + wG(s3)) =

= 14(t51 + t1t4 + t1t22 + t1t4) = 14(t51 + t1t22 + 2t1t4):

Запас. Производящая функция запаса. Множество исследуемых объектов в комбинаторике часто называют запасом. Пусть Z запас. Поставим в соответствие каждому z 2 Z многочлен w(z) от нескольких переменных с целыми коэффициентами. Будем называть многочлен w(z) весом элемента a. Сумму весов всех элементов запаса называют производящей функцией запаса Z и обозначают через W (Z), т. е.

X

W (Z) = w(z):

z2Z

Пусть R еще одно конечное множество. На множестве RM функций f : M ! R действует группа G, как объяснялось в примере 5.3. Рассматривая M как множество элементов некоторой фигуры, а R как множество красок, будем называть

22

такие функции раскрашиваниями. Два раскрашивания назовем эквивалентными, если они эквивалентны относительно действия G, т. е. лежат в одной орбите этой группы, действующей на RM . Обозначим через [RM ] множество классов эквивалентности раскрашиваний.

Пусть каждому элементу y 2 R придан некоторый вес wR(y) многочлен с целыми коэффициентами от фиксированного числа переменных. Тогда вес функции f 2 RM есть, по определению,

Y

w(f) = wR(f(x)):

x2M

Если f1 f2, то, очевидно, w(f1) = w(f2), поэтому можно определить вес класса эквивалентности w(F ), где F 2 [RM ] как вес любого элемента f 2 F .

Пример 7.2. Пусть M = f1; 2; 3; 4; 5g множество вершин правильной четырехугольной пирамиды:

01

23

@ 1 A;

54

R = fr; gg множество цветов. На множестве M действует

группа

G

=

(см. пример 5.1). Раскрашивания

1)

и

2) G

-эк-

C4

вивалентны, раскрашивание 3) им не эквивалентно:

1)

0r

r

r1;

2) 0g

r

r1;

3) 0r

r

g1

:

@g

gA

@g

rA

@g

rA

Положим wR(r) = a, wR(g) = b. Тогда для веса w(f) любого из раскрашиваний 1); 2); 3) и для веса w(F ) любого из сответствующих классов эквивалентности будем иметь

w(F ) = w(f) = a3b2:

Формулировка теоремы Пойа. Пример. Теперь мы можем сформулировать основной результат.

Теорема 7.1 (Пойа). Прозводящая функция запаса классов

23

эквивалентности раскрашиваний удовлетворяет равенству

w(F ) = P	0G; M;	X	wR(y);	(wR(y))2 ; :::; (wR(y))n1		;
X	@		X	X	A
F		y2R	y2R	y2R

где P (G; M; t1; :::; tn) цикловой индекс группы G; действующей на M.

Доказывать эту теорему не будем, рассмотрим только пример ее применения.

Пример 7.3. Обратимся к примерам 7.1 и 7.2. Определим производящую функцию запаса классов эквивалентности раскрашиваний в два цвета. На основании теоремы имеем

X

w(F ) = P (M; G; a + b; a2 + b2; a3 + b3; a4 + b4; a5 + b5) =

F

= 14 (a + b)5 + (a + b)(a2 + b2)2 + 2(a + b)(a4 + b4) =

= a5 + 2a4b + 3a3b2 + 3a2b3 + 2ab4 + b5:

Таким образом, число раскрашиваний, при которых, например, три элемента окрашены в красный цвет и два в зеленый, равно коэффициенту при a3b2, т. е. 3. Общее число раскрашиваний равно сумме всех коэффициентов, т. е. 12.

ДОМАШНЕЕ ЗАДАНИЕ

Дан многогранник W, представляющий собой либо правильную n-угольную призму, либо правильную n-угольную пирамиду, либо правильную n-угольную усеченную пирамиду, либо n-угольный диэдр (фигуру, состоящую из двух одинаковых правильных n-угольных пирамид с общим основанием), либо такой же усеченный диэдр (фигуру, состоящую из двух одинаковых правильных усеченных пирамид с общим большим основанием). Требуется найти:

1)группу G движений многогранника W;

2)цикловой индекс группы G, действующей на множестве M вершин (варианты 1–10), граней (варианты 11–20), ребер (варианты 21–30) многогранника W;

3)число способов раскрашивания элементов множества M

втри цвета;

4)производящую функцию запаса классов эквивалентности раскрашиваний, если используются два цвета.

Данные для каждого варианта указаны в таблице.

Номер	W	n		Номер	W	n
варианта				варианта
1, 11, 21	Призма	3		6, 16, 26	Диэдр	5
2, 12, 22	Усеченный	3		7, 17, 27	Призма	4
	диэдр				(отличная
					от куба)
3, 13, 23	Диэдр	3		8, 18, 28	Призма	5
4, 14, 24	Усеченная	4		9, 19, 29	Усеченная	5
	пирамида				пирамида
5, 15, 25	Пирамида	6		10, 20, 30	Диэдр	4
					(отличный
					от правильного
					октаэдра)

ЛИТЕРАТУРА

1. Кострикин А.И. Основы алгебры. М.: Изд-во МЦНМО, 2009.

2.Курош А.Г. Курс высшей алгебры. СПб.: Лань, 2007.

3.Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: Изд-во МАИ, 1992.

	ОГЛАВЛЕНИЕ
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		3
1.	Множества и отображения . . . . . . . . . . . . . . . . . . .	3
2.	Понятие группы . . . . . . . . . . . . . . . . . . . . . . . .	10

3.Теорема Лагранжа . . . . . . . . . . . . . . . . . . . . . . . 14

4.Группы движений . . . . . . . . . . . . . . . . . . . . . . . . 15

5.Действие группы на множестве . . . . . . . . . . . . . . . . 17

6.Лемма Бернсайда . . . . . . . . . . . . . . . . . . . . . . . 19

7.Теорема Пойа . . . . . . . . . . . . . . . . . . . . . . . . 21

Домашнее задание . . . . . . . . . . . . . . . . . . . . . . . .	25
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	26

ДЛЯ ЗАМЕТОК