Вывод формулы сочетания с повторениями

[Cosmochelik]

Как вывести формулу сочетания с повторениями?


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

[sergey zhukov]

Cosmochelik
Допустим, мы выбираем $m$ шаров из урны, содержащей $n$ разных шаров. Видно, что случай сочетаний с повторениями $\frac{(n+m-1)!}{m!(n-1)!}$ сводится к случаю сочетаний без повторений $\frac{n!}{m!(n-m)!}$, нужно только добавить в исходную урну с $n$ разными шарами еще $m-1$ других разных шаров, которые и будут играть роль "дубликаторов". Т.е. если они попадают в нашу выборку, то это означает, что какой-то шар (из исходного не пополненного множества $n$) был выбран повторно. Скажем, если в выборку попали все $m-1$ "дубликаторов" и 1 шар из исходного множества, то это значит, что этот 1 шар был выбран $m$ раз.

[dgwuqtj]

Обозначим через $f(m, n)$ количество сочетаний с повторениями (в терминологии sergey zhukov — $m$ шаров выбирается из урны с шарами $n$ типов). При каждом таком сочетании либо последний $n$-й тип не используется, либо можно считать, что последний выбранный шар ровно $n$-го типа, то есть $f(m, n) = f(m, n - 1) + f(m - 1, n)$. Отсюда формула выводится по индукции, ну и нужна база $f(0, n) = 1$, $f(m, 0) = 0$ при $m > 0$.

А ещё можно через производящие функции. Так как $f(m, n)$ — это количество представлений $m$ в виде суммы $n$ натуральных чисел (0 считается натуральным), то $\sum_{m = 0}^\infty f(m, n) t^m = (\sum_{i = 0}^\infty t^i)^n = (1 - t)^{-n}$. Дальше раскрываем по биному Ньютона, $(1 - t)^{-n} = \sum_{m = 0}^\infty (-1)^m \binom {-n} m$, ну и $(-1)^m \binom {-n} m = \binom {n + m - 1} m = \frac{(n + m - 1)!}{m! (n - 1)!}$. Только формулу с факториалами надо творчески понимать при $n = 0$.

[Cosmochelik]

sergey zhukov
А как доказать что нужно добавить именно $m - 1$ ?
dgwuqtj
Да, спасибо. Я пытался получить какую-то рекуррентную формулу, но тогда что-то пошло не так)

[sergey zhukov]

Cosmochelik
Ну, тут можно сказать, что сочетания с повторениями - это то же, что выборка с возвращением. При выборке с возвращением после выборки последнего шара (который уже не возвращается), в урне остается $n-1$ шаров. Значит (в нашем подохде с добавлением шаров), туда нужно было изначально добавить $m-1$ шаров.