Комбинаторная задача.

[toreto]

В наличии имеются одинаковые камни трех цветов. Сколько различных ожерелий можно собрать из 12 камней? (Ожерелье определяется расположением элементов по окружности. Сдвиг вдоль окружности и отражение дают то же ожерелье.)

Мои соображения. Если бы все камни были бы различных цветов, то $11!$ перестановок по окружности (это уже с учетом сдвига, но еще не учтено отражение). С учетом отражения $0,5\cdot 11!$. Но теперь самое сложное -- нужно учесть, что всего три цвета. Пока нет идей как это учитывать.

Была еще идея пересчитать в лоб. Одноцветных ожерелий $3$ штуки, 11 камней одного цвета, $1$ камень другого --$ 6$ вариантов. Но их походу тут очень много.

Подскажите, пожалуйста, как тут рациональнее подойти к этой задаче?

[Mihr]

toreto,
не вижу простого решения, однако хочу сделать замечание по поводу начала Вашего решения.

toreto в сообщении #1091744 писал(а):

С учетом отражения $0,5\cdot 11!$

Деление на два не переносится на случай ожерелий из камней трех цветов. Некоторые ожерелья будут симметричны, и их отражения ни к чему не приведут. Пополам нужно будет делить лишь число несимметричных ожерелий.
А вообще, поиск решения зависит от того, можно ли ожерелья переворачивать (отражать) или нельзя. Лучше сразу уточнить этот вопрос (переспросить у того, кто дал задачу, или перечитать точное условие). Если переворачивать ожерелья нельзя, то это задача Мак-Магона о числе ожерелий с $n$ бусинами $m$ цветов, которая рассмотрена в некоторых пособиях. Например, В.А. Колосов. Теоремы и задачи алгебры, теории чисел и комбинаторики. М. 2001, стр. 214-216.

[toreto]

Mihr в сообщении #1091862 писал(а):

toreto,
не вижу простого решения, однако хочу сделать замечание по поводу начала Вашего решения.

toreto в сообщении #1091744 писал(а):

С учетом отражения $0,5\cdot 11!$

Деление на два не переносится на случай ожерелий из камней трех цветов. Некоторые ожерелья будут симметричны, и их отражения ни к чему не приведут. Пополам нужно будет делить лишь число несимметричных ожерелий.
А вообще, поиск решения зависит от того, можно ли ожерелья переворачивать (отражать) или нельзя. Лучше сразу уточнить этот вопрос (переспросить у того, кто дал задачу, или перечитать точное условие). Если переворачивать ожерелья нельзя, то это задача Мак-Магона о числе ожерелий с $n$ бусинами $m$ цветов, которая рассмотрена в некоторых пособиях. Например, В.А. Колосов. Теоремы и задачи алгебры, теории чисел и комбинаторики. М. 2001, стр. 214-216.

Спасибо. В условии же написано, что отражение дает то же ожерелье. А это значит можно или нельзя? А под $\varphi (n)$ понимается функция Эйлера?

[Mihr]

toreto в сообщении #1092062 писал(а):

В условии же написано, что отражение дает то же ожерелье. А это значит можно или нельзя?

Конечно, это значит, что переворачивать можно, и непосредственно решение задачи Мак-Магона сюда не подходит.
Не сочтите мою реплику за флуд, я позволил себе высказаться просто потому, что не исключал такой возможности: вдруг Вы привели условие задачи по памяти, а оно не совсем такое. Это ведь бывает нередко. Вот я и попросил уточнить условие.

toreto в сообщении #1092062 писал(а):

А под $\varphi (n)$ понимается функция Эйлера?

Да. Но это, вероятно уже неважно: решение той задачи использовать не получается

Тогда некоторую надежду вселяет то, что используемых цветов не очень много - всего 3. Может быть, удастся перебрать варианты? Попробую на всякий случай. Если получится что-то разумное - отпишусь.

[toreto]

Условие не по памяти, точно воспроизведено. Спасибо!

[arseniiv]

Теорема Редфилда—Пойа, если более прямо станет лень искать, тоже может помочь. По ссылке даже упомянуто название таких конфигураций — bracelets (не знаю, переводят ли их на русский браслетами), и как к ним применить теорему.

[Cancre]

Очень советую династический учебник
Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. "Комбинаторика" (2006г)
Параграф 121 "Хороводы"
Там как раз ваш случай разобран.

[toreto]

Cancre в сообщении #1092107 писал(а):

Очень советую династический учебник
Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. "Комбинаторика" (2006г)
Параграф 121 "Хороводы"
Там как раз ваш случай разобран.

Там не разобран нужный случай. Потому как с различными бусинами задачу я уже решил и без учебника.

-- 19.01.2016, 11:52 --

arseniiv в сообщении #1092090 писал(а):

Теорема Редфилда—Пойа, если более прямо станет лень искать, тоже может помочь. По ссылке даже упомянуто название таких конфигураций — bracelets (не знаю, переводят ли их на русский браслетами), и как к ним применить теорему.

Спасибо. С Английским у меня туговато, может руки дойдут разобраться с теоремой еще

[Skeptic]

Число цветов - система счисления, число камней в ожерелье - число разрядов. Итого, число комбинаций - двенадцати разрядное троичное число.

[Brukvalub]

Skeptic в сообщении #1092220 писал(а):

Число цветов - система счисления, число камней в ожерелье - число разрядов. Итого, число комбинаций - двенадцати разрядное троичное число.

Это неверно, поскольку в условии черным по белому написано:

toreto в сообщении #1091744 писал(а):

Ожерелье определяется расположением элементов по окружности. Сдвиг вдоль окружности и отражение дают то же ожерелье.)

[Cancre]

toreto в сообщении #1092132 писал(а):

Cancre в сообщении #1092107 писал(а):

Очень советую династический учебник
Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. "Комбинаторика" (2006г)
Параграф 121 "Хороводы"
Там как раз ваш случай разобран.

Там не разобран нужный случай. Потому как с различными бусинами задачу я уже решил и без учебника.

Ммда, эт я поторопился.
Но дальше тема развёртывается, советую почитать. И обратить внимание на задачу №24 этой главы (ответы и некоторые пояснения в конце учебника) Может, чем нибудь поможет.

[arseniiv]

(Оффтоп)

toreto в сообщении #1092132 писал(а):

Спасибо. С Английским у меня туговато, может руки дойдут разобраться с теоремой еще

Есть и на русском статья, но там нет указанного факта про группу диэдра. Вообще, конечно, лучше взять описание теоремы из какой-нибудь книги по комбинаторике, но тут я не советчик.

[Skeptic]

(arseniiv)

По правилам темы нельзя давать полный ответ, допускаются только подсказки, что я и сделал.
У меня не решение, а первый шаг решения. Сходу говорить о том, что он неверен, опрометчиво. Следующий шаг решения - удовлетворение условиям задачи. Это я оставил на усмотрение ТС, если его заинтересует такой подход.

[provincialka]

Skeptic в сообщении #1092531 писал(а):

У меня не решение, а первый шаг решения.

Skeptic в сообщении #1092220 писал(а):

число комбинаций - двенадцати разрядное троичное число.

Никоим образом! это число изображает отдельное ожерелье, а не их количество. Просто банальная перекодировка.

Видимо, без перебора всё-таки не решить... Надо только организовать его аккуратно. Может, разбить ожерелья по длине наибольшего одноцветного участка?

[arseniiv]

(Skeptic)

Не, я понимаю ошибиться кнопкой при цитировании — но при ручном вводе ника? Я вам ничего не писал в этой теме, мне хватило других.