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

[NSKuber]

Someone

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

И если так, то где можно почитать нормально об азах комбинаторики?.. Подскажите хорошую книжку, пожалуйста. :)

iou в сообщении #1108771 писал(а):

А книга - "Комбинаторика" Виленкин Н.Я.

[Denis Russkih]

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

Вроде бы уже всё объяснили и не раз

Да, это уже давно понятно. :)

Я теперь спрашиваю о немного другом варианте этой задачи: в самом деле, что было бы, если бы книги оказались одинаковы, т.е. не было бы разницы, в каком порядке их красить?.. А имело бы значение только то, сколько всего имеется красных, зелёных и коричневых книг (без учёта их содержимого и порядка, в котором они расположены). Как утверждает iou, в этом случае решением будет $12 \cdot 3 = 36$. Но я не понимаю, с чего он это взял.

Как мне кажется, в этом случае (когда речь идёт об одинаковых книгах) должна использоваться приведённая здесь формула для нахождения числа сочетаний с повторениями (в нашем случае 3 элемента, взятых по 12, где элементы в наборе могут повторяться):

${\widetilde{C}}_n^m = \dfrac{(n + m - 1)!}{m! (n-1)!} = \dfrac{(3 + 12 - 1)!}{12! \cdot (3 - 1)!} = \dfrac{14!}{12! \cdot 2!} = 91$

Таким образом, для случая с одинаковыми книгами правильным ответом будет 91, а вовсе не 36. Во всяком случае, мне так кажется. Прошу меня поправить, если я не прав.

Косвенно моя правота подтверждается постом Geen, в котором он приводит ответ $13 \cdot 7$, что как раз и есть 91, хотя он пришёл к этому ответу каким-то другим путём.

Someone в сообщении #1108890 писал(а):

А где у Виленкина такая задача и с таким решением?

Полагаю, iou вовсе не имел в виду, что у Виленкина есть такая задача. Он просто отвечал на мою просьбу подсказать хорошую книгу по комбинаторике.

[Aritaborian]

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

Спасибо, а 2013 год подойдёт?

Да. Это второе не совсем второе, но не в этом суть издание. Просто я рекомендовал то, что лежало на столе ;-)

[gris]

Про одинаковые книги.
Красных может быть от нуля до двенадцати. В каждом случае жёлтых может быть от нуля до двенадцати минус количество красных. Коричневым выбирать не приходится. Все варианты разные. Все присутствуют. Считаем.
Итак $13+12+...+1=91$

[Aritaborian]

По-прежнему не могу понять неправильности ответа $12 \cdot 3 = 36$. Берём первую книгу. Есть три варианта её переплёта. Переплетаем. Откладываем. Берём вторую. Есть три варианта её переплёта. Переплетаем. Откладываем... Дюжина книг, три цвета. Книги неразличимы. Ответ: $36$.

[gris]

Aritaborian, а что Вы считаете "способом", количество которых надо посчитать.

[buddy]

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

Если надо переплести $12$ книг, каждую в один из трёх цветов на выбор, то количество возможных способов, по-моему, должно быть $3^{12} = 531441$. (Ну, мне так интуитивно кажется.)

Рискну присоединиться. )) Задача заключается в определении количества разных наборов элементов длиной $12$-ть из $3$-х сортов элементов, имеем декартово произведение $12$-ти троек.

[Aritaborian]

gris в сообщении #1108909 писал(а):

а что Вы считаете "способом"

Крепко задумался, а что же я (но первым был iou ;-) считаю способом...

[Denis Russkih]

Aritaborian

Ну вот, скажем, может быть вариант, когда у нас получилось 5 красных книг, 3 зелёных и 4 коричневых. А может быть так, что получится 2 красных книги, 7 зелёных и 3 коричневых. А может быть и так, что все книги окажутся зелёными.

Сколько же, по-вашему, всего может быть таких вариантов — если все книги неразличимы, т.е. не имеет значения их содержимое и взаимное расположение? :)

Вы полагаете, что таких вариантов будет всего 36?.. А мне вот думается, что 91. И уже два человека, помимо меня, назвали число 91. :) Дело в том, что 91 — это так называемое количество сочетаний с повторениями. Для вычисления этого количества есть специальная формула, её я приводил выше, и результатом является 91. Хотя тот же самый ответ, похоже, можно получить и другими способами. (Как часто бывает в математике.)

Ну а в случае, если книги всё-таки различимы, правильный ответ будет $3^{12} = 531441$. Это уже понятно.

-- 24.03.2016, 22:55 --

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

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

Ну, я так вижу внутренним взором. :)

К примеру, в нашем случае
$m = n = 12, k = 3$
(т.е. все книги неразличимы, и доступно 3 цвета обложки):

$\dfrac{3^{12-12}(12+1)(12+2)}{2} = \dfrac{13 \cdot 14}{2} = 91$

А вот когда все книги различимы ( $m = 12, n = 0, k = 3$ ):

$\dfrac{3^{12-0}(0+1)(0+2)}{2} = \dfrac{3^{12} \cdot 2}{2} = 3^{12} = 531441$

А вот смешанный вариант, когда половина книг различима, а половина — идентична друг другу ( $m = 12, n = 6, k = 3$ ):

