重複組合せの問題Vol.3
重複組合せについては前回の記事を見てください．
これまでにVol.1, Vol.2ではつぎのような問題を扱いました．
今回は次のような問題を考えます．
\(x, y, z\) の和がちょうど \(n\) ではなく，\(n\) 以下となる組を考えます．
考え方．
不等式のままでは扱いにくいので，等式を作ります．
どのようにするかというと，
\(w=n-x-y-z\) という新しい変数を導入すると，\(w\geqq 0\)となります．
すると，
・\(x+y+z\leqq n\)を満たす0以上の整数\(x, y, z\)の組
と，
・\(x+y+z+w=n\)を満たす0以上の整数\(x, y, z, w\)の組
は1対1に対応することがわかります．
よって，変数を一つ増やすことでVol.1のパターンに問題を書き換えることができたので，
\begin{align*}
{}_4H_n &= {}_{n+3}C_n\\
&= \dfrac{1}{6}(n+3)(n+2)(n+1)
\end{align*}
となります．
一般の場合
変数の数を \(m\) 個に増やします．
この場合も，新しい変数 \(x_{m+1}=n-x_1-x_2-\cdots-x_m\) を導入すると，問題は以下のように書き換えることができます．
よって，\begin{align*}
{}_{m+1}H_{n} &= {}_{n+m}C_{n}\\
&= {}_{n+m}C_{m}
\end{align*}
となります．
別の求め方から得られる等式
この問題の答えを別の求め方をしてみます．
Vol.1でも説明しているように，\(x_1+x_2+\cdots+x_m=i, x_1,x_2,\ldots,x_m\geqq 0\)を満たす\((x_1, \ldots, x_m)\)の組の個数は
\begin{align*}
{}_mH_i &= {}_{m+i-1}C_i\\
&= {}_{m+i-1}C_{m-1}
\end{align*}
です．
よって，Vol.3の問題の答えは，これを \(i=0, 1, \ldots, n\) について足し合わせたものになるので，
\begin{align*}
\sum_{i=0}^n {}_{m+i-1}C_{i}
\end{align*}
これが，上で求めたものと一致するはずなので，
\begin{align*}
\sum_{i=0}^n {}_{m+i-1}C_i = {}_{n+m}C_{m}
\end{align*}
という等式が得られます．
ちなみに，この等式は二項係数の性質を使って帰納法で証明することもできます．
