Странный пример задачки по комбинаторике

[Yadryara]

Получается, TOTAL, Вы предложили 4-й вариант трактовки условия. Ваш ответ верен, если различать не только все книги, но и порядок их переплетания.

[Denis Russkih]

manul91 в сообщении #1108972 писал(а):

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

Вот оно что! :) Спасибо за подробные объяснения, теперь всё стало яснее. :)

manul91 в сообщении #1108972 писал(а):

Ваша формула верна только при $k \equiv 3$ и неверна при $k \neq 3$.

Ох, блин. :) Ведь чувствовал, что с ней всё-таки что-то не так. Но поленился проверить для $k \neq 3$.

Огромное спасибо, что отловили этот баг. :)

Yadryara в сообщении #1108982 писал(а):

manul91 в сообщении #1108972 писал(а):

В правильной обобщенной формуле для $k$ цветов, без факториалов не обойтись...

Осталось пожелать Denis Russkih удачи самостоятельно добраться и до этой обобщённой формулы.

А чего там добираться? Тут как раз всё понятно.

Пусть $k$ — количество возможных цветов, $m$ — общее количество книг, $n$ — количество неразличимых книг. Тогда итоговая формула будет такой:

$\dfrac{k^{m-n}(k+n-1)!}{n!(k-1)!}$


...Конечно, это если не учитывать новую идею TOTAL касательно того, что порядок, в котором берутся книги для переплетания, тоже имеет значение. :) Если же попытаться учесть, то ситуация получается сложнее. Нельзя просто умножить формулу на $m!$, ведь некоторые из книг неразличимы, и нам всё равно, в каком порядке их переплетать. Но и на $(m-n)!$ умножить тоже нельзя — поскольку, хотя порядок выбора неразличимых книг и не важен, но их вкрапления могут выглядеть по-разному.

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

В принципе, эта ситуация аналогична той, о которой говорил manul91, только здесь у нас не 2 разделителя, а целых $n$ разделителей, которые неразличимы между собой, но могут по-разному разбивать последовательность выбора различимых книг. :) Значит, если я правильно понял, наш множитель должен вычисляться по следующей формуле: $\dfrac{m!}{n!}$.

Таким образом, итоговая формула — с учётом возможности переплетания книг в разном порядке — примет вид:

$\dfrac{k^{m-n}(k+n-1)!}{n!(k-1)! } \cdot \dfrac{m!}{n!} = \dfrac{k^{m-n}m!(k+n-1)!}{n^2!(k-1)! }$

Вроде бы так. :) Хотя сочинял я это всё чисто интуитивно, так что полной уверенности нет.

[Yadryara]

Denis Russkih, Вы большой молодец!

Ну разве что $n!\cdot n! \neq n^2!$

Надо было так: $n!\cdot n! =(n!)^2

-- 25.03.2016, 16:40 --

Впрочем, "Альфа" понимает и без скобок:

5!^2 = (5!)^2= $14400$

, но

$5^2! = 5^{2!}=25$

[Denis Russkih]

Yadryara в сообщении #1109059 писал(а):

Ну разве что $n!\cdot n! \neq n^2!$

Спасибо, я просто не знал, как это правильно записать. :)

Значит, итоговая версия формулы (с учётом порядка, в котором берутся книги) будет такая:

$\dfrac{k^{m-n}m!(k+n-1)!}{(n!)^2(k-1)! }$

[manul91]

Denis Russkih в сообщении #1109035 писал(а):

В принципе, эта ситуация аналогична той, о которой говорил manul91, только здесь у нас не 2 разделителя, а целых $n$ разделителей, которые неразличимы между собой, но могут по-разному разбивать последовательность выбора различимых книг. :) Значит, если я правильно понял, наш множитель должен вычисляться по следующей формуле: $\dfrac{m!}{n!}$.

Браво.
Остается только отметить что когда формула $\dfrac{k^{m-n}(k+n-1)!}{n!(k-1)!}$ является обобщением (обобщает задачу про переплетов $m$ неотличимых книг в $k$ цветов - на переплетов $m$ книг из которых $n$ неотличимы в $k$ цветов), то формула $\dfrac{k^{m-n}m!(k+n-1)!}{(n!)^2(k-1)! }$ является вообще-то решением другой задачи - получающейся из последней с дополнительным условием что порядок переплетения книг теперь тоже существен.
Т.е. последняя формула не сводится к прежней, путем выбора каких-нибудь конкретных значений для ее величин.

-----------------------------------------------------


Если кому-то интересно, вот еще двух задачeк на разминку (простая, и более сложная):

1) Сколько отличающихся двуцветных ожерельев можно сделать из $m$ бусин - из которых $n_1$ белых (и $m-n_1$ черных).
Формулу объяснить "по понятному", и обобщить на ожерельев из k цветов (бусины одного цвета понятное дело неотличимы).


