Лемма Бёрнсайда и задача об ожерельях
Уильям Бёрнсайд
Недавно натолкнулась на интересную комбинаторную задачу, которая, как выяснилось, имеет отношение к разным проблемам в разных разделах математики, причем не только математики.
Задача. Сколько существует различных ожерелий, составленных из 
красных и 
синих бусин? (Считается, что два ожерелья одинаковы, если одно можно получить из другого поворотом.)
Эта задача решается с помощью леммы Бернсайда, которая позволяет получить и множество других интересных результатов.
Сначала немного истории. Уильям Бернсайд (1852–1927) привел доказательство этой леммы в своей книге в 1897 г. Однако выяснилось, что данную формулу знали еще Коши (1845 г.) и Фробениус (1887 г.). Видимо, лемма была настолько хорошо известна, что Бернсайд не указал авторство Коши. Данный результат имеет несколько названий (кроме уже приведенного): лемма Коши — Фробениуса, лемма не Бернсайда (в области теории групп очень многие результаты принадлежат именно Бернсайду).
Для формулировки леммы понадобятся некоторые сведения. Поскольку нас интересует задача об ожерельях, на ее примере и будем все рассматривать.
Обозначим через 
множество всех ожерелий. Пусть 
— множество всех различных поворотов ожерелий (ясно, что разных поворотов всего 
). Очевидно, что — группа. При этом каждому ожерелью из можно сопоставить ожерелье, полученное из него с помощью поворота 
. При этом два ожерелья считаются одинаковыми, или эквивалентными, если одно можно перевести в другое каким-либо поворотом из . Таким образом, все ожерелья разбиваются на классы эквивалентности, или орбиты. Наша задача — найти число различных орбит. Читать полностью ‘Лемма Бёрнсайда и задача об ожерельях’ »
до 
(числа всегда написаны с использованием пяти цифр). Несмотря на то, что все билеты имеют одинаковые шансы выиграть, часто говорят о красивых номерах и номерах довольно некрасивых. Поскольку оценка красоты является эстетической, является ли число красивым или нет зависит от вкусов каждого. 
,
при делении на 
,
. 
чисел 
, которые удовлетворяют условию 
при всех 
?
множество перестановок, в которых элемент 
элементов.
. Мы должны посчитать, в скольких перестановках на своих местах стоят элементы 
. Оставляем эти элементы на своих местах, а остальные 
элемента переставляем местами произвольным образом — итого 
перестановок. Выбрать два различных множества из множеств 
можно 
способами.
множеств 
элементов, а 
способами.![\[|A_1\cup A_2\cup\ldots\cup A_n|=n\cdot(n-1)!-{\sf C}_n^2(n-2)!+{\sf C}_n^3(n-3)!+\ldots+(-1)^n{\sf C}_n^n\cdot0!\]](http://hijos.ru/wp-content/ql-cache/quicklatex.com-bb2a07e44a8ba768f44a0fba709b59de_l3.png "Rendered by QuickLaTeX.com")
![\[n!-|A_1\cup A_2\cup\ldots\cup A_n|=n!\sum_{k=0}^n\frac{(-1)^k}{k!}.\]](http://hijos.ru/wp-content/ql-cache/quicklatex.com-99134e6cec8d4f987595f03a322fe026_l3.png "Rendered by QuickLaTeX.com")
при 
. Часть из этих монет лежит вверх орлом, а часть — решкой. Монеты можно переворачивать по следующим правилам: можно перевернуть все монеты, находящиеся в одном горизонтальном ряду, в одном вертикальном ряду или на одной диагонали (если монета лежит в углу, она образует диагональ из одной монеты). Целью игры является перевернуть все монеты вверх либо орлом, либо решкой. Всегда ли возможно это сделать или существуют некоторые расположения монет, для которых это невозможно? 
