数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

重複組合せVol.3

応用例・利用例

スポンサードリンク

重複組合せの問題Vol.3

重複組合せについては前回の記事を見てください．

これまでにVol.1, Vol.2ではつぎのような問題を扱いました．

Vol.1 $n$ を自然数とする． $x+y+z= n$ を満たす 0 以上の整数 $(x,y,z)$ の組はいくつあるか．

Vol.2 $n$ を自然数とする． $x+y+z= n$ , $x\geqq 1, y\geqq 0, z\geqq 0$ を満たす整数 $(x,y,z)$ の組はいくつあるか．

今回は次のような問題を考えます．

Vol.3 $n$ を自然数とする． $x+y+z\leqq n$ を満たす0以上の整数 $(x,y,z)$ の組はいくつあるか．

$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$ 個に増やします．

$n$ を自然数とする． $x_1+x_2+\cdots+x_m\leqq n$ を満たす0以上の整数 $(x_1,x_2,\ldots,x_m)$ の組はいくつあるか．

この場合も，新しい変数 $x_{m+1}=n-x_1-x_2-\cdots-x_m$ を導入すると，問題は以下のように書き換えることができます．

$n$ を自然数とする． $x_1+x_2+\cdots+x_m+x_{m+1}= n$ を満たす0以上の整数 $(x_1,x_2,\ldots,x_m, x_{m+1})$ の組はいくつあるか．

よって，\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*}

という等式が得られます．

ちなみに，この等式は二項係数の性質を使って帰納法で証明することもできます．