2) Пусть задано абстрактное множество из $m$ отличимых "состояний" - $S_1, S_2, .... S_m$.
"Эволюционным правилом над этих состояний" будем называть правило $U$, которое отображает любое состояние $S_k$ в некоторое другое конкретное состояние из этого множества (может в частности и совпадать с исходном).
Например для $m=3$, одна возможная "эволюционная динамика" определяется как $U: (S_1 \rightarrow S_2, S_2 \rightarrow S_3, S_3 \rightarrow S_1)$, а другая возможная "эволюционная динамика" определяется как $U: (S_1 \rightarrow S_2, S_2 \rightarrow S_1, S_3 \rightarrow S_1)$.
Эволюционное правило $U$ будем называть "обратимым", если любое из состояний $S_k$ имеет ровно одного "предшественника" $S_l$ такого чтобы $U \cdot S_l \rightarrow S_k$.
2a) Сколько разных эволюционных правил существует над множестве из $m$ отличимых состояний?
2b) Сколько разных обратимых эволюционных правил существует над множестве из $m$ отличимых состояний?
2c) Из всех обратимых эволюционных правил, какова доля правил содержащая конкретного цикла состояний $S_1 \rightarrow S_2 ..... \rightarrow S_k$ длиной $k (k \leq m)$?

Теперь, две конкретные эволюционные правила $U^1$ и $U^2$ будем называть "изоморфными", если существует взаимнооднозначное отображение между состояний, которое преобразует $U^1$ в $U^2$ и наоборот.
Например $U^1: (S_1 \rightarrow S_2, S_2 \rightarrow S_3, S_3 \rightarrow S_1)$ изоморфно $U^2: (S_1 \rightarrow S_3, S_3 \rightarrow S_2, S_2 \rightarrow S_1)$ (обе представляются одним замкнутым циклом из трех элементов), но они не изоморфны $U^3: (S_1 \rightarrow S_1, S_2 \rightarrow S_2, S_3 \rightarrow S_3)$ (оно представляется тремя отдельными циклами по одного элемента, т.е. переводящими каждого из элементов в себе).

Далее допустим, что мы перестали отличать изоморфные правила - мы "потеряли" возможность отличать сами состояния ("стерли" индексы состояний, после построения правила) - а отличаем только конфигурации цепочек определяемые правилом.

2d) Сколько разных (неизоморфных) эволюционных правил существует над множестве из $m$ состояний?
2e) Сколько разных (неизоморфных) обратимых эволюционных правил существует над множестве из $m$ состояний?
2f) Из всех обратимых (неизоморфных) эволюционных правил, какова доля правил содержащая по меньшей мере одного цикла длиной $k (k \leq m)$?

[buddy]

Стандартный подход без "изобретательства" к решению таких задач дает лемма Бернсайда.

[manul91]

buddy в сообщении #1109183 писал(а):

Стандартный подход без "изобретательства" к решению таких задач дает лемма Бернсайда.

Что-то я переборщил с задачу 1), пусть будет так - "сколько разных ожерельев можно сделать из m различимыми бусинами" ; )

[Denis Russkih]

manul91

Прошу прощения, но те две Ваших задачки слишком сложны для меня. :)

Вторая — вообще какой-то ад. :) Эволюционная динамика, неизоморфные обратимые эволюционные правила... Это что вообще было? :) Явно не для моих скромных умственных способностей. :) Так грозно звучит, что сразу ясно — пытаться вникнуть бесполезно.

Ну и первая задачка, несмотря на обманчиво простую формулировку, тоже наверняка слишком сложна для меня, раз для её решения требуется эта загадочная лемма Бернсайда. Насколько я понимаю, бессмысленно даже и пробовать её решить.

manul91 в сообщении #1109194 писал(а):

Что-то я переборщил с задачу 1), пусть будет так - "сколько разных ожерельев можно сделать из m различимыми бусинами" ; )

Сколько разных ожерельев можно сделать из $m$ различимых бусин?..

Хм, интересно. :) Вообще, в целом для $m$ различимых бусин возможно $m!$ различных вариантов взаимного расположения. Однако ожерелье-то закольцовано, поэтому некоторые варианты неотличимы друг от друга, так как получаются простым сдвигом бусин / вращением ожерелья.

Подумаем, сколько может быть "двойников" у одного ожерелья. Представим, что мы разрезали его в произвольном месте и растянули в простую цепочку бусин. Тогда, если мы будем снимать бусину с одного конца и нанизывать её на другой конец, то у нас будет получаться то же самое ожерелье. Кроме того, мы можем перевернуть эту цепочку вверх ногами — так, что все бусины окажутся идущими в обратном порядке — и всё равно это будет то же самое ожерелье.

Таким образом, есть $2m$ разных вариантов, как может выглядеть одно и то же ожерелье: $m$ сдвигов на одну бусину и столько же их зеркальных отражений.

Если для каждого ожерелья существует $2m$ разных вариантов представления в виде цепочки бусин, а для всех возможных ожерелий имеется $m!$ таких вариантов, то логично предположить, что из $m$ бусин можно составить
$\dfrac{m!}{2m} = \dfrac{(m-1)!}{2}$
ожерелий.

Вроде так, хотя я могу и ошибаться. :)


...Кстати, ответ на самом деле зависит ещё и от того, обладают ли бусины симметрией. :) Предположим, что на бусину нанесена цифра 6. Тогда мы можем снять эту бусину, перевернуть и нанизать как 9. :) Различимость "входа" и "выхода" у всех бусин значительно расширяет количество ожерелий, которые можно изготовить. :) Насколько я понимаю, это $2^m$ вариантов нанизывания бусин для каждого ожерелья, а значит, из $m$ бусин можно будет составить
$\dfrac{m! \cdot 2^m}{2m} = 2^{m-1}(m-1)!$
ожерелий.

...А ещё можно поворачивать бусину, уже нанизанную на нитку, вокруг этой нитки. Если различать углы поворота бусин вокруг нитки, то количество возможных ожерелий становится практически бесконечным. :)

В общем, многое зависит от того, что считать ожерельем и что считать бусиной. :)