4. Решить задачу о «счастливых билетах».

Дипломная работа состоит из четырёх частей:

В § 1 рассмотрена связь теории групп с комбинаторикой: применение группы перестановок к решению комбинаторных задач. Основной используемый факт в этом параграфе – лемма Бернсайда.

В § 2 показан наиболее общий метод пересчёта (известный ещё в XVIII веке), а также приведены примеры его использования в теории чисел.

Параграф 3 посвящён вопросу комбинаторной геометрии – вопросу о разбиении фигуры на несколько меньших частей. Рассмотренная теорема Борсука является тем стержнем, вокруг которого возможно дальнейшее рассмотрение этого вопроса.

В § 4 решается известная задача о счастливых билетах с привлечением методов из математического анализа.

§ 1. Применение леммы Бернсайда к решению комбинаторных задач [3]

1.1. Орбиты группы перестановок

Пусть G – группа перестановок на множестве М={1, 2, …, n } . Подмножество ОМ называется орбитой группы G , если: а) α( a ) O для любого α G и любого a O , то есть действие перестановок изG на элементы О не выводит за пределы О ; б) любые два элемента из О можно перевести друг в друга некоторой перестановкой из G .

Легко показать, что всякая группа перестановок G ={ ε = α ₀ , α ₁ , …, α_{k -1} } имеет орбиты.

Орбитами подобного вида исчерпываются все типы орбит, то есть, если О – орбита группы G и аО, то О=О(а).

Любые две орбиты О(а) и О( b ) либо совпадают (если b O ( a )), либо не пересекаются (если bO ( a )).

Таким образом, множество М распадается в объединение непересекающихся подмножеств – орбит группы G . В связи с разбиением множества М на орбиты группы перестановок G возникают следующие два вопроса:

1) Сколько орбит имеет группа G на множестве М ?

2) Какова длина каждой из этих орбит, то есть из скольких элементов они состоят?

Ответим на эти вопросы.

1.2. Длина орбиты группы перестановок. Лемма Бернсайда

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

Длина орбиты О(а) равна индексу стабилизатора G_a в группе G , то есть | O ( a )|= | G |:| G_a |.

Доказательство. Пусть G ={ ε = α ₀ , α ₁ , …, α_{k -1} }, G_a ={ε=β₀ , β₁ , …, β _{s -1} }. Для подсчёта различных элементов в последовательности a =α₀ ( a ), α₁ ( a ), …, α _{k -1} ( a ) удобно особым образом расположить в ряд элементы группы G . Для этого используем тот факт, что группу G можно представить в виде объединения всевозможных непересекающихся правых классов смежности по подгруппе G_a , имеющих одинаковое число элементов. То есть существуют перестановки γ₀ =ε, γ₁ , …, γ _{l -1} из группы G такие, что все перестановки ряда

α ₀₌ β₀ ° γ₀ = ε, α ₁ = β₁ ° γ₀ , …, α _{s -1} = β _{s -1} ° γ₀ ,

α_{s =} β₀ ° γ₁ , α_{s +1} = β₁ ° γ₁ , …, α_{2 s -1} = β _{s -1} ° γ₁ , (*)

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

α_(l-1)s= β ₀ ° γ _l-1 , α_(l-1)s+1 = β ₁ ° γ _l-1 , …, α _ls-1 = β _s-1 ° γ _l-1

попарно различны и исчерпывают всю группу G .

Для любого i =0, …, l -1 применение s перестановок α _is , α _{is +1} , …, α_{( i +1) s -1} , образующих i -тую строку таблицы (*), к элементу а даёт один и тот же элемент γ _i (а) (так как β₀ , β₁ , …, β _{s -1} оставляют а неподвижным). Все l элементов γ _i (а) попарно различны. Действительно, если бы γ _i (а)=γ _j (а) для некоторых i , j , то а=(γ _j ° γ _i ^-1 ) ( a ) , то есть перестановка (γ _j ° γ _i ^-1 ) G_a . Но это возможно только тогда, когда γ _i и γ _j содержатся в одном правом классе смежности группы G по подгруппе G_a , чего быть не может. Таким образом, длина орбиты О(а) равна l , то есть числу строк в таблице (*): k = l ∙ s (то есть l является индексом подгруппы в группе). По теореме Лагранжа l =| G |:| G_a |, то есть | O ( a )|= | G |:| G_a |. Теорема доказана.

Теперь ответим на первый вопрос. Для этого сформулируем и докажем лемму Бернсайда.

Пусть λ(α) – число неподвижных точек перестановки α , t ( G ) – число орбит группы перестановок G ={ ε = α ₀ , α ₁ , …, α_{k -1} }, действующей на множестве М={1, 2, …, n }. Тогда для любой группы перестановок имеет место равенство:

t ( G )=λ(α), где α G .

Доказательство. Рассмотрим отношение «перестановка α сохраняет неподвижным элемент m » между перестановками группы G и элементами множества М . Сопоставим парам ( α , m ) , α G ,m M , вершины прямоугольной сети и отметим те из них, для которых соответствующая пара ( α , m ) находится в указанном отношении, то есть α( m )= m (рис. 1).

Иными словами, построим график указанного отношения.