2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Есть n людей, каждый со своими m тараканами в голове
Сообщение18.09.2017, 17:18 


18/09/17

2
Есть n людей у каждого из которых в голове сидит m тараканов, и больше чем m поместиться не может. Значит сели эти люди выпивать, напились, кто в умат, кто в стельку, а кто и вовсе в дугу, а их тараканы тем временем вырвались на свободу. Но вот люди отошли от пьянки и стали собирать тараканов и снова сажать их себе в голову, правда тараканы перемешались, а люди забыли где чей, ну, или просто не смогли их различить. Наконец всех тараканов рассадили по головам, в каждую голову ровно m. Так вот, какова вероятность, что каждый человек не имеет в голове своего таракана? И какова вероятность, что каждый человек посадил себе в голову ровно одного своего таракана?

 Профиль  
                  
 
 Re: Есть n людей, каждый со своими m тараканами в голове
Сообщение05.12.2017, 01:01 
Аватара пользователя


01/12/17
87
Мельбурн
Посмотрите на тему «Беспорядок» (По-английски "Derangement"). Правда в Вашем случае не все так просто, так как речь идет не о «классическом» беспорядке (ни один не на своем месте), а о «контейнерном» (нет ни одного в том же множестве). Хотя связь конечно есть. Подумаю.

Что касается «своего таракана», то речь идет о перестановке с одним фиксированным элементом (1-cycle permutation). Это тоже не так просто, как обычная перестановка.

 Профиль  
                  
 
 Re: Есть n людей, каждый со своими m тараканами в голове
Сообщение16.12.2017, 01:24 
Аватара пользователя


01/12/17
87
Мельбурн
Кажется, у меня у самого в голове появятся тараканы, настолько достала меня эта задача. Каждый раз я мысленно к ней возвращаюсь. Поставил еще на math.stackexchange (в строгой формулировке, поскольку там чувство юмора не столь хорошо развито), надеясь привлечь дополнительные ресурсы. Все бесполезно!

Сегодня нашел нее очень простое решение:

Берем по 1 таракану из каждой головы и перераспределяем. Таким образом получаем $!n$ возможных перестановок (субфакториал, беспорядок, смешение, derangement ). Затем берем еще по одному таракану и снова перераспределяем. Получаем $(!n)^2$ распределений и т.д.

Для $m$ тараканов из каждой головы таким образом имеем $(!n)^m$ вариантов.

Если по одному таракану остается, требуется перераспределить по $m-1$ оставшихся тараканов. При этом выбрать таракана в каждой голове можно $m$ способами. Таким образом получаем $m^n(!n)^{m-1}$ вариантов. В общем случае, если $k$ тараканов остается, имеем \left(C_{m}^{k}\right)^n(!n)^{m-k}$ вариантов.

Неужели действительно все так просто?

 Профиль  
                  
 
 Re: Есть n людей, каждый со своими m тараканами в голове
Сообщение16.12.2017, 02:31 
Аватара пользователя


01/12/17
87
Мельбурн
О вероятности. Аналогичным способом можно рассчитать общее количество расстановок (без ограничений): $(n!)^m$.

Таким образом вероятность равна $\cfrac{\left(C_{m}^{k}\right)^n(!n)^{m-k}}{(n!)^m}$. При к=0 и 1 получаем $\left(\cfrac{!n}{n!}\right)^m$ и $\cfrac{m^n(!n)^{m-1}}{(n!)^m}$ соответственно.

 Профиль  
                  
 
 Re: Есть n людей, каждый со своими m тараканами в голове
Сообщение16.12.2017, 03:50 
Заслуженный участник
Аватара пользователя


27/04/09
21936
Уфа
Численный эксперимент забраковал последние две формулы (так что и общую). А именно, при $(n,m) = (2,2)$ беспорядочное расположение* лишь одно: $(\{3,4\},\{1,2\})$, и «1-порядочных» четыре, с вероятностями соотв. $1/6$ и $2/3$, ваша формула даёт $1/4$ и $1$.

* Исходным посчитаем $(\{1,2\},\{3,4\})$.

-- Сб дек 16, 2017 06:00:02 --

