重複組合せVol.1

この記事の所要時間: 146

重複組合せの問題Vol.1

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

この記事では,重複組合せの代表的な問題を1つ紹介します.

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

\(n=3\) の場合を例として,実際に書き出してみましょう.

\(x, y, z\)はそれぞれが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個を選ぶ方法が何通りあるか,という問題で,キャンディ,クッキー,チョコの個数をそれぞれ \(x, y, z\) とすればQ1.の \(n=3\)の場合と同じ問題です.

一般の \(n\) の場合も同様なので,

\begin{align*}
{}_nH_3&={}_{n+2}C_3\\
&=\dfrac{1}{6}(n+2)(n+1)n
\end{align*}

通りとなります.

もっと一般の場合

では,変数が \(m\) 個ある場合はどうでしょうか.

Q2.  \(n\) を自然数とする.\(x_1+x_2+\cdots+x_m= n\) を満たす\(m\)個の 0 以上の整数 \((x_1,x_2,\ldots,x_m)\)の組はいくつあるか.
これも同じですね.\(m\)個から重複を許して\(n\)個を選ぶのと同じなので,
\begin{align*}
{}_nH_m &= {}_{n+m-1}C_m
\end{align*}
通りになります.

次回以降,この問題の亜種とも呼べるような,応用について紹介していきます.
スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加