Таблицы Брадиса

Для поворотов вычислено в

Для поворотов вычислено в

Элементы математики в задачах - Г. А. Мерзон

Задача 34. а) Найдите число способов раскрасить п-местную кару­сель в красный и синий цвета.

б)     Найдите число способов раскрасить ожерелье из п бусинок в красный и синий цвета.

1 п-1

Ответ, а) - ^ 2(т,п');

1 п-1

2[19] + ^ У 2(т-п), п = 21 + 1;

2п т=о

1 п-1

3 • 2г-1 + -- У 2(т-п), п = 21.

2п т=о

-о-

Теория групп 2. Гомоморфизмы                       247

Решение. а) Нас интересует число орбит при действии Z/nZ (цик­лическими перестановками) на множестве раскрасок n-элементного множества. Воспользуемся леммой Бернсайда. Для этого для каждого числа m нам нужно найти |Fix m| —число раскрасок, переходящих в себя при циклическом сдвиге на m. При такой раскраске каждая орбита сдвигов на m должна быть покрашена одним цветом, а значит,

|Fix m| = 2число орбит. Так как каждая из этих орбит состоит из n/(m, n) элементов (это следует из того, что am = 0 (mod n) ^ a = (m, n)k), всего их (m, n). Следовательно, |Fix m| = 2(m,n) и по лемме Бернсайда

1  n-1

искомое число способов есть - У\ 2<-т,п\

n 0

б)  Этот пункт аналогичен предыдущему, но группа симметрий ожерелья больше Z/nZ — это группа диэдра Dn. Ее можно опреде­лить как группу движений плоскости, сохраняющих правильный n-угольник. Нетрудно заметить, что она состоит из n поворотов (обра­зующих нормальную подгруппу, изоморфную Z/nZ) и n симметрий.

Для поворотов |Fix g| вычислено в предыдущем пункте. Вычислим |Fix g| для симметрий. Если n нечетно, то ось симметрии прохо­дит ровно через одну вершину (и |Fixg| = 2(n+1)/2); если же n чет­но, то для половины симметрий ось проходит через две вершины (и |Fixg| = 2(n+2:i/2), а для другой половины — не проходит через вер- -ф-          шины (и |Fixg| = 2n/2).                         (\)