重複組合わせの性質


具体的な問題を解きながら、重複組み合わせの性質を調べてみましょう。

問題1


$\hspace{1em} (1)\ \ x+y+z = 7  の正の整数解の組はいくつあるか。$

$\hspace{1em} (2)\ \ x+y+z < 8  の正の整数解の組はいくつあるか。$

解説

$(1)は$

$\qquad x = x'-1, \ y = y'-1, \ z = z'-1 \qquad (x',y',z' は 0または正の整数) とおくと、$

$\hspace{3em} x'+y'+z '= 4$

$これは「 x',y',z'の異なる3個のものから4個とる重複組合せ」だから$

$\hspace{3em} _3\mathrm{H}_4 = _6\mathrm{C}_4 = _6\mathrm{C}_2 = 15 \qquad $ (通り)


$(2)は$

次のように場合分けする。
$\qquad$ (i) $x+y+z=3 $
$\qquad$ (ii) $x+y+z=4 $
$\qquad$ (iii) $x+y+z=5$
$\qquad$ (iv) $x+y+z=6 $
$\qquad$ (v) $x+y+z=7$

$これらを(1)のように解くと、順に$

$\hspace{3em} _3\mathrm{H}_0 = 1, \qquad _3\mathrm{H}_1 = 3, \qquad _3\mathrm{H}_2 = 6, \qquad _3\mathrm{H}_3 = 10, \qquad _3\mathrm{H}_4 = 15$

$となるから  全部で  1+3+6+10+15=35  (通り)$


$(2)の別解$

$ダミー変数 u (uは整数)を用いて$

$\hspace{3em} x+y+z < 8  を  x+y+z+u = 8  と考えると$

$\qquad (1) と同様にして  _4\mathrm{H}_4 = 35 通り  と、いとも簡単に求まる。$


ということは

$\hspace{3em} _3\mathrm{H}_0 + _3\mathrm{H}_1 + _3\mathrm{H}_2 + _3\mathrm{H}_3 + _3\mathrm{H}_4 = _4\mathrm{H}_4$

が成り立つということになる。

$そこで、8 \ を \ k+4 \ に置きかえて$

$\qquad x+y+z < k+4  を考える。上と同様にして$

$\qquad x'+y'+z' < k+1$

$\qquad x'+y'+z' = 0  の解が  _3\mathrm{H}_0 \ 通り$
$\qquad x'+y'+z' = 1  の解が  _3\mathrm{H}_1 \ 通り$
$\qquad \qquad \vdots$
$\qquad x'+y'+z' = k  の解が  _3\mathrm{H}_k \ 通り$

$したがって、全部で \quad _3\mathrm{H}_0 + _3\mathrm{H}_1 + \cdots + _3\mathrm{H}_k \ 通り$

$一方、ダミー整数 u を考えて$

$\hspace{3em} x+y+z+u = k+4$

よって
$\hspace{3em} x'+y'+z'+u' = k  となって、解は \ _4\mathrm{H}_k \ 通りあるから$

$\hspace{3em} _3\mathrm{H}_0 + _3\mathrm{H}_1 + \cdots + _3\mathrm{H}_k = _4\mathrm{H}_k$


ページの先頭へ↑



問題2


$\hspace{3em} _n\mathrm{H}_0 + _n\mathrm{H}_1 + \cdots +_n\mathrm{H}_r = _{n+1}\mathrm{H}_r$

 が成り立つことをを証明しなさい。

解説

$問題1で、さらに、文字数を3個からn個に拡張した不等式$

$\hspace{3em} x_1 + x_2 + \cdots + x_n < n+k+1 \qquad \qquad (1)\hspace{16em}$

$\qquad x_1' = x_1-1, \ x_2' = x_2-1, \cdots, \ x_n' = x_n-1  とおくと$

$\hspace{3em} x_1'+x_2'+ \cdots + x_n' < k+1 $

$\qquad X_n' = x_1' + x_2' + \cdots + x_n'$  とおくと

$\hspace{3em} X_n' = 0  の解が _n\mathrm{H}_0 \ 通り$
$\hspace{3em} X_n' = 1  の解が _n\mathrm{H}_1 \ 通り$
$\hspace{3em} \qquad \vdots$
$\hspace{3em} X_n' = k  の解が _n\mathrm{H}_k \ 通り$

$よって (1)の不等式の整数解は$

$\qquad _n\mathrm{H}_0 + _n\mathrm{H}_1 + \cdots + _n\mathrm{H}_k \ 個ある。$

