Комбинаторная задача о рассадке людей на стулья

[Rusit8800]

После того, как я вспомнил об одной известной тюремной загадке, мне в голову пришла следующая задача.

Пусть имеется $m$ стульев, и $n$ - человек, желающих на них посидеть. Мы можем рассаживать людей на эти стулья сколько угодно раз: некоторые стулья могут быть пустыми, а на некоторых может сидеть несколько человек. Самое главное - рассадить всех. При этом мы считаем разными случаями все перестановки людей, сидящих на одном стуле(вид "башни" из людей, сидящих на одном стуле имеет значение). Число всех таких рассадок равно $P$, это число нужно найти.

Решу вначале упрощенную задачу. Пусть задано множество $\[\left\{ {{n_1},{n_2},..,{n_k}} \right\}\]$ , такое, что $\[\sum\limits_{i = 1}^k {{n_i} = n} \]$, причем $\[1 \leqslant k \leqslant m\]$ и $\[{n_i} \geqslant 1\]$, то есть задано разбиение числа $n$ такое, чтобы число слагаемых разбиения было не больше, чем число стульев(все эти числа, разумеется, натуральные). Каждое число из множества $\[\left\{ {{n_1},{n_2},..,{n_k}} \right\}\]$ показывает число человек в $k$ группах, которые будут сидеть на одном стуле. Поскольку $\[{n_i} \geqslant 1\]$, то $\[k \leqslant n\]$ (разбиение на группы по одному человеку содержит наибольшее число слагаемых - $n$).
Вначале мы выбираем $k$ стульев $\[C_m^k\]$ способами. Далее мы независимо от выбора стульев рассаживаем на $k$ стульев $k$ групп людей $\[k!\]$ способами. Число способов переставить людей в каждой группе равно $\[\prod\limits_{i = 1}^k {\left( {{n_i}!} \right)} \]$. По правилу произведения, число рассадок заданной групп людей $\[\left\{ {{n_1},{n_2},..,{n_k}} \right\}\]$ по $m$ стульям равно

$$\[k!C_m^k\prod\limits_{i = 1}^k {\left( {{n_i}!} \right)} \]$$

Обозначим за $A$ множество всех возможных множеств $\[\left\{ {{n_1},{n_2},..,{n_k}} \right\}\]$, то есть множество всех разбиений числа $n$, удовлетворяющих вышеуказанным условиям. Тогда ответ к задаче можно выразить формулой:

$$\[P = \sum\limits_{\left\{ {{n_1},{n_2},..,{n_k}} \right\} \in A} {k!C_m^k\prod\limits_{i = 1}^k {\left( {{n_i}!} \right)} } \]$$

Меня такой ответ не удовлетворяет, так как придется собственноручно искать все нужные разбиения, считать каждое слагаемое вручную и все сложить.
Есть ли другой ответ к задаче?

[arseniiv]

Упорядочим стулья и будем сажать людей сначала на первый, потом на второй и т. д.. Запишем протокол, разделяя рассадки на разные стулья палочками. Можно видеть, что протоколы и рассадки соответствуют друг другу биективно, а как посчитать протоколы, довольно ясно.

[DeBill]

Rusit8800 в сообщении #1353753 писал(а):

Есть ли другой ответ к задаче?

А чем $n!C^{k-1}_{n+k-1}$ Вам не нравится?

[TOTAL]

Rusit8800 в сообщении #1353753 писал(а):

Есть ли другой ответ к задаче?

У меня есть другой ответ (не знаю, правильный ли): $\prod\limits_{k = m}^{m+n-1} {k}$

Установили в ряд $m+n$ стульев.
Первый человек садится на свободный (но не первый) стул, второй человек садится на свободный (но не первый) стул и т.д.

[Rusit8800]

DeBill в сообщении #1353790 писал(а):

А чем $n!C^{k-1}_{n+k-1}$ Вам не нравится?

Это ответ к задаче? Вы посчитали сумму

Rusit8800 в сообщении #1353753 писал(а):

$$\[P = \sum\limits_{\left\{ {{n_1},{n_2},..,{n_k}} \right\} \in A} {k!C_m^k\prod\limits_{i = 1}^k {\left( {{n_i}!} \right)} } \]$$

другим способом? Как вам удалось?

-- 15.11.2018, 21:10 --

Мои то рассуждения, кстати, верны?

