2014 dxdy logo

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

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




 
 Комбинаторика сумма сочетаний
Сообщение18.05.2013, 02:39 
Доброго времени суток!
помогите пожалуйста разобраться с таким примером
$\sum_{l=1}^{n}\l\cdot({C}_{n}^{l})^2 $
Сначала я получил $n\cdot\sum_{l=1}^{n}{C}_{n-1}^{l-1}\cdot{C}_{n}^{l} $
Далее по треугольнику паскаля определил чему равно $ \sum_{l=1}^{n}{C}_{n-1}^{l-1}\cdot{C}_{n}^{l} $ получилось ${C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n} $
подскажите пожалуйста что с этим делать дальше ибо нет никаких соображений, у меня несколько примеров на данном этапе хотелось бы остальные сделать самостоятельно.

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение18.05.2013, 05:49 
bekemzi в сообщении #725284 писал(а):
Сначала я получил $n\cdot\sum_{l=1}^{n}{C}_{n-1}^{l-1}\cdot{C}_{n}^{l} $

Остаётся заметить, что $\sum\limits_{l=1}^{n}{C}_{n-1}^{l-1}\cdot{C}_{n}^{l}\ -$ это число путей из левого нижнего угла клетчатого прямоугольника $n\times (n-1)$ в правый верхний, состоящих только из шагов вправо и вверх.

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение18.05.2013, 08:31 
bekemzi в сообщении #725284 писал(а):
чему равно $ \sum_{l=1}^{n}{C}_{n-1}^{l-1}\cdot{C}_{n}^{l} $
Можно воспользоваться тождеством (или сверткой) Вандермонда:
$$\binom{m+n}{r}=\sum_k\binom{m}{k}\binom{n}{r-k}$$
http://en.wikipedia.org/wiki/Vandermonde%27s_identity

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение18.05.2013, 10:33 
Простите, переформулирую вопрос, возможно ли $n\cdot({C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n})$ записать в виде некой функции что-ли, так как если раскрывать, то получится $n+\frac{n\cdot(n+1)}{1!}+\frac{n\cdot(n+1)\cdot(n+2)}{2!}+...$ или $n\cdot({C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n})$ является коечным ответом?

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение18.05.2013, 11:45 
bekemzi в сообщении #725337 писал(а):
Простите, переформулирую вопрос, возможно ли $n\cdot({C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n})$ записать в виде некой функции что-ли, так как если раскрывать, то получится $n+\frac{n\cdot(n+1)}{1!}+\frac{n\cdot(n+1)\cdot(n+2)}{2!}+...$ или $n\cdot({C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n})$ является коечным ответом?
Формально говоря, и исходное задание суммы и оба Ваших выражения - функции от $n$. Обычно в таких задачах спрашивают о замкнутом виде формулы, т.е. о равной формуле, содержащей лишь конечное число сложений, умножений и биномиальных коэффициентов. Вы просто должны упростить выражение. Исходное выражение - однократная сумма, полученное Вами - тоже однократная сумма, так что выражение Вы не упростили полностью, а пока только преобразовали (хотя биномиальных коэффициентов внутри суммы стало меньше, так что все-таки сумму немного упростили).
Сумму ${C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n}$ можно выразить в замкнутом виде, для выражения достаточно лишь индукции и основного тождества $C_n^k=C_{n-1}^k+C_{n-1}^{k-1}$. Попробуйте.

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение21.05.2013, 08:00 
Дико извиняюсь, но можно намекнуть как посчитать индукцию или дать ссылку на хороший материал :-( ибо я в тупике :-(

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение21.05.2013, 08:23 
Попробуйте сначала построить индуктивное предположение на основании нескольких частных случаев (либо на основании свертки Вандермонда)

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение21.05.2013, 08:25 
Аватара пользователя
bekemzi в сообщении #726505 писал(а):
Дико извиняюсь, но можно намекнуть

${C}_{n}^{n}+{C}_{n+1}^{n}+...+{C}_{n+n}^{n}$ - это коэффициент при $x^n$ в сумме $(1+x)^n +(1+x)^{n+1} + \cdots + (1+x)^{2n}.$

Находите сумму геометрической прогрессии, затем находите нужный коэффициент.

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение21.05.2013, 15:07 
Снова извините, посчитал сумму прогрессии получил $сумма=\frac{(x+1)^n\cdot ((x+1)^n-1)}{x}$,
но дальше всё плохо совсем
$(x+1)^1=1$
$(x+1)^3=3$
$((x+1)^6)+((x+1)^5)+((x+1)^4)=10$
Где-то ошибка или х страшное комплексное число :shock:

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение21.05.2013, 16:33 
Вы неверно нашли сумму прогрессии. У вас же n+1 член, поэтому сумма будет
$\[\frac{{{{(1 + x)}^n}({{(1 + x)}^{n + 1}} - 1)}}{x} = \frac{1}{x}{(1 + x)^{2n + 1}} - \frac{1}{x}{(1 + x)^n}\]$
А теперь заметьте, что во втором слагаемом $\[{x^n}\]$ вообще не будет, поэтому исследуем первое
$\[\frac{1}{x}{(1 + x)^{2n + 1}} = \frac{1}{x}\sum\limits_{k = 0}^{2n + 1} {C_{2n + 1}^k{x^{2n + 1 - k}}} \]$
$\[{x^n}\]$ получится при $\[k = n\]$
Окончательно ваша сумма
$\[\sum\limits_{k = n}^{2n} {C_k^n}  = C_{2n + 1}^n\]$

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение21.05.2013, 16:57 
Аватара пользователя
Зачем такие сложности?
$\sum\limits_{l=1}^{n} l\cdot(C_{n}^{l})^2=\frac{n}{2}\sum\limits_{l=0}^{n} (C_{n}^{l})^2=\frac{n}{2}\cdot C_{2n}^{n}$
Первое равенство следует из того, что $C_{n}^{k}=C_{n}^{n-k}$

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение21.05.2013, 17:30 
Аватара пользователя
sopor в сообщении #726678 писал(а):
Зачем такие сложности?
$\sum\limits_{l=1}^{n} l\cdot(C_{n}^{l})^2=\frac{n}{2}\sum\limits_{l=1}^{n} (C_{n}^{l})^2=\frac{n}{2}\cdot C_{2n}^{n}$
Первое равенство следует из того, что $C_{n}^{k}=C_{n}^{n-k}$

Проверьте первое равенство и второе равенство. (А ответ верный.)

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение21.05.2013, 17:41 
Аватара пользователя
TOTAL в сообщении #726695 писал(а):
sopor в сообщении #726678 писал(а):
Зачем такие сложности?
$\sum\limits_{l=1}^{n} l\cdot(C_{n}^{l})^2=\frac{n}{2}\sum\limits_{l=1}^{n} (C_{n}^{l})^2=\frac{n}{2}\cdot C_{2n}^{n}$
Первое равенство следует из того, что $C_{n}^{k}=C_{n}^{n-k}$

Проверьте первое равенство и второе равенство. (А ответ верный.)


Спасибо, да, индекс не тот поставил

 
 
 
 Re: Комбинаторика сумма сочетаний
Сообщение21.05.2013, 18:03 
Всем огромное спасибо!

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


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