$一方、ダミー変数 u(uは整数)を用いると、_{n+1}\mathrm{H}_k \ 個あることから$

$\qquad _n\mathrm{H}_0 + _n\mathrm{H}_1 + \cdots + _n\mathrm{H}_k = _{n+1}\mathrm{H}_k$

$kをrと置きかえて$
\[_n\mathrm{H}_0 + _n\mathrm{H}_1 + \cdots +_n\mathrm{H}_r = _{n+1}\mathrm{H}_r \]

別解

変化するのは $r$ であることに注意して、$r$ についての数学的帰納法を用いましょう。

$\qquad r = 0  のとき 左辺=1,右辺=1 よって成り立つ。$

$\qquad r = k  のとき成り立つとすると$

$\qquad _n\mathrm{H}_0 + _n\mathrm{H}_1 + \cdots + _n\mathrm{H}_k = _{n+1}\mathrm{H}_k$

このとき

$\qquad _n\mathrm{H}_0 + _n\mathrm{H}_1 + \cdots + _n\mathrm{H}_k + _n\mathrm{H}_{k+1}$
$\qquad = _{n+1}\mathrm{H}_k + _n\mathrm{H}_{k+1}$
$\qquad = _{n+k}\mathrm{C}_k + _{n+k}\mathrm{C}_{k+1}$
$\qquad = _{n+k+1}\mathrm{C}_{k+1}$
$\qquad = _{n+1}\mathrm{H}_{k+1}$

となって $r = k+1$ のときも成りたつ。


ページの先頭へ↑



問題3


$\hspace{3em} _1\mathrm{H}_r + _2\mathrm{H}_r + \cdots +_n\mathrm{H}_r = _n\mathrm{H}_{r+1}$

が成り立つことを証明しなさい。

解説

今度は $n$ が変化しています。やはり数学的帰納法で証明しましょう。

$\qquad n = 1  のとき 左辺 = _1\mathrm{H}_r =1 ,  右辺 = _1\mathrm{H}_{r+1} = 1  で成り立ちます。$

$\qquad n = k  のとき成り立つとすると$

$\hspace{3em} _1\mathrm{H}_r + _2\mathrm{H}_r + \cdots +_k\mathrm{H}_r = _k\mathrm{H}_{r+1}$

このとき

$\qquad _1\mathrm{H}_r + _2\mathrm{H}_r + \cdots +_k\mathrm{H}_r + _{k+1}\mathrm{H}_r$
$\qquad = _k\mathrm{H}_{r+1} + _{k+1}\mathrm{H}_r$
$\qquad = _{k+r}\mathrm{C}_{r+1} + _{k+r}\mathrm{C}_r$
$\qquad = _{k+r+1}\mathrm{C}_{r+1}$
$\qquad = _{k+1}\mathrm{H}_{r+1}$

となって$n = k+1$ のときも成り立つ。

これで十分なのですが、もう少しスマートにできないものでしょうか。


ページの先頭へ↑



$_n\mathrm{H}_r$ の性質



$\hspace{2em} (1) \qquad _n\mathrm{H}_r = _n\mathrm{H}_{r-1} + _{n-1}\mathrm{H}_r \qquad (n \geqq 2)$

(証明)

すでに、問題2の別解と問題3で使われているのですが、ここでは次のように考えてみましょう。

$異なる n 個のものから、重複を許して r 個とるのに$

$\quad$ (i) $r 個の中に特定の 1 個を含む場合$

$\qquad 特定の 1 個を取り出し、次にまた n 個の中から残り r-1 個を取り出すと \qquad _n\mathrm{H}_{r-1}$ 通り

$\quad$ (ii) $r 個の中に特定の 1 個を含まない場合$

$\qquad 特定の 1 個を除く (n-1) 個から r 個を取り出すから \qquad _{n-1}\mathrm{H}_r 通り$

(i),(ii)のどちらかであるから

$\hspace{3em} _n\mathrm{H}_r = _n\mathrm{H}_{r-1} + _{n-1}\mathrm{H}_r  が成り立つ。$



$\hspace{2em} (2) \qquad _1\mathrm{H}_r + _2\mathrm{H}_r + \cdots +_n\mathrm{H}_r = _n\mathrm{H}_{r+1} \qquad (n \geqq 2)$

(証明)

