Комбинаторное тождество

[Whitaker]

Здравствуйте!
Доказать следующее тождество:
$C_{n+m}^{n}=\sum P(k_1, k_2, ...,k_m, n-k_1-...-k_m+1)$
где суммирование распространено на все целые неотрицательные решения уравнения $k_1+2k_2+...+mk_m=m$

Подскажите хотя бы с чего начать.

[Sonic86]

Что за функция $P$?

[Whitaker]

Sonic86 в сообщении #476119 писал(а):

Что за функция $P$?

$P(n_1, n_2, ..., n_k)=\frac{n!}_{n_1!n_2!....n_k!}$, где $n=n_1+n_2+...+n_k$
Это есть количество различных перестановок $n$ элементов среди которых $n_1$ элементов первого типа,$ n_2$ элементов второго типа, .... $n_k$ элементов $k$-го типа

[arseniiv]

Мультиномиальный коэффициент называется это часто.

[deep blue]

$C_{n+m}^{n}$ это число неотрицательных решений уравнения $x_1+x_2+...+x_{n+1}=m$. Оно очевидным образом складывается из групп решений характеризующихся всевозможными допустимыми наборами чисел $k_1,k_2,...,k_m$. В каждой такой группе есть $k_1$ переменных со значением 1, $k_2$ переменных со значением 2, $k_3$ переменных со значением 3, ...