Вообще, $\sum\limits_{k=0}^m \frac{\left(C_{m}^{k}\right)^n(!n)^{m-k}}{(n!)^m}$ может превышать единицу. У меня вышло $3/2$.

 Профиль  
                  
 
 Re: Есть n людей, каждый со своими m тараканами в голове
Сообщение16.12.2017, 04:20 
Аватара пользователя


01/12/17
87
Мельбурн
С $m=n=2$ как раз получается хорошо, учитывая, что !2=1 (в отличие от 2!=2).
Насчет общего количества возможно я ошибся. Надо проверить.

 Профиль  
                  
 
 Re: Есть n людей, каждый со своими m тараканами в голове
Сообщение16.12.2017, 04:26 
Заслуженный участник
Аватара пользователя


27/04/09
21936
Уфа
При $n\leqslant2$ надо её просто на что-то умножить — отношения вероятностей верные получаются. В иных случаях даже они не те. На будущее, для $(3, 3)$ должны получиться вероятности $1/30, 9/56, 9/280, 1/1680$. Вообще, вероятность для $k=m$ должна быть равна $1/C_{mn}^{m,\ldots,m}$ (мультиномиальный коэффициент).

-- Сб дек 16, 2017 06:28:34 --

pcyanide в сообщении #1275307 писал(а):
С $m=n=2$ как раз получается хорошо
Вероятности-то не совпадают, что тут хорошего? Посмотрите сами, шесть расстановок пересмотреть можно вручную.

UPD: Поправил последнюю вероятность.

 Профиль  
                  
 
 Re: Есть n людей, каждый со своими m тараканами в голове
Сообщение16.12.2017, 04:33 
Аватара пользователя


01/12/17
87
Мельбурн
Ошибка действительно есть.

Дело в том, что распределяя по одному, мы не учитываем, что несколько могут попасть в одну голову. в следующий раз несколько попадают в другую голову, таким образом компенсируя ситуацию. Чувствовал я, что здесь гораздо хитрее.

Точно так же индукция по $m$ получается хитрее. Надо не просто перераспределить, а вложить по 2,3 и т.д. в одну голову, перераспределяя других. Одно очевидно: при $m=1$ получаем действительно $!n$ :)

 Профиль  
                  
 
 Re: Есть n людей, каждый со своими m тараканами в голове
Сообщение17.12.2017, 15:34 


15/04/15
454
pcyanide в сообщении #1275276 писал(а):
Берем по 1 таракану из каждой головы и перераспределяем. Таким образом получаем $!n$ возможных перестановок (субфакториал, беспорядок, смешение, derangement ). Затем берем еще по одному таракану и снова перераспределяем. Получаем $(!n)^2$ распределений и т.д.

Для $m$ тараканов из каждой головы таким образом имеем $(!n)^m$ вариантов.

А куда же делся вариант с упорядоченным распределением тараканов:
enolc в сообщении #1248709 писал(а):
какова вероятность, что каждый человек не имеет в голове своего таракана

?
Наверно, должно быть так:
а) $\left(\cfrac{!n}{!n+1}\right)^m$
б) $\left(\cfrac{1}{!n+1}\right)^m$

 Профиль  
                  
 
 Re: Есть n людей, каждый со своими m тараканами в голове
Сообщение17.12.2017, 18:39 


15/04/15
454
Ой, что-то я не то сморозила! Ни один мой таракан не попал на свое место. :D
может так?
а) $\left(\cfrac{!n}{n!}\right)^m$
Похоже, я двигаюсь с закрытыми глазами напролом в том же направлении, что и другие участники тараканьих бегов. :facepalm:
б) $\left(\cfrac{!n}{n!^2}\right)^{m-1}$

 Профиль  
                  
 
 Re: Есть n людей, каждый со своими m тараканами в голове
Сообщение18.12.2017, 07:13 
Заслуженный участник
Аватара пользователя


27/04/09
21936
Уфа
А с указанными мной выше вероятностями сходится? (Не проверял, уже ухожу.) Как раз ведь для сверки оставлял.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модератор: Модераторы



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

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


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

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