2014 dxdy logo

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

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


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


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



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


26/10/14
380
Новосибирск
Someone
Denis Russkih в сообщении #1108766 писал(а):
И если так, то где можно почитать нормально об азах комбинаторики?.. Подскажите хорошую книжку, пожалуйста. :)

iou в сообщении #1108771 писал(а):
А книга - "Комбинаторика" Виленкин Н.Я.

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


05/01/13

3968
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 вовсе не имел в виду, что у Виленкина есть такая задача. Он просто отвечал на мою просьбу подсказать хорошую книгу по комбинаторике.

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


11/06/12
10390
стихия.вздох.мюсли
Denis Russkih в сообщении #1108840 писал(а):
Спасибо, а 2013 год подойдёт?
Да. Это второе не совсем второе, но не в этом суть издание. Просто я рекомендовал то, что лежало на столе ;-)

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 21:26 
Заслуженный участник
Аватара пользователя


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

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


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

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 21:37 
Заслуженный участник
Аватара пользователя


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

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


19/03/16

114
Denis Russkih в сообщении #1108766 писал(а):
Если надо переплести $12$ книг, каждую в один из трёх цветов на выбор, то количество возможных способов, по-моему, должно быть $3^{12} = 531441$. (Ну, мне так интуитивно кажется.)
Рискну присоединиться. )) Задача заключается в определении количества разных наборов элементов длиной $12$-ть из $3$-х сортов элементов, имеем декартово произведение $12$-ти троек.

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


11/06/12
10390
стихия.вздох.мюсли
gris в сообщении #1108909 писал(а):
а что Вы считаете "способом"
Крепко задумался, а что же я (но первым был iou ;-) считаю способом...

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


05/01/13

3968
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 я смог обойтись без них. :)

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


19/03/16

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

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


05/01/13

3968
buddy в сообщении #1108938 писал(а):
Вам осталось обобщить свою задачу до леммы Бернсайда и Теоремы Пойа. )

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

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


24/08/12
1053
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$ возможных выборов цвета, в процессе переплетения.

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

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


01/09/13
4656
Схлестнулись статистики Бозе, Ферми и Максвелла :-)

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


29/04/13
8120
Богородский
Ну что же, рассмотрены 3 варианта условия и получены правильные ответы на них: $36$, $91$ и $531441$.

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

$$\dfrac{3^{m-n}(n+1)(n+2)}{2}$$
manul91 в сообщении #1108972 писал(а):
В правильной обобщенной формуле для $k$ цветов, без факториалов не обойтись...

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

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


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

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

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



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

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


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

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