数学切り抜き帳
 数学目次へ
重複組み合わせの数
桜花学園大学教授
岩井　齊良
　異なる n 個のものから重複を許して r 個のものを取り出す場合の数 nHr は，公式

　　　　　　　　　　　　 nHr ＝ n+r-1Cr

によって求められる。この公式を説明しよう．

●　自動販売機による説明
　次のようなジュースの販売機があるとする．

　それぞれの図柄のボタンを押すと，ボタンの下からそのジュースが出てくる．
　この販売機で合計5本のジュースを取り出す場合をすべて挙げると次のようになる．

(5，0，0)
(4，1，0)
(4，0，1)
(3，2，0)
(3，1，1) (3，0，2)
(2，3，0)
(2，2，1) (2，1，2) (2，0，3)
(1，4，0)
(1，3，1) (1，2，2) (1，1，3) (1，0，4)
(0，5，0)
(0，4，1) (0，3，2) (0，2，3) (0，1，4) (0，0，5)

　これを次のイラストで示す．

　○ はジュースを表す．｜ は3つの取り出し口の間の仕切りである．
　ここには，

　　　　2個の ｜ と5 個の ○ の並べ替え

のすべてが挙げられている．
　これらの場合の数は，

　　　　　　2+5C5＝21

である．

　自動販売機で売られるジュースの種類が n で，取り出すジュースの数が r のとき，ジュースの取り出し方は，

　　　　n-1 個の │ と r 個の ○ の並べ替え

で表される．ジュースの総数が r で，仕切りの数が n−1 である．
　そして，これらの場合の数は，

　　　　　　　n+r-1Cr

である．

　以上のことから，

n 個のもの r 個を取り出す重複組み合わせ ←→ n-1 個の │ と r 個の ○ の並べ替え

という1対1対応が成り立つ．
　したがって，
　異なる n 個のものから重複を許して r 個のものを取り出す場合の数 nHr は，

　　　　　　　　　　　　 nHr ＝ n+r-1Cr

となる．

　ここでは，公式 nHr ＝ n+r-1Cr を覚えるのではなく，重複組み合わせと○｜の並びとの1対1対応も覚えよう．

●　自然数解
　8を3つの自然数の和として表す方法，つまり

　　　　　X＋Y＋Z＝8

となる自然数の解 (X，Y，Z) の個数について考えてみよう．

　この答は次の21個である．

6＋1＋1
5＋2＋1
 5＋1＋2
4＋3＋1
 4＋2＋2 4＋1＋3
3＋4＋1
 3＋3＋2 3＋2＋3 3＋1＋4
2＋5＋1
 2＋4＋2 2＋3＋3 2＋2＋4 2＋1＋5
1＋6＋1
 1＋5＋2 1＋4＋3 1＋3＋4 1＋2＋5 1＋1＋6

　この場合の数を求める方法として次のモデルを考えよう．

　8個の○を並べる

　　　　　○○○○○○○○

　8個の○の間には7個のすき間がある．
　そのうち2個所のすき間を選ぶことによって，8個の○は3つのグループに分かれる．

これらのパターンが上の和と1対1に対応している．つまり，

8を3つの自然数の和として表す ←→ 8個の○のすき間（7個）から2つを選ぶ

という1対1対応が成り立つ．
　これらの場合の数は，

　　　　7C2＝21

である．

　以上のことを一般化すると，

N を r 個の自然数の和として表す ←→ N 個の○の並びのすき間（N−1個）から r-1 個を選ぶ

という1対1対応が成り立つ．
　したがって，これらの場合の数は，

　　　　　　　　N-1Cr-1

である．

●　自然数解，非負整数解，重複組み合わせ
　前項では，

　　　[1]　X1＋X2＋X3＋…＋Xr＝N，　X1，X2，X3，…，Xr は自然数

という方程式の解 (X1，X2，X3，…，Xr ) について考えた．
　これに対し，

　　　[2]　x1＋x2＋x3＋…＋xr＝n，　x1，x2，x3，…，xr は0以上の整数

という方程式の解 (x1，x2，x3，…，xr ) について考えよう．

　[1] の解 (X1，X2，X3，…，Xr ) に対し，

　　　　　(X1−1)＋(X2−1)＋(X3−1)＋…＋(Xr−1)＝N−r

つまり，n＝N−r とした [2] の解
(x1，x2，x3，…，xr )＝(X1−1，X2−1，X3−1，…，Xr−1) が対応する．
　また，[2] の解 (x1，x2，x3，…，xr) に対し，

　　　　　(x1＋1)＋(x2＋1)＋(x3＋1)＋…＋(xr＋1)＝n＋r

つまり，N＝n＋r とした [1] の解
(X1，X2，X3，…，Xr)＝(x1＋1，x2＋1，x3＋1，…，xr＋1) が対応する．
　さらに， [2] の解は r 個のものから n 個のものを取り出す重複組み合わせと対応する．