Формула Пойя-Бернсайда

Формулы перечисления, рассмотренные в предыдущем разделе, представляют собой частные случаи весьма общей формулы, открытой в начале XX века английским математиком Уильямом Бернсайдом. В 1940 году венгерский математик Дьердь Пойя, работающий последние годы в США, с большим успехом применил эту формулу к решению ряда важных математических и научных задач. Эту общую формулу описывает следующая

Теорема 7. Пусть S - произвольное множество, содержащее конечное число элементов, a G - конечная группа симметрии этого множества, содержащая n операций симметрии g₁, g₂, ..., g_n-1, g_n. (Одной из этих операций должна быть тождественная, или единичная, операция.) Пусть через С(g) обозначено число элементов множества S, инвариантных относительно операции g. Тогда общее число N элементов S, не эквивалентных по отношению к симметриям группы G, равно

(Если g₁ - тождественная, или единичная, операция, то С(g₁) = Т, то есть числу элементов S.)

Довольно легко объяснить, из каких соображений возникает эта формула. Сравнительно несложно применять ее для решения многих задач. Однако строгое доказательство формулы требует знакомства с весьма глубокими разделами математики. Интересующихся отсылаем к статье автора о конечной классификации [42] и к книге Джона Риордана [41] (см. библиографию). Там можно найти полное доказательство формулы Пойя - Бернсайда и примеры ее приложений в более тонких ситуациях.

Читатель может также попытаться вывести каждую из четырех формул предыдущего раздела (для инволюций, симметрии группы прямоугольника, группы вращений квадрата и диэдральной группы квадрата) из общей формулы теоремы 7.

Для каждого правильного многоугольника (напомним, что многоугольником называется часть плоскости, ограниченная отрезками прямых) существует группа вращений. Она называется циклической группой этого многоугольника, поскольку ее элементами являются все вращения на углы, кратные 360°/r, причем применение этих операций к многоугольнику все время переводит его в самого себя, перемещая по кругу (по циклу) стороны и углы многоугольника. Кроме того, для правильного r-угольника также существует группа вращений и зеркальных отражений, называемая диздральной группой этого многоугольника. Циклическая группа правильного r-угольника состоит из r симметрии, а диэдральная группа - из 2r симметрии.

Весьма интересны группы симметрии пространственных тел. Например, группа всех пространственных вращений правильного тетраэдра (тела, гранями которого являются четыре равносторонних треугольника) состоит из 12 симметрии. Группа вращений куба и группа вращений правильного октаэдра (тела, гранями которого являются восемь равносторонних треугольников) содержат по 24 симметрии. А группа вращений правильного додекаэдра (тела, ограниченного 12 правильными пятиугольниками) и группа вращений правильного икосаэдра (тела, ограниченного 20 равносторонними треугольниками) содержат по 60 симметрии.

Заинтересованный читатель может попробовать применить формулу Пойя - Бернсайда к решению ряда задач, содержание которых связано с этими новыми областями приложений теоремы 7. Задачи приведены ниже в качестве упражнений.

45. Стороны правильного шестиугольника раскрашиваются двумя красками. Сколько типов "раскрашенных" таким образом шестиугольников можно получить, если допускать вращение шестиугольника относительно центра? (Указание: N = ¹/₆ (C₀ + С₆₀ + C₁₂₀ + С₁₈₀ + С₂₄₀ + С₃₀₀).) Нарисуйте все возможные случаи.

46. Пусть в условиях предыдущей задачи мы разрешим также переворачивать шестиугольник. Сколько различных раскрасок станет теперь?

47. Решите предыдущие две задачи для случая трех и четырех цветов. Наконец, исследуйте общий случай k цветов.

48. Вершины равностороннего треугольника могут быть окрашены пятью цветами. Треугольник можно вращать и зеркально отображать. Сколько способов раскраски существует?

49. Пусть р - любое простое число, за исключением 2 (то есть р = 3, 5, 7, 11, 13, 17, ...). р бусинок, каждая из которых может быть окрашена в любой из b цветов, нанизываются на нитку. Сколько различно окрашенных ниток бус можно получить? Теперь предположим, что концы нитки связываются, образуя ожерелье. Сколько различных ожерелий можно получить, если ожерелья, отличающиеся одно от другого лишь вращениями, мы будем считать одинаковыми? Сколько мы получим ожерелий, если можно будет также переворачивать ожерелье? Проверьте полученную вами формулу для случая b = 2 цвета и р = 5 бусинок; для случая b = 4, р = 3.

50. Проверьте утверждение, что куб имеет 24 симметрии вращения. (Указание: у куба существует три типа осей, проходящих через его центр: от грани к грани, от ребра к ребру и от вершины к вершине. Исследуйте типы вращений куба вокруг всех таких осей.)

61. Грани куба раскрашиваются шестью разными красками. Покажите, что это можно сделать 30 различными способами.

52. Сколько существует различно раскрашенных кубов, у которых три грани окрашены в черный, а три другие в белый цвет?

53. Сколько существует различно раскрашенных кубов, имеющих две красные, две белые и две синие грани?

54. Каждая из восьми вершин куба либо остается на месте, либо отсекается. Сколько существенно различных тел может при этом получиться? У скольких из них отсечены ровно четыре вершины? Изобразите схематически все эти случаи.