Применение леммы Бернсайда к решению комбинаторных задач

Государственное образовательное учреждение

высшего профессионального образования

Санкт-Петербургский государственный

технологический институт

(Технический университет)

 

Кафедра Экономики и                           Факультет Экономики и                    

               логистики                                                менеджмента

 

Курс     2                                                               Группа __9991____

 

Учебная дисциплина: КОМБИНАТОРИКА

 

 

КУРСОВАЯ РАБОТА

 

 

 

Тема: “Применение леммы Бернсайда

к решению комбинаторных задач.”

 

 

Студент                          Личная подпись                               Антонова М.А.

 

Руководитель                Личная подпись                Халимон  В. И

 

Оценка

за курсовую работу ___________  Личная подпись руководителя_______________

 

 

 

 

Санкт-Петербург

2011

 

Содержание:

Введение...............................................................................................3

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

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

3.Задачи о раскрасках.........................................................................7

      3.1. Задача  о бусах.........................................................................7

     3.2. Группа вращений  куба.........................................................11

4. Заключение....................................................................................15

5. Список литературы.......................................................................16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

Комбинаторные задачи о количестве объектов, не совмещаемых друг с другом определенными преобразованиями, которые решаются с помощью Леммы Бернсайда, являются наиболее простым приложением теории групп. Не надо думать, что теория групп специализируется на решении комбинаторных задач. Различные приложения теории групп в современной науке (в других разделах математики, в физике, в химии, в информатике) настолько же разнообразны насколько и недоступны после полусеместрового курса.

Группы — один из основных типов алгебраических систем, а теория групп — один из основных разделов современной алгебры. Понадобилась работа нескольких поколений математиков, занявшая в общей сложности около ста лет, прежде чем идея группы выкристаллизовалась с ее сегодняшней ясностью. От Лагранжа, стихийно применявшего группы подстановок для решения алгебраических уравнений в радикалах (1771), через работы Руффини (1799) и Абеля (1824) к Эваристу Галуа, в работах которого (1830) уже достаточно сознательно используется идея группы (им же впервые введен и сам термин),— вот путь, по которому развивалась эта идея в рамках теории алгебраических уравнений.

 

 

 

3

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

 

Пусть G - группа с нейтральным элементом е, а Х - множество. Группа G действует на множестве Х, если задана операция обозначаемое (g,х) = gх, такое что:

1. (g,h)х = g(hх) для всех g, h G, х M

2. eх = х, где e есть единица G.

Введем теперь некоторые понятия, связанные с действием группы G на множестве X , которые используются в формулировке и доказательстве леммы Бернсайда.

Орбитой элемента x ∈ X под действием G называется множество Gx = {gx | g ∈ G}.                         Количество элементов в данной орбите называется    длиной орбиты (в разных орбитах может быть разное количество элементов). Любые две орбиты либо не пересекаются, либо совпадают. Таким образом, множество X  разбивается в дизъюнктное объединение орбит. Неподвижными точками элемента g ∈ G называются те x ∈ X , для которых gx = x. Множество неподвижных точек элемента g обозначается через X g . Множество элементов группы G, оставляющих на месте данный элемент x ∈ X называется стабилизатором элемента x и обозначается через St(x). Другими словами, St(x) = {g ∈ G | gx = x}. Очевидно, что стабилизатор является подгруппой в G.

 

4

Количество пар (g, x), для которых gx = x можно вычислить двумя способами, которые указаны в разных частях следующего уравнения:

  ,где

Последнее равенство играет большую роль при доказательстве леммы Бернсайда. Второе ключевое соображение приведено в следующей лемме:

Лемма: Длина орбиты элемента x равна индексу стабилизатора этого элемента.

Поэтому, если группа G конечна, то |Gx| · | St(x)| = |G|.

Доказательство:

Индекс подгруппы - это количество смежных классов по этой подгруппе. Пусть G/ St(x) обозначает множество смежных классов. Зададим функцию f : G/ St(x) Gx формулой f gSt(x)=gx и докажем, что  f биективна. Сюръективность сразу следует из определения орбиты. Предположим, что f gSt(x) = f hSt(x), т.е.

gx=hx. Но тогда gx=x, откуда gx, а из этого сразу следует, что gSt(x) = hSt(x). Таким образом f биективно отображает G/ St(x) на Gx, а это возможно только если:

 .

 

 

 

 

 

 

 

5

 

2. Лемма Бернсайда.

 

 

Лемма Бернсайда вычисляет количество орбит действия группы на множестве с помощью суммы по всем элементам группы. Она применяется в том случае, когда порядок множества Х намного больше . чем порядок группы G.

Лемма: Пусть G - конечная группа, действующая на множестве Х. Для любого элемента g из G будем обозначать через множество элементов Х, оставляемых на месте g.

 

Число орбит равно среднему количеству точек, оставляемых на месте элементов из G.

