重複組合せVol.2 - 数学の力

重複組合せの問題Vol.2

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

前回の記事(重複組合せVol.1)では，重複組合せの代表的な問題として次のような問題を紹介しました．

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

この問題の答えは，

\begin{align*}
{}_3H_n &= {}_{n+2}C_2
\end{align*}

になることが分かりました(詳しくは前回の記事を見てください)．

今回は，少し応用した問題を考えてみます．

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

$x$ の条件が0以上ではなく1以上になっています．

以前の記事のお菓子の問題に直した方が分かりやすいかもしれません．

Q1. かごにキャンディ，クッキー，チョコが入っています．この中から $n$ 個をもらえることになりました．選び方は何通りあるか．但し，チョコが好きなのでチョコは少なくとも1個選ぶものとする．

このままでは解けないので，必ず選ぶチョコを先に1個取ってしまいます．すると，あと $n-1$ 個はキャンディ，クッキー，チョコから自由に選べるので，重複組合せの考え方を使うと，

\begin{align*}
{}_3H_{n-1} &= {}_{n+1}C_{n-1}\\
&= {}_{n+1}C_{2}\\
&= \dfrac{1}{2}(n+1)n.
\end{align*}
となります．

上の問題Q.3でこの考え方を使うと，次のようになります．

新しい変数 $w=x-1\,(x=w+1)$ を考えて問題の条件を書き直すと，

Q'. $w+y+z=n-1, w\geqq 0, y\geqq 0, z\geqq 0$ を満たす整数 $(w, y, z)$ の組はいくつあるか．

となります． $w$ と $x$ は1対1に対応するので， $(w,y,z)$ の組の個数を考えてもいいわけです．よって， ${}_{3}H_{n-1}$ となります．

より一般の場合

不等式の条件の部分がより一般的な場合も同様にして解くことができます．

Q2. $n$ を自然数とする． $x_1+x_2+\cdots+x_m= n, x_1\geqq p_1, x_2\geqq p_2, \ldots, x_m\geqq p_m$ を満たす整数 $(x_1, x_2, \ldots, x_m)$ の組はいくつあるか． $p_1, p_2, \ldots, p_m$ は整数で， $n\geqq p_1+p_2+\cdots+p_m$ を満たすとする．

この問題も，

$w_1=x_1-p_1, w_2=x_2-p_2, \ldots, w_m=x_m-p_m$ という $m$ この変数を新しく導入します．すると，

Q2'. $n$ を自然数とする． $w_1+w_2+\cdots+w_m= n-p_1-p_2-\cdots-p_m, w_1\geqq 0, w_2\geqq 0, \ldots, w_m\geqq 0$ を満たす整数 $(w_1, w_2, \ldots, w_m)$ の組はいくつあるか．
$p_1, p_2, \ldots, p_m$ は整数で， $n- p_1-p_2-\cdots-p_m\geqq 0$ を満たす．

よって，

$\begin{align*} {}_{m}H_{n-p_1-p_2-\cdots-p_m} = {}_{n+m-p_1-p_2-\cdots-p_m-1}C_{m-1} \end{align*}$

となります．