. Іншими словами, побудуємо графік зазначеного відношення. Число зазначених точок (точок, що належать графіком) можна підрахувати двома способами:
визначити число зазначених точок на кожній вертикалі і підсумувати отримані величини або ж визначити число таких точок по кожній горизонталі і потім вичистити їх суму.
Згідно з визначенням відносини на кожній вертикалі зазначаються всі точки, які зберігаються перестановкою, відповідної цієї вертикалі. Їх число дорівнює Тому число всіх точок графіка одно
З іншого боку, на кожній горизонталі зазначаються всі перестановки, що зберігають елемент m, відповідальний цієї горизонталі. Ми знаємо, що вони утворюють групу Gm - стабілізатор елемента т - і їх чисто одно
Тому при другому способі підрахунку числа зазначених точок графіка розглянутого відносини отримуємо вираз
Однак якщо елементи i, j М містяться в одній орбіті, то і тому Нехай - все орбіти групи G, такі, що, і доданки в цьому об'єднанні не перетинаються. Розіб'ємо суму (1) на частини так, щоб всередині кожної з частин підсумовування йшло за елементами деякої орбіти:
Кожне з t доданків у правій частині цієї рівності можна перетворити таким чином:
Тому
Таким чином, при другому способі підрахунку ми отримали зазначених точок графіка. Прирівнюючи величини, отримані при першому і другому способах, отримаємо
т.е.
Лема доведена.
§2. Задачі про розмальовках
Розглянемо дві комбінаторні задачі на застосування леми Бернсайда. симетрія багатогранник лема Бернсайд
Завдання 1: Скількома способами можна розфарбувати вершини куба в три кольори (наприклад, червоний, синій і зелений)?
Кожну з восьми вершин куба можна розфарбувати трьома способами, причому незалежно від того, як розфарбовані інші вершини, то безліч всіх вершин куба можна розфарбувати 38=6 561 різними способами. Однак при такому підході до вирішення завдання мовчазно передбачається, що ми вміємо розрізняти вершини куба перед забарвленням, т. Е., Скажімо, куб жорстко закріплений або його вершини занумеровані. При цьому отриманий відповідь можна інтерпретувати наступним чином: можна так розфарбувати 38 абсолютно однакових, жорстко закріплених кубів, що всі вони будуть відрізнятися. Дли 38 + 1 кубів цього зробити вже не можна.
Ситуація істотно змінюється, якщо ми відмовимося від припущення про те, що куби жорстко закріплені, так як по-різному забарвлені куби можна повернути так, що в новому положенні їх забарвлення співпадуть (рис. 5).
Природно вважати, що два куби розфарбовані однаково, якщо їх розмальовки збігаються після деякого обертання одного з кубів в просторі. Будемо говорити, що такі розмальовки кубів геометрично неотличими. Тому природним уточненням завдання про розфарбовування є наступна задача: Скількома геометрично різними способами можна розфарбувати вершини куба в три кольори.
Переформулюємо тепер цю задачу так, щоб стала зрозумілою її зв'язок з лемою Бернсайда. Нехай М - безліч всіляких по-різному розфарбованих кубів одного розміру, положення яких в просторі фіксоване, G -группа всіх обертань куба, що складається з 24 перестановок. Група G природним чином визначає групу перестановок на безлічі М. Саме: якщо - деяке обертання, то кожному кубу з М можна зіставити деякий, взагалі кажучи, інший куб. який виходить з першого при обертанні. Це відповідність є, очевидно, перестановкою на безлічі М, яку будемо позначати. Групу всіх таких перестановок безлічі М. визначаються перестановками з G, ми будемо позначати. Ясно, що.
Те, що два куби і з М розфарбовані геометрично однаково, означає, що один з них можна перевести обертанням в таке положення, в якому вони невиразні. Іншими словами, існує така перестановка, що, т. Е. І містяться в одній орбіті групи, що діє на безлічі М. Таким чином, для того щоб визначити число геометрично помітних способів розмальовки вершин куба, потрібно знайти кількість орбіт групи на безлічі М.
Вважаючи вершини кубів занумерован числами 1,2, 3, 4, 5, 6, 7, 8. розмальовку кожного з 38 кубів можна однозначно охарактеризувати «словом» з 8 букв, кожна з яких є або k , або c, або з. Те, що i-ая літера слова дорівнює до (або з, або з), означає, що i-ая вершина при вибраній нумерації пофарбована в червоний колір (або в синій, або в зелений відповідно). Наприклад, для кубів, зображених на рис. 5, маємо відповідно послідовності ссззсскк, ссссккзз. Перестановки з груп...
