“場合の数”をかぞえる - 順列・組合せ重複組合せ n個の異なるものからr個以下のものをとった場合の総数

学習環境

新装版数学読本4 (松坂和夫(著)、岩波書店)の第15章(“場合の数”をかぞえる - 順列・組合せ)、15.2(組合せ)、重複組合せの問27の解答を求めてみる。

0個以下のものをとった重複組合せは1通り。

(\begin{matrix} n + 0 \\ 0 \end{matrix}) = (\begin{matrix} n \\ 0 \end{matrix}) = 1

また、

\begin{array}{l} (\begin{matrix} n + (r - 1) \\ r - 1 \end{matrix}) + (\begin{matrix} n + r - 1 \\ r \end{matrix}) \\ = \frac{(n + (r - 1))!}{((n + (r - 1)) - (r - 1))! (r - 1)!} + \frac{(n + r - 1)!}{((n + r - 1) - r)! r!} \\ = \frac{(n + r - 1)!}{n! (r - 1)!} + \frac{(n + r - 1)!}{(n - 1)! r!} \\ = \frac{(r + n) (n + r - 1)!}{n! r!} \\ = \frac{(n + r)!}{((n + r) - r)! r!} \\ = (\begin{matrix} n + r \\ r \end{matrix}) \end{array}

よって、帰納法により、n個の異なるものからr個以下のものをとった重複組合せの総数は、

(\begin{matrix} n + r \\ r \end{matrix})

に等しい。

（証明終）