Лемма Бёрнсайда и задача об ожерельях
Недавно натолкнулась на интересную комбинаторную задачу, которая, как выяснилось, имеет отношение к разным проблемам в разных разделах математики, причем не только математики.
Задача. Сколько существует различных ожерелий, составленных из красных и
синих бусин? (Считается, что два ожерелья одинаковы, если одно можно получить из другого поворотом.)
Эта задача решается с помощью леммы Бернсайда, которая позволяет получить и множество других интересных результатов.
Сначала немного истории. Уильям Бернсайд (1852–1927) привел доказательство этой леммы в своей книге в 1897 г. Однако выяснилось, что данную формулу знали еще Коши (1845 г.) и Фробениус (1887 г.). Видимо, лемма была настолько хорошо известна, что Бернсайд не указал авторство Коши. Данный результат имеет несколько названий (кроме уже приведенного): лемма Коши — Фробениуса, лемма не Бернсайда (в области теории групп очень многие результаты принадлежат именно Бернсайду).
Для формулировки леммы понадобятся некоторые сведения. Поскольку нас интересует задача об ожерельях, на ее примере и будем все рассматривать.
Обозначим через множество всех ожерелий. Пусть
— множество всех различных поворотов ожерелий (ясно, что разных поворотов всего
). Очевидно, что
— группа. При этом каждому ожерелью из
можно сопоставить ожерелье, полученное из него с помощью поворота
. При этом два ожерелья считаются одинаковыми, или эквивалентными, если одно можно перевести в другое каким-либо поворотом из
. Таким образом, все ожерелья разбиваются на классы эквивалентности, или орбиты. Наша задача — найти число различных орбит. Читать полностью ‘Лемма Бёрнсайда и задача об ожерельях’ »