Лемма Бёрнсайда и задача об ожерельях

Уильям Бёрнсайд

Уильям Бёрнсайд

Недавно натолкнулась на интересную комбинаторную задачу, которая, как выяснилось, имеет отношение к разным проблемам в разных разделах математики, причем не только математики.

Задача. Сколько существует различных ожерелий, составленных из n красных и m синих бусин? (Считается, что два ожерелья одинаковы, если одно можно получить из другого поворотом.)

Эта задача решается с помощью леммы Бернсайда, которая позволяет получить и множество других интересных результатов.

Сначала немного истории. Уильям Бернсайд (1852–1927) привел доказательство этой леммы в своей книге в 1897 г. Однако выяснилось, что данную формулу знали еще Коши (1845 г.) и Фробениус (1887 г.). Видимо, лемма была настолько хорошо известна, что Бернсайд не указал авторство Коши. Данный результат имеет несколько названий (кроме уже приведенного): лемма Коши — Фробениуса, лемма не Бернсайда (в области теории групп очень многие результаты принадлежат именно Бернсайду).

Для формулировки леммы понадобятся некоторые сведения. Поскольку нас интересует задача об ожерельях, на ее примере и будем все рассматривать.

Обозначим через M множество всех ожерелий. Пусть G — множество всех различных поворотов ожерелий (ясно, что разных поворотов всего n+m). Очевидно, что Gгруппа. При этом каждому ожерелью из M можно сопоставить ожерелье, полученное из него с помощью поворота g\in G. При этом два ожерелья считаются одинаковыми, или эквивалентными, если одно можно перевести в другое каким-либо поворотом из G. Таким образом, все ожерелья разбиваются на классы эквивалентности, или орбиты. Наша задача — найти число различных орбит.

Теперь рассмотрим какой-либо поворот ожерелья. Назовем данный вариант ожерелья неподвижной точкой относительно данного поворота, если после применения этого поворота ожерелье останется прежним в формально (на каждом месте будет находиться бусина того же самого цвета). Обозначим через I(g) количество неподвижных точек поворота g.

Лемма Бернсайда. Количество орбит равно сумме количеств неподвижных точек по всем элементам группы G, деленной на количество элементов в G:

    \[n(G)=\frac{1}{|G|}\sum_{g\in G} I(g).\]

Доказательство леммы Бернсайда (Bogart, Kenneth, 1991). Очевидно, что

    \[\sum_{g\in G}I(g)=\sum_{f\in M}J(f),\]

где f — фиксированный элемент множества M, а J(f) — число различных элементов G, которые переводят f в себя (относительно которых f инвариантен).

Составим таблицу следующим образом. Каждый столбец будет соответствовать одному элементу множества \frak{m}\in M, каждая строка — элементу g\in G. В данном столбце и данной строке стоит элемент из M, в который переходит элемент, соответствующий данному столбцу, при применении к нему элемента из G, соответствующему данной строке.

Пример. Рассмотрим ожерелья из двух красных и двух синих бусин. Перенумеруем их следующим образом: ККСС — 1, КСКС — 2, КССК — 3, СККС — 4, СКСК — 5, ССКК — 6 (существует 6=\frac{4!}{2!2!} перестановок с повторениями из двух элементов, в которых каждый элемент повторяется два раза). Перенумеруем повороты ожерелья: на 0 бусин — 1, на 1 бусину — 2, на 2 бусины — 3, на 3 бусины — 4. Получим следующую таблицу:
Rendered by QuickLaTeX.com

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

Возьмем произвольный элемент f из какого-либо столбца. В своем столбце он встречается J(f) раз — мы так определяли J(f). Значит, и каждый элемент f из любого столбца данного класса в любом столбце встречается столько же раз, а именно J(f) раз.

Таким образом, если мы возьмем по одному столбцу из каждого класса одинаковых столбцов и найдем сумму элементов в них, то получим, с одной стороны, n(G)|G| (умножаем количество столбцов на число элементов в каждом из них), а с другой стороны — сумму величин J(f) по всем f:

    \[n(G)|G|=\sum_{f\in M}J(f),\]

что и требовалось доказать.

Для нашего примера мы имеем два класса столбцов. Во втором и пятом столбцах элементы 2 и 5 повторяются по 2 раза; в остальных столбцах каждый из элементов 1,3,4,6 повторяется по одному разу. Левая и правая части равенства из леммы равны 8.

Ну а теперь мы можем вернуться к нашей задаче.

Если d — общий делитель чисел m и n, то поворот на d бусин не изменяет ожерелья, состоящие из d одинаковых кусков , каждый из которых состоит из (m+n)/d бусин и содержит n/d красных и m/d синих бусин. Поэтому число неподвижных точек для этого поворота равно числу способов расставить эти бусины на (m+n)/d местах, т.е.

    \[{\sf C}_{m+n}^m=\frac{(m+n)!}{m!n!}.\]

Рассмотрим теперь поворот на dk бусин, где k=1,2,\ldots, d. Этот поворот имеет столько же неподвижных точек, сколько и поворот на d бусин, если k и d взаимно просты. Количество чисел, не превосходящих d и взаимно простых с d равно \varphi(d), где \varphi(d)функция Эйлера.

Тем самым, нам нужно найти сумму по всем поворотам, т.е. количество различных ожерелий равно (сумма берется по всем общим делителям m и n)

    \[N=\sum_{d}\varphi(d)\frac{((n+m)/d)!}{(n/d)!(m/d)!}.\]

Для нашего примера получаем

    \[N=\frac{1}{4}\left(\varphi(1)\frac{4!}{2!2!}+\varphi(2)\frac{2!}{2!}\right)=2,\]

что полностью соответствует результату, полученному ранее с помощью таблицы.

Источники: http://e-maxx.ru/algo/burnside_polya
https://ru.wikipedia.org/wiki/%D0%91%D1%91%D1%80%D0%BD%D1%81%D0%B0%D0%B9%D0%B4,_%D0%A3%D0%B8%D0%BB%D1%8C%D1%8F%D0%BC
http://elibrary.lt/resursai/Uzsienio%20leidiniai/Omsk/1998-02/ogu9802_05.pdf

Оставьте свой отзыв

Добавить изображение