Есть n людей, каждый со своими m тараканами в голове

[enolc]

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

[pcyanide]

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

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

[pcyanide]

Кажется, у меня у самого в голове появятся тараканы, настолько достала меня эта задача. Каждый раз я мысленно к ней возвращаюсь. Поставил еще на 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}$ вариантов.

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

[pcyanide]

О вероятности. Аналогичным способом можно рассчитать общее количество расстановок (без ограничений): $(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}$ соответственно.

[arseniiv]

Численный эксперимент забраковал последние две формулы (так что и общую). А именно, при $(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$.

[pcyanide]

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

[arseniiv]

При $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: Поправил последнюю вероятность.

[pcyanide]

Ошибка действительно есть.

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

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

[PETIKANTROP]

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$

[PETIKANTROP]

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

[arseniiv]

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