$\dfrac{3^{12-6}(6+1)(6+2)}{2} = \dfrac{3^{6} \cdot 7 \cdot 8}{2} = 20412$

По-моему, всё верно. :) И даже факториалы привлекать не потребовалось, после объяснения gris я смог обойтись без них. :)

[buddy]

Вам осталось обобщить свою задачу до леммы Бернсайда и Теоремы Пойа. )

[Denis Russkih]

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

Вам осталось обобщить свою задачу до леммы Бернсайда и Теоремы Пойа. )

Шутить изволите? :) Это какое-то очень сильное колдунство. :) Я даже не понимаю, что там говорится.

[manul91]

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

Как мне кажется, в этом случае (когда речь идёт об одинаковых книгах) должна использоваться приведённая здесь
формула для нахождения числа сочетаний с повторениями (в нашем случае 3 элемента, взятых по 12, где элементы в наборе могут повторяться):
${\widetilde{C}}_n^m = \dfrac{(n + m - 1)!}{m! (n-1)!} = \dfrac{(3 + 12 - 1)!}{12! \cdot (3 - 1)!} = \dfrac{14!}{12! \cdot 2!} = 91$

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

Заметим что конкретное разбиение 12 неотличимых книг на 3-х цветов: 2 красные книги, 4 желтые и 6 коричневые, можно записать как:

oo|oooo|oooooo

считая что слева направо - группы красных, желтых и коричневых книг соответно.

Знак "o" символизирует элементов соответного цвета ("книг"), знаки "|" - разделители, разделяют группы элементов одинакового цвета.

Так можно записать любое разбиение; для 12 элементов и 3 цветов - нам нужны 12 кружочков "o" и 3-1=2 разделителей "|"

Например, строка:

oooooooo||oooo

кодирует 8 красных 0 желтых 4 коричневых книг, а строка

|oooooooooooo|

кодирует 0 красных, 12 желтых и 0 коричневых книг.

Очевидно каждая такая строка (кодирующая какое-то разбиение 12 неотличимых книг в 3-х куч разных цветов), имеет 14 символов (12 + 3 -1).

Теперь, задача сводится к нахождению различимых последовательностей из 14 символов - в которых входят ровно 12 символа "o", и ровно 2 символа "|".

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

Таких строк тогда итого: $\frac{14 \cdot 13}{2!} \cdot \frac{12 \cdot 11 \cdot....2\cdot1}{12!} = \frac{14!}{2!\cdot 12!}$
- тут первая дробь обозначает вариантов расположения разделителей "|" (для первого разделителя имеем 14 возможных позиций из 14; для второго остаются 13 позиций из 14 - это нужно поделить на 2! так как порядок несуществен - символы двух разделителей неотличимы);
- а вторая дробь соответно оставшихся вариантов для расположения кружочков после того как разделители расставлены (для первого кружочка остаются 12 возможных позиций; для второго остаются 11 позиций и т.д. - все комбинации нужно поделить на 12! так как порядок несуществен - символы кружочков неотличимы).

Кстати сразу ясно что после того как мы расставили разделителей - места для кружочков всегда однозначно определены (из-за этого и вторая дробь вообще всегда равна единице -. так что ее можно и вообще не писать)

Отсюда и "понятна" формула для общего случая сочетаний с повторениями ${\widetilde{C}}_n^m = \dfrac{(n + m - 1)!}{m! (n-1)!}$

-- 25.03.2016, 04:14 --

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

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

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

И даже факториалы привлекать не потребовалось

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

Для $m=n=1, k=5$ (одна книга, пять цветов), ваша формула дает $\frac{5^{1-1} \cdot 2 \cdot 3}{2} = 3$ варианта.
А вариантов очевидно не 2, а 5.

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

-- 25.03.2016, 04:39 --

Aritaborian в сообщении #1108908 писал(а):

По-прежнему не могу понять неправильности ответа $12 \cdot 3 = 36$. Берём первую книгу. Есть три варианта её переплёта. Переплетаем. Откладываем. Берём вторую. Есть три варианта её переплёта. Переплетаем. Откладываем... Дюжина книг, три цвета. Книги неразличимы. Ответ: $36$.

Ваше число можно назвать "количество возможных выборов цвета, в процессе переплетения (берем - выбираем - откладываем, и т.д)".

Например если нужно переплесть двух неотличимых книг в два цвета (синий и красный), у вас будет $2 \cdot 2 = 4$ возможных выборов цвета, в процессе переплетения.

А различимых вариантов итогового переплетения, всего три - обе книги красные, обе книги синие, и одна красная и одна синяя.

[Geen]

Схлестнулись статистики Бозе, Ферми и Максвелла

[Yadryara]

Ну что же, рассмотрены 3 варианта условия и получены правильные ответы на них: $36$, $91$ и $531441$.

Здорово, что Denis Russkih сумел добраться и до формулы, справедливой для $k=3$:

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

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

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

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

[TOTAL]

Выбираем произвольную книгу, переплетаем её в один из цветов. Из оставшихся книг выбираем любую, переплетаем. И т.д. Итого $3^{12} \cdot 12!$