Нектороая комбинаторная сумма.

[Сомик]

Пусть $H_n^k=C_{n+k-1}^k$ - число сочетаний из $n$ по $k$ с повторениями. Хотелось бы найти $\sum_{k=0}^n(H_n^k)$

Или другими словами. Если мультимножеством называть множество с повторяющимеся элементами, то надо найти число всех мультиподмножеств множества из $n$ элементов (при этом мощность каждого мультиподмножества не превышает $n$).

[Gafield]

Математические пакеты такое считают. Для $n>0$ Mathematica дает

$$ \frac{4^n \Gamma \left(n+\frac{1}{2}\right)}{\sqrt{\pi } \Gamma (n+1)}. $$

[Сомик]

Спасибо. Но мне бы с доказательстовм
Mathematica пишет, как она это выводит ?

Кстати Maple выдал $\frac{(n+1)C_{2n}^{n-1}}{n}$

[Echo-Off]

Попробуйте доказать по индукции

[Сомик]

Echo-Off писал(а):

Попробуйте доказать по индукции

попробую...

[Gafield]

Нет, конечно. Однако, поскольку теперь известен ответ, можно попытаться доказать по индукции. Разность правых частей при изменении аргумента от $n$ к $n+1$ равна

$$\frac{(3 n+1) (2 n)!}{n! (n+1)!}$$

. Осталось доказать, что то же самое верно для левой

[maxal]

Во-первых, можно заметить, что

$${n+k-1\choose k} = (-1)^k {-n\choose k}$$

и поэтому искомая сумма есть ни что иное как сумма первых $n+1$ коэффициентов разложения функции $(1-x)^{-n}$ в ряд по степеням $x$:

$$(1-x)^{-n} = {-n\choose 0} - {-n\choose 1} x + {-n\choose 2} x^2 - \dots$$

Во-вторых, вычислить эту сумму проще всего, умножив полученную производящую функцию на $1+x+x^2+\dots=(1-x)^{-1}$, так что искомая сумма будет равна просто коэффициенту при $x^n$ в разложении $(1-x)^{-n} (1-x)^{-1}=(1-x)^{-(n+1)}$.
Согласно биному Ньютона, этот коэффициент равен попросту:

$$(-1)^n {-(n+1)\choose n} = {2n\choose n}.$$

Добавлено спустя 4 минуты 19 секунд:

Сомик писал(а):

Кстати Maple выдал $\frac{(n+1)C_{2n}^{n-1}}{n}$

Странно, что у мапла не хватило сил упростить это до ${2n\choose n}.$ Хотя, наверное, надо было его уговорить с помощью команды simplify()

Добавлено спустя 13 минут 7 секунд:

Re: Нектороая комбинаторная сумма.

Сомик писал(а):

Или другими словами. Если мультимножеством называть множество с повторяющимеся элементами, то надо найти число всех мультиподмножеств множества из $n$ элементов (при этом мощность каждого мультиподмножества не превышает $n$).

Кстати, тут есть комбинаторное доказательство. Понятно, что каждое такое мультиподмножество определяется кратностями своих элементов. Пусть $x_k$ - это кратность элемента $k$. Тогда условие, что мощность мультиподмножества не превосходит $n$ записываеться просто как

$$x_1 + x_2 + \dots + x_n \leq n.$$

Более того, каждое решение этого неравенства в неотрицательных целых числах определяет некоторое мультиподмножество. Поэтому вместо подсчета мультиподмножест можно подсчитать число всех решений этого неравенства. А это проще всего сделать, введя в рассмотрение "невязку" $y$ и превратив неравенство в равенство:

$$x_1 + x_2 + \dots + x_n + y = n.$$

Подсчет числа решений такого уравнения - классическое упражнение, которое есть в каждом учебнике по комбинаторике. Для $m=n+1$ переменных и свободного члена $n$ оно равно числу сочетаний с повторениями из $m$ по $n$, то есть:

$${n+m-1\choose n}={2n\choose n}.$$

[Сомик]

спасибо