2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 
Сообщение16.03.2008, 22:38 
Математические пакеты такое считают. Для $n>0$ Mathematica дает $$
\frac{4^n \Gamma \left(n+\frac{1}{2}\right)}{\sqrt{\pi } \Gamma   (n+1)}.
$$

 
 
 
 
Сообщение16.03.2008, 22:55 
Аватара пользователя
Спасибо. Но мне бы с доказательстовм :)
Mathematica пишет, как она это выводит ?

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

 
 
 
 
Сообщение16.03.2008, 23:17 
Аватара пользователя
Попробуйте доказать по индукции

 
 
 
 
Сообщение16.03.2008, 23:18 
Аватара пользователя
Echo-Off писал(а):
Попробуйте доказать по индукции

попробую...

 
 
 
 
Сообщение16.03.2008, 23:25 
Нет, конечно. Однако, поскольку теперь известен ответ, можно попытаться доказать по индукции. Разность правых частей при изменении аргумента от $n$ к $n+1$ равна $$\frac{(3 n+1) (2 n)!}{n!  (n+1)!}$$. Осталось доказать, что то же самое верно для левой :)

 
 
 
 
Сообщение18.03.2008, 17:33 
Аватара пользователя
Во-первых, можно заметить, что
$${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}$ :shock:

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

Добавлено спустя 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}.$$

 
 
 
 
Сообщение18.03.2008, 18:48 
Аватара пользователя
спасибо

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group