積の和典型の3通りの証明

横一列に並んだ$n+m-1$個の玉から$m-1$個の玉を除いて$a_1,a_2,\dots,a_m$個の玉のグループに分け，さらに各グループから$1$個ずつ玉を除くことを考えると除き方は各組$(a_1,a_2,\dots,a_m)$に対して$a_1a_2\cdots a_m$通りだけある．これを全ての組に対して行うことは$m+n-1$個の玉から$2m-1$個を選んで除くことと等価なので，結局積の和は${}_{n+m-1} \mathrm{ C }_{n-m}$である．$\square$

$(0,0)$から$(2m,n-m)$まで格子点を通りながら最短経路で行く方法であって$(2m,n-m-1)$を通らないものに対して，経路上で$x$座標が$2k$であるような格子点であって$y$座標が最小であるものを$b_k$とする．このとき$a_1+a_2+\cdots+a_m=n,a_0=0$なる正整数の組$(a_0,a_1,a_2,\dots a_m)$に対して$b_{k+1}-b_k=a_k-1$が$k=0,1,2,\dots,m-1$について成り立つような経路が$a_1a_2\cdots a_m$だけある．よってこの積の和は全ての経路の総数に等しく，${}_{n+m-1} \mathrm{ C }_{n-m}$である．

$$ f(x)=(x+2x^2+3x^3+\dots)$$
とすると所望の値は$f(x)^m$を展開したときの$x^n$の係数である．ところで
$$ f(x)=x(1+x+x^2+\cdots)^2 $$
であるので$(1+x+x^2+\cdots)^{2m}$を展開したときの$x^{n-m}$の係数を求めればよく，これは$n-m$個の玉を$2m$人に分配する方法の総数$ {}_{n+m-1} \mathrm{ C }_{n-m} $である．$\square$