性質(1)より        $_n\mathrm{H}_r - _{n-1}\mathrm{H}_r = _n\mathrm{H}_{r-1}$
$\quad n\rightarrow n-1$  とおいて  $_{n-1}\mathrm{H}_r - _{n-2}\mathrm{H}_r = _{n-1}\mathrm{H}_{r-1}$
$\quad n\rightarrow n-2$  とおいて  $_{n-2}\mathrm{H}_r - _{n-3}\mathrm{H}_r = _{n-2}\mathrm{H}_{r-1}$
$\qquad \qquad \vdots$
$\quad n\rightarrow 2$    とおいて   $_2\mathrm{H}_r - _1\mathrm{H}_r = _2\mathrm{H}_{r-1}$

辺々加えて

$\quad _n\mathrm{H}_r - _1\mathrm{H}_r = _n\mathrm{H}_{r-1} + _{n-1}\mathrm{H}_{r-1} + \cdots + _2\mathrm{H}_{r-1}$

ここで、

$\quad _1\mathrm{H}_r = 1, \quad _1\mathrm{H}_{r-1} = 1 だから \quad _1\mathrm{H}_r = _1\mathrm{H}_{r-1}$

$\quad _n\mathrm{H}_r - _1\mathrm{H}_{r-1} = _n\mathrm{H}_{r-1} + _{n-1}\mathrm{H}_{r-1} + \cdots + _2\mathrm{H}_{r-1}$
$\quad _n\mathrm{H}_r = _n\mathrm{H}_{r-1} + _{n-1}\mathrm{H}_{r-1} + \cdots + _2\mathrm{H}_{r-1} + _1\mathrm{H}_{r-1}$

$\quad r\rightarrow r+1$  とおいて

$\quad _n\mathrm{H}_{r+1} = _n\mathrm{H}_r + _{n-1}\mathrm{H}_r + \cdots +_1\mathrm{H}_r$

よって

$\qquad _1\mathrm{H}_r + _2\mathrm{H}_r + \cdots +_n\mathrm{H}_r = _n\mathrm{H}_{r+1} \qquad (n \geqq 2)$


 


$\hspace{2em} (3) \qquad _n\mathrm{H}_0 + _n\mathrm{H}_1 + \cdots + _n\mathrm{H}_r = _{n+1}\mathrm{H}_r \qquad (n \geqq 2)$

(証明)

性質(1)より       $_n\mathrm{H}_r - _n\mathrm{H}_{r-1} = _{n-1}\mathrm{H}_r$
$\quad r\rightarrow r-1$  とおいて  $_n\mathrm{H}_{r-1} - _n\mathrm{H}_{r-2} = _{n-1}\mathrm{H}_{r-1}$
$\quad r\rightarrow r-2$  とおいて  $_n\mathrm{H}_{r-2} - _n\mathrm{H}_{r-3} = _{n-1}\mathrm{H}_{r-2}$
$\qquad \qquad \vdots$
$\quad r\rightarrow 1$    とおいて  $_n\mathrm{H}_1 - _n\mathrm{H}_0 = _{n-1}\mathrm{H}_1$

辺々加えて

$\quad _n\mathrm{H}_r - _n\mathrm{H}_0 = _{n-1}\mathrm{H}_r + _{n-1}\mathrm{H}_{r-1} \cdots + _{n-1}\mathrm{H}_1$

ここで

$\quad _n\mathrm{H}_0 = 1 , \quad _{n-1}\mathrm{H}_0=1 だから \quad _n\mathrm{H}_0 = _{n-1}\mathrm{H}_0$

$\quad _n\mathrm{H}_r - _{n-1}\mathrm{H}_0 = _{n-1}\mathrm{H}_r + _{n-1}\mathrm{H}_{r-1} \cdots + _{n-1}\mathrm{H}_1$
$\quad _n\mathrm{H}_r = _{n-1}\mathrm{H}_r + _{n-1}\mathrm{H}_{r-1} \cdots + _{n-1}\mathrm{H}_1 + _{n-1}\mathrm{H}_0$

$\quad n\rightarrow n+1$  とおいて

$\quad _{n+1}\mathrm{H}_r = _n\mathrm{H}_r + _n\mathrm{H}_{r-1} + \cdots + _n\mathrm{H}_0$

よって

$\qquad _n\mathrm{H}_0 + _n\mathrm{H}_1 + \cdots + _n\mathrm{H}_r = _{n+1}\mathrm{H}_r \qquad (n \geqq 2)$




ページの先頭へ↑



メインメニュー に戻る