重複組合わせの性質


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

問題１


$\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'の異なる３個のものから４個とる重複組合せ」だから$

$\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$


ページの先頭へ↑



問題２


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

$が成り立つことをを証明しましょう。$

$解説$

$問題１で、さらに、文字数を３個から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 　のとき　左辺＝１，右辺＝１　よって成り立つ。$

$\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 のときも成りたつ。$


ページの先頭へ↑



問題３


$\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)$

$(証明)$

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

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

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

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

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

$\qquad 特定の １ 個を除く (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)$



ページの先頭へ↑




メインメニュー　に戻る