Question

Подсчитайте количество различных ожерелий из 2 красных и 6 синих бусинок. Ожерелья считаются одинаковыми, если одно ожерелье может быть получено из другого передвижением бусинок по кольцу или переворачиванием ожерелья. В ответе должно быть ОДНО число!

Answer 1

Вот все 4 ожерелья:

ККСССССС

КСКССССС

КССКСССС

КСССКССС

Других нет: все ожерелья однозначно определяются набором расстояний между красными бусинками, а других способов представить 6 в виде суммы двух неотрицательных целых чисел, кроме 6 = 0 + 5 = 1 + 5 = 2 + 4 = 3 + 3, нет (если порядок слагаемых не учитывать).

Answer 2

Используя формулу Бернсайда для подсчета количества орбит действия группы перестановок на множестве ожерелий, получаем:

Количество орбит = (число поворотов) * (число отражений) * (число ожерелий, инвариантных относительно любой перестановки)

Число поворотов: у нас есть 8 бусинок, и мы можем начать ожерелье с любой из них, поэтому число поворотов равно 8.

Число отражений: мы можем отразить ожерелье по вертикали или по горизонтали, поэтому число отражений равно 2.

Число ожерелий, инвариантных относительно любой перестановки: ожерелья, в которых все синие бусинки расположены в одной половине, будут инвариантны относительно любой перестановки, поэтому число таких ожерелий равно 2.

Итого, количество различных ожерелий равно (8 + 2) / 2 * 2 = 10.

Ответ: 10.