2014 dxdy logo

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

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




 
 Комбинаторное тождество
Сообщение30.06.2015, 14:09 
Из общих соображений, вроде-бы, должно выполняться равенство:

$$\binom{n+k-1}{k-1}=\sum_{i=1}^{\min(n,k)} {\binom{n-1}{i-1}} {\binom{k}{i}}$$

Численно проверял, сходится, а вот как это доказать, плохо представляю, или это очевидное соотношение? В учебниках по комбинаторике не нашел, у Феллера в тI("An Introduction to Probability Theory and Its Applications") есть похожие соотношения, но такого выражения точно нет. Не поможете ли с доказательством?

 
 
 
 Re: Комбинаторное тождество
Сообщение30.06.2015, 14:15 
druggist
По-моему, нужно просто использовать это тождество нужное количество раз $${n\choose k}={n-1\choose k-1}+{n-1\choose k}$$

 
 
 
 Re: Комбинаторное тождество
Сообщение30.06.2015, 14:20 
Аватара пользователя
В равенстве $(1+x)^{n+k-1}=(1+x)^{n-1}(1+x)^k$ сравните коэффициенты при $x^n $ в левой и правой части.

 
 
 
 Re: Комбинаторное тождество
Сообщение30.06.2015, 17:51 
DiMath,ex-math, большое спасибо, идея ясна. А еще говорят, "- Подумаешь, бином Ньютона!" :-)

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


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