数学の力

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

重複組合せVol.1


スポンサードリンク

重複組合せの問題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*}
{}_3H_n&= {}_{n+2}C_n\\
&= {}_{n+2}C_2\\
&= \dfrac{1}{2}(n+2)(n+1)
\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*}
{}_mH_n &= {}_{m+n-1}C_n
\end{align*}
通りになります.


次回以降,この問題の亜種とも呼べるような,応用について紹介していきます.