2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Странный пример задачки по комбинаторике
Сообщение25.03.2016, 09:20 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение25.03.2016, 13:59 
Аватара пользователя


05/01/13

3968
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)! }$

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

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение25.03.2016, 16:26 
Аватара пользователя


29/04/13
8013
Богородский
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$

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение25.03.2016, 17:48 
Аватара пользователя


05/01/13

3968
Yadryara в сообщении #1109059 писал(а):
Ну разве что $n!\cdot n!  \neq n^2!$

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

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

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

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение25.03.2016, 23:09 
Заслуженный участник


24/08/12
1039
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)$?

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение25.03.2016, 23:21 


19/03/16

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

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение26.03.2016, 00:19 
Заслуженный участник


24/08/12
1039
buddy в сообщении #1109183 писал(а):
Стандартный подход без "изобретательства" к решению таких задач дает лемма Бернсайда.

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

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение26.03.2016, 19:46 
Аватара пользователя


05/01/13

3968
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)!$
ожерелий.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 38 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group