Доказательство основано на подсчёте числа элементов одного множества двумя способами:

 

 

 

6

 

3. Задачи о раскрасках.

3.1 Задача о бусах.

Пусть I – произвольное множество, а C – множество цветов. Рас- краской множества I называется функция из I в C . Множество всех раскрасок обозначается через C I

Пусть G группа, действующая на множестве I . Тогда формула gf(i) = f(i) где , задает действие G на .

Вычислить количество различных бус из 6 бусинок, каждая из которых может быть одного из трех цветов.

 

Решение.  Уточним условие. Под различными бусами подразумеваются те, которые нельзя совместить друг с другом с помощью поворотов и осевой симметрии. Занумеруем места для бусинок числами от 1 до 6, а цвета – буквами a, b, c. Тогда раскраска – это сопоставление конкретного цвета каждому из мест, т. е.  последовательность

{x1, x2 , x3, x4, x5, x6}, где xk  ∈ {a, b, c}. Очевидно, что всего существует 36 таких раскрасок.  Естественно, не все раскраски соответствуют различным бусам. Например

раскраска, в которой первая бусинка имеет цвет b, а остальные – цвет c, совмещается поворотом с раскраской, у которой вторая бусинка имеет цвет b, а остальные – цвет c.

На множестве X всех раскрасок действует группа поворотов и осевых симметрий. Операция в этой группе –

7

композиция, т. е. последовательное выполнение преобразований (композиция поворота и осевой симметрии равна осевой симметрии относительно другой оси, а композиция двух симметрий относительно различных осей равна повороту). Как обычно, операция композиции  является ассоциативной, ней- тральным элементом является тождественное отображение, обратным к осевой симметрии является она сама, а обратным к повороту – поворот в обратную сторону. Обозначим эту группу буквой G.

Группа G естественным образом действует на множестве мест {1, 2, 3, 4, 5, 6}, то есть задано отображение из G в симметрическую группу S6. Обозначим через τ поворот, переводящий каждое место в следующее (последнее в первое), а через σ – осевую симметрию  относительно оси, проходящей между местами 6 и 1, и 3 и 4. Выпишем перестановки (в циклической форме) из S6, в которые переходит каждый из элементов группы G.

Элемент	e	τ	τ 2	τ 3	τ 4	τ 5
Перест.	e	(123456)	(135)(246)	(14)(25)(46)	(153)(264)	(654321)

Элемент	σ	στ	στ 2	στ 3	στ 4	στ 5
Перест.	(16)(25)(34)	(15)(24)	(14)(23)(56)	(13)(46)	(12)(36)(45)	(26)(35)

 

Далее мы будем отождествлять преобразования с соответствующими им перестановками. Теперь легко задать формулой действие элементов группы G на множестве X :

 

 

8

α(x1 , x2, x3 , x4, x5, x6) = (xα−1 (1) , xα−1 (2) , xα−1 (3) , xα−1 (4) , xα−1 (5), xα−1 (6) ). Например цвет второй бусинки после поворота τ (т. е. поворота бус на 60◦) совпадает с цветом первой бусинки до поворота (τ (1) = 2, поэтому

τ −1(2) = 1).

Раскраски, совмещаемые друг с другом каким-нибудь преобразованием из группы G задают одинаковые бусы. Раскраски задают одинаковые бусы тогда и только тогда, когда они лежат в одной орбите под действием G.  Таким образом, задача состоит в том, чтобы вычислить количество орбит действия G на X .

Для того, чтобы воспользоваться леммой Бернсайда, необходимо выяснить, сколько элементов множества X оставляет на месте каждый  элемент группы G. Очевидно,

|X e | = |X | = 36 . Так как поворот τ переводит друг в друга соседние элементы, то у раскраски, не изменяющейся при этом повороте, любые две соседних бусинки должны

иметь один и тот же цвет. Отсюда следует, что все бусинки такой раскраски имеют один цвет, откуда |X τ | = 3. То же рассуждение относится и к элементу τ 5, следовательно

  |(X^ τ)^ 5 | = 3

В общем случае, те бусинки, которые элемент группы переставляет по циклу, имеют один и тот же цвет тогда и только тогда, когда элемент группы сохраняет раскраску. Поэтому количество цветов, которые надо выбрать для получения раскраски, сохраняемой элементом группы, равно

9

количеству независимых циклов в перестановке, соответствующей этому элементу (при этом учитываются циклы длины 1, которые не выписаны в таблице 1). Для элемента α ∈ G обозначим это число через c(α). Так

как по условию бусинки можно красить в один из трех цветов, то c(α) цветов можно выбрать 3c(α) способами. Таким образом, 3c(α) – это и есть количество раскрасок, не меняющихся под действием элемента α. Получим:

 

 

 

  

Наконец, по лемме Бернсайда количество различных бус (число орбит) равно:

 

 

 

 

 

 

 

 

 

 

 

 

10

 

3.2 Группа  вращений куба

 

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

