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
14494
Про одинаковые книги.
Красных может быть от нуля до двенадцати. В каждом случае жёлтых может быть от нуля до двенадцати минус количество красных. Коричневым выбирать не приходится. Все варианты разные. Все присутствуют. Считаем.
Итак $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
14494
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
1039
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
4648
Схлестнулись статистики Бозе, Ферми и Максвелла :-)

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


29/04/13
8013
Богородский
Ну что же, рассмотрены 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
5486
Нов-ск
Выбираем произвольную книгу, переплетаем её в один из цветов. Из оставшихся книг выбираем любую, переплетаем. И т.д. Итого $3^{12} \cdot 12!$

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

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



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

Сейчас этот форум просматривают: genk


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

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