重複組合せの問題Vol.1
重複組合せについては前回の記事を見てください.この記事では,重複組合せの代表的な問題を1つ紹介します.
Q1. を自然数とする. を満たす 0 以上の整数 の組はいくつあるか.
の場合を例として,実際に書き出してみましょう.
はそれぞれが0以上で和が3なので,
(0,0,3), (0,1,2), (0,2,1), (0,3,0), (1,0,2), (1,1,1), (1,2,0), (2,0,1), (2,1,0), (3,0,0)
と全部で10通りあります.
前回の記事の問題でいうと,キャンディ,クッキー,チョコから3個を選ぶ方法が何通りあるか,という問題で,キャンディ,クッキー,チョコの個数をそれぞれ とすればQ1.の の場合と同じ問題です.
一般の の場合も同様なので,
\begin{align*}
{}_3H_n&= {}_{n+2}C_n\\
&= {}_{n+2}C_2\\
&= \dfrac{1}{2}(n+2)(n+1)
\end{align*}
通りとなります.
より一般の場合
では,変数が 個ある場合はどうでしょうか.Q2. を自然数とする. を満たす個の 0 以上の整数 の組はいくつあるか.
これも同じですね.個から重複を許して個を選ぶのと同じなので,
\begin{align*}
{}_mH_n &= {}_{m+n-1}C_n
\end{align*}
{}_mH_n &= {}_{m+n-1}C_n
\end{align*}
通りになります.
次回以降,この問題の亜種とも呼べるような,応用について紹介していきます.