Комбинаторика

[nok99]

Здравствуйте! Необходимо доказать равенство, пользуясь комбинаторными методами.

4 в степени n = сумма от i=0 до n от произведения C из 2i по i и C из 2n-2i по n-i.

Возможно, здесь замешаны числа Каталано, но пока я не понял как их точно увязать. Заранее спасибо!

[deMarchi]

а бином Ньютона который говорит, что сумма перестановок (сочетаний) равна 2 в степени n?

[nok99]

с биномом дальше то нечего делать - где взять ещ одно сочетание и как загнать его под сумму?

С числами Каталана продвинулся немного. оказалось

$$ K_{n+1}=\sum{C_{2i}^i}*C_{2n-2i}^{n-i}*{\frac 1 {(n-i+1)*(i+1)}} $$

осталось избавиться от этого дробного коэффициэнта как-то

а асимптоматически K стремится к нечту похожему на $4^n$

[deMarchi]

да нет, достаточно вот этого
http://cito-web.yspu.yar.ru/link1/metod ... node4.html
ну и $P_{n_1, ... ,n_k}=\frac{(n_1+n_2+...+n_k)!}{n_1!n_2!...n_k!}$
$\sum_{n_1+...+n_k}P(n_1,...,n_k)=k^n$