Застосування переліку груп підстановок до розв'язування комбінаторних задач

Застосування переліку груп підстановок

до розв'язування комбінаторних задач 

Нехай   – довільна група пiдстановок на множинi  ,   – деяка пiдстановка. Для кожного натурального   символом   позначено кiлькiсть циклiв довжини   у розкладi пiдстановки   на добуток взаємно простих циклiв.

У [1] Дж. Редфiлдом, а дещо пiзнiше – Дж. Пойя у [2] було введене центральне поняття теорії переліку – поняття циклового iндексу. А саме, цикловим iндексом   групи пiдстановок   називають многочлен вiд   змiнних  , визначений за формулою:

Точку   називають нерухомою для пiдстановки  , якщо  . Символом   позначають число нерухомих точок пiдстановки  , а символом   – кiлькiсть орбiт групипідстановок .

Наступне твердження відіграє є базовим при розв'язуванні задач теорії переліку.

Теорема (Лема Бернсайда). [3]. Для довiльної групи пiдстановок   має мiсце рiвнiсть:

Лема Бернсайда  допускає рiзнi узагальнення та модифiкацiї. Найважливiшим є її узагальнення на довiльнi групи дiй, причому i сама форма, i доведення твердження залишаються без змiни. Це узагальнення часто використовується в ситуацiї, коли доводиться обмежувати дiю групи   на пiдмножини множини  .

Використовуючи основні твердження теорії переліку груп підстановок, можна розв'язувати окремі комбінаторні задачі, приклади яких наведено нижче. Ці задачі можна пропонувати учням старших класів для розв¢язування на факультативних заняттях, адаптуючи до рівня їх знань основні теоретичні відомості теорії переліку.

Задача 1. Скiлькома геометрично рiзними способами  можна розташувати два різні типи намистин у низку з   намистин, якщо кількість намистин кожого кольору фіксована (не фіксована)?

Задача 2. Скiльки рiзних низок намиста можна скласти з   бiлих, m синіх i p жовтихнамистин?

Задача 3. Cкiлькома геометрично рiзними способами можна розфарбувати гранi куба 2-ма (3-ма) кольорами?

Задача 4. Cкiлькома геометрично рiзними способами три брати-близнюки можуть розташуватися у вершинах куба (тетраедра)?

Задача 5. Дано q правильних тетраедрiв, гранi яких фарбуються двома кольорами. Два розфарбування вважаються еквiвалентними, якщо вiд одного з них до iншого можна перейти, переставляючи тетраедри й обертаючи їх. Скiльки iснує рiзних попарно нееквiвалентних способiв розфарбувань?