-- 15.11.2018, 21:16 --

arseniiv в сообщении #1353785 писал(а):

Упорядочим стулья и будем сажать людей сначала на первый, потом на второй и т. д.. Запишем протокол, разделяя рассадки на разные стулья палочками. Можно видеть, что протоколы и рассадки соответствуют друг другу биективно, а как посчитать протоколы, довольно ясно.

Это похоже на вывод формулы числа сочетаний с повторениями (по крайней мере такой вывод дан в Виленкине). Меня, правда, смущает, что в таком типе сочетаний один и тот же человек может повторяться. Но по условию это не так.

[arseniiv]

Не, это перестановки с повторениями $m' = m-1$ одинаковых междустулий и ещё $n$ штук разных людей по штуке каждого. Формула получается

$$\frac{(m' + \sum^n 1)!}{m'! \prod^n 1!} = \frac{(m' + n)!}{m'!},$$

ответ совпадает с предложенными DeBill и TOTAL.

UPD. Я совсем с ума сошёл, писать штуки типа $\sum^n 1$ и $\prod^n 1!$ — это же $n\cdot 1$ и $1!^n$!

[DeBill]

Rusit8800 в сообщении #1354328 писал(а):

Мои то рассуждения, кстати, верны?

Да вроде - веррно, если разбиения понимать как неупорядоченные. Но уж больно страшная сумма. Возможно, она свернется - надо что то с производящими функциями делать.
А та формула, что я написал - это по arseniiv: переставляем людей как попало, и - шарами и перегородками ("палочками")- рассаживаем на стулья...

[Rusit8800]

DeBill в сообщении #1354348 писал(а):

если разбиения понимать как неупорядоченные

Разбиение на группы $\[\left\{ {{n_1},{n_2},..,{n_k}} \right\}\]$ ,конечно,неупорядочено. Но походу сделал ошибку в том, что назвал $\[\left\{ {{n_1},{n_2},..,{n_k}} \right\}\]$ множеством, хотя по сути это мультимножество(но не кортеж), так как группы могут состоять из одинакового количества человек, но порядок не имеет значения. Но эти группы $n_i$ все равно будут считаться разными, так что на ответ не повлияет.

$$\frac{(m' + \sum^n 1)!}{m'! \prod^n 1!} = \frac{(m' + n)!}{m'!},$$

$$\[\frac{{(m' + n)!}}{{m'!}} = \frac{{(m - 1 + n)!}}{{(m - 1)!}} = \bar C_m^nn!\]$$

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

[arseniiv]

Rusit8800 в сообщении #1354353 писал(а):

Разбиение на группы $\[\left\{ {{n_1},{n_2},..,{n_k}} \right\}\]$ ,конечно,неупорядочено.

А, и стулья неразличимы? Тогда надо смотреть разбиения $n$ на не более чем $m$ слагаемых, это через одни факториалы красиво уже не выражается.

[Rusit8800]

arseniiv в сообщении #1354365 писал(а):

А, и стулья неразличимы? Тогда надо смотреть разбиения $n$ на не более чем $m$ слагаемых, это через одни факториалы красиво уже не выражается.

Они вот так неупорядочены $ \bar C_m^n$ и вид "башни" из людей не имеет значения, а так вот так $ \bar C_m^nn!$ упорядочены и вид "башни" имеет значение.

-- 16.11.2018, 20:21 --

Хотя что-то мне кажется, что эти рассуждения неверны, а верны только первоначальные, так как, видимо, кое-где может отсутствовать упорядоченность. Я сейчас подумаю над этим вопросов и напишу более подробно и понятно.

-- 16.11.2018, 20:28 --

Согласен, формула

$$\[\frac{{(m' + n)!}}{{m'!}} = \frac{{(m - 1 + n)!}}{{(m - 1)!}} = \bar C_m^nn!\]$$

неверна, здесь

arseniiv в сообщении #1354365 писал(а):

Тогда надо смотреть разбиения $n$ на не более чем $m$ слагаемых, это через одни факториалы красиво уже не выражается.

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

[arseniiv]

Rusit8800 в сообщении #1354569 писал(а):

Пока не могу придумать, как решить свою задачу с помощью ваших идей.

Видимо, никак (ну, в принципе можно всунуть квадратную деталь в треугольное отверстие, но чего это будет стоить!).