Об одном комбинаторном тождестве из вероятностной задачи

[Sdy]

Довольно давно я решал следующую задачу.
Условие задачи.
$n$ шаров случайно раскладывают по $m$ ящикам. Найдите вероятность того, что ни один ящик не будет пуст, если шары неразличимы.
Решение первым способом.
Тогда я решил её довольно просто : раз шары неразличимы, то мы будем различать только исходы, в которых различается количество шаров в разных ящиках (ящики различимы) и

$$\Omega = \{(i_1,\ldots, i_m) : \forall j ~ : ~ 1 \leq j \leq m ~ 0 \leq i_j \leq n ~ \wedge ~ i_1+i_2+\ldots+i_m=n \}$$

Мощность $\Omega$ находится через рассуждение с шарам и перегородками (добавляем к $n$ шарам ещё $m-1$ шар и выбираем из них $m-1$ шаров, которые мы будем считать перегородками, вот и получили число всех раскладок, отличающихся только числом шаров в разных ящиках), $\#\Omega = {n+m-1 \choose m-1}.$
Будем считать что мы находимся в классической модели, то есть все исходы равновероятны. Обозначим событие $A = \{\text{Ни один ящик не пуст}\} = \{\text{В каждом ящик есть хотя бы один шар}\}$. Чтобы найти его мощность, поймём, что наличие в каждом ящик хотя бы одного шара означает, что $m$ шаров мы разложили по одному в каждый ящик, а потом уже разложили остальные шарики, что можно сделать (применяя аналогичное рассуждение с перегородками) ${(n-m)+(m-1) \choose m-1} = {n-1 \choose m-1}$ способами.
Поэтому,

$$\mathbb{P}(A) = \dfrac{\#A}{\#\Omega} = \dfrac{{n-1 \choose m-1}}{{n+m-1 \choose m-1}}$$

Решение вторым способом.
Недавно я наткнулся на другое решение этой задачи.
Будем использовать тоже самое вероятностное пространство, вследствие чего имеем $\#\Omega = {n+m-1 \choose m-1}$, через $A$ также обозначим $A = \{\text{Ни один ящик не пуст}\} = \{\text{В каждом ящик есть хотя бы один шар}\}$. Но искать вероятность $A$ будем по формуле включений-исключений.
Для $1 \leq k \leq m$ введём события $ A_ k = \{\text{$k$-й ящик пуст}\}$, тогда $A^c = A_1 \cup \ldots \cup A_m$.
Тем же методом с перегородками получаем, что $\forall 1 \leq i_1 < \ldots < i_l \leq m, ~ \#A_{i_1} \cap A_{i_2} \cap \ldots \cap A_{i_l} = {n+m-l-1 \choose m-l-1}.$

Тогда используя формулу включений исключений имеем,

$$\mathbb{P}(A) = 1 - \mathbb{P}(A^c) = 1 - \mathbb{P}\left(\bigcup\limits_{k=1}^{m}A_k\right)= 1- $$

$$-\left(\sum\limits_{k=1}^{m}\mathbb{P}(A_k) - \sum\limits_{j < k \leq m}\mathbb{P}(A_j \cap A_k) + \ldots + (-1)^{m-2}\sum\limits_{1 \leq i_1 < i_2 < \ldots < i_{m-1} \leq m}\mathbb{P}(A_{i_1}\cap A_{i_2}\cap \ldots \cap A_{i_{m-1}})\right) = $$

$$= 1 - \sum\limits_{k=1}^{m-1}(-1)^{k-1}{m \choose k}\dfrac{{n+m-k-1 \choose m-k-1}}{{n+m-1 \choose m-1}} = \sum\limits_{k=0}^{m-1}(-1)^{k}{m \choose k}\dfrac{{n+m-k-1 \choose m-k-1}}{{n+m-1 \choose m-1}}$$

Отсюда, объединяя моё решение с этим решением, я получаю (избавляясь от знаменателя), что

$${n-1 \choose m-1} = \sum\limits_{k=0}^{m-1}(-1)^{k}{m \choose k}{n+m-k-1 \choose m-k-1}$$

Вопрос.
Всё ли у меня верно? Получилось довольно интересное (для меня) комбинаторное тождество. Я проверил его численно, и вроде бы всё получается, но всё равно есть некоторые сомнения. Хотелось бы убедиться что всё хорошо на случай если когда-то придётся это тождество использовать.

[мат-ламер]

Sdy в сообщении #1623026 писал(а):

Условие задачи.
$n$ шаров случайно раскладывают по $m$ ящикам.

Что значит "случайно раскладывают"? Вы считаете все различные раскладки равновероятными. Думаю, что логично предположить, что мы берём очередной неразличимый шар и направляем его в случайно выбранный ящик.

[Sdy]

мат-ламер,
Вы можете решить эту задачу и в другой модели, но следить за судьбой каждого шара удобно когда они различимы, а в случае неразличимых шаров, чтобы не обсчитаться удобнее решать как это сделал я. Это классическая трактовка того, что значит "неразличимые шары размещаются по различимым ящикам", например, можно посмотреть задачу $1.52$, в задачнике Зубкова, Севастьянова, Чистякова, "Сборник задач по теории вероятностей".

То есть я не сомневаюсь в корректности первого способа решения и в адекватности вероятностного пространства описываемому эксперименту. Интерес для меня представляет его комбинация со вторым способом, которая даёт комбинаторное тождество. Напрямую проверить тождество у меня пока не получилось.

[мат-ламер]

Sdy в сообщении #1623094 писал(а):

Это классическая трактовка того, что значит "неразличимые шары размещаются по различимым ящикам", например, можно посмотреть задачу $1.52$, в задачнике Зубкова, Севастьянова, Чистякова, "Сборник задач по теории вероятностей".

Что касается именно этой задачи, то там в скобках конкретизируется, что понимается под элементарным событием.

Sdy в сообщении #1623094 писал(а):

но следить за судьбой каждого шара удобно когда они различимы, а в случае неразличимых шаров, чтобы не обсчитаться удобнее решать как это сделал я.

Что касается вопроса удобства слежения, то попробуйте объяснить два варианта понимания условия компьютеру с целью замоделировать процесс методом Монте-Карло.

Sdy в сообщении #1623094 писал(а):

То есть я не сомневаюсь в корректности первого способа решения

Я тоже не сомневаюсь. Суть моего предыдущего поста было уточнение условия.

[TOTAL]

Sdy в сообщении #1623026 писал(а):

Вопрос.
Всё ли у меня верно? Получилось довольно интересное (для меня) комбинаторное тождество.

$$(1+x)^{n-1}= (1+x)^{n+m-1}\left(1-\frac{x}{x+1} \right)^m= (1+x)^{n+m-1}-C_m^1x(x+1)^{n+m-2}+C_m^2x^2(x+1)^{n+m-3} - \cdots$$

Слева и справа находим коэффициент при $x^{m-1}$

[Sdy]

TOTAL,
Очень изящно, у меня вроде бы всё получилось, спасибо!