Известно (принимаем это без доказательства), что вращение куба однозначно определяется перестановкой его больших диагоналей, и каждая перестановка диагоналей реализуется каким-то вращением. Так как у куба 4 больших диагоналей, то сказанное выше означает, что группа вращений куба изоморфна симметрической группе S4 . Для решения задач про раскраску вершин (граней, ребер) куба необходимо реализовать эту группу в группе перестановок вершин (граней, ребер), т.е. в группа S8 (соответственно, S6 , S12 ). Частично эта задача и решена в приведенной ниже таблице. Для построения таблицы введем обозначения для вершин, больших диагоналей, граней и ребер куба A1A2A3A4 A5A6A7 A8.

 

 

 

 

 

 

11

Обозначим большие диагонали как:

d1 = A1A7,  d2 = A2A8,  d3 = A3A5 ,  d4 = A4 A6;

Грани:

f1 = A1A2A3 A4,  f2 = A1A2 A6A5,  f3 = A2A3 A7A6,

f4 = A3A4A8 A7,  f5 = A4A1 A5A8,  f6 = A1A2 A3A4;

И ребра:

e1 = A1 A2,	e2 = A2A3,		e3 = A3A4,		e4 = A4A1,
e7 = A3 A7,	e8 = A4A8,		e9 = A5A6,		e10 = A6A7,
e4  = A4A1,		e5  = A1A5,		e6  = A2A6,
e10  = A6A7,		e11  = A7A8,		e12  = A8A5.

 

В следующей таблице все перестановки  записаны в циклической форме, т.е. (d1d2d3) означает, что данное вращение перемещает диагональ d1   в d2, d2   в d3 , d3   в d1, а d4 оставляет на месте (вращение куба вокруг диагонали d4).

 

S4  (диаг.)	S8  (вершины)	S6( грани)	S12  (ребра)
e	e	e	e
(d1 d2 ) (d1 d3 ) (d1 d4 ) (d2 d3 ) (d2 d4 ) (d3 d4 )	(A1A2)(A7A8)(A4A6)(A3A5) (A1A5)(A3A7)(A4A6)(A2A8) (A1A4)(A7A6)(A2A8)(A3A5) (A2A3)(A5A8)(A4A6)(A1A7) (A2A6)(A4A8)(A3A5)(A1A7) (A3A4)(A5A6)(A2A8)(A1A7)	(f1f2 )(f3 f5)(f4f6) (f1f6 )(f2 f5)(f3f4) (f1f5 )(f2 f4)(f3f6) (f1f3 )(f2 f4)(f5f6) (f1f6 )(f2 f3)(f4f5) (f1f4 )(f3 f5)(f2f6)	(e2e5)(e3e9)(e4 e6)(e7 e12) (e8e10 ) (e1e12 )(e2 e11 ) (e3e10 )(e4e9)(e6e8) (e1e8)(e2e12 )(e3 e5 )(e6e11 ) (e7e9) (e1e7)(e3e6)(e4 e10 ) (e5e11 )(e8e9) (e1e10 )(e2 e9) (e3 e12 )(e4e11 )(e5e7) (e1e11 )(e2 e8)(e4 e7 )(e5e10 ) (e6e12 )
(d1 d2 )(d3d4) (d1 d3 )(d2d4) (d1 d4 )(d2d3)
(d1 d2 d3 ) (d1 d3 d2 ) (d1 d2 d4 ) (d1d4d2) (d1d3d4) (d1d4d3) (d2d3d4) (d2d4d3)			σ
(d1d2d3d4) (d1d4d3d2) (d1d3d2d4) (d1d4d2d3) (d1d2d4d3) (d1d3d4d2)			τ

 

Все остальные клетки легко заполнить без всякого пространственного воображения, картинки куба и т.п. Достаточно просто уметь перемножать перестановки. Например, для того чтобы заполнить клетку с буквой σ достаточно разложить перестановку (d1d2d3) в произведение транспозиций (d1d2d3) = (d1 d2 )(d2d3), после чего перемножить перестановки, стоящие в соответствующих местах последнего столбца:

σ = (e2e5)(e3e9)(e4 e6)(e7 e12 )(e8e10 ) · (e1 e7)(e3 e6) (e4e10 )(e5e11 )(e8 e9) =(e1e12 e7)(e2e5e11 )(e3e4e8) (e6e9e10 ).

 

Для примера найдем еще перестановку τ . Так как (d1d2d3d4) = (d1d2d3)(d3 d4 ), то

 

τ = σ · (e1e11 )(e2 e8)(e4 e7)(e5e10 )(e6e12 ) =

 = (e1e2 e3e4)(e5e6e7e8 )(e9e10 e11 e12 ).

Данное правило  заполнения таблицы  построено на следующем соображении.

Представление группы G вращений  куба в группах Sn несомненно является гомоморфизмом αk   : G → Sn , так как последовательному выполнению вращений очевидно