[答1190] 碁石の並べ方

'


[答1190] 碁石の並べ方


　白黒の碁石がたくさんあって、○○○○○●●●●○○○●●●●●●○○○ のように、

　○も●も どこも３個以上続くように、全部で 21個を横１列に並べる方法の数は？


[解答1]

　いちばん左が ○でも●でも同じだけの並べ方があるので、○の場合を求め、２倍します。

　７個のブロック ○○○●●●○○○●●●○○○●●●○○○ が 1通り、

　６個のブロック ○○○●●●○○○●●●○○○●●● に 石を 3個を増やす方法は、

　 増やすブロックを 3個選べばよいので、₆Ｈ₃＝6･7･8/3!＝56 、

　５個のブロック ○○○●●●○○○●●●○○○ に 石を 6個を増やす方法は、

　 増やすブロックを 6個選べばよいので、₅Ｈ₆＝₁₀Ｃ₆＝210 、

　４個のブロック ○○○●●●○○○●●● に 石を 9個を増やす方法は、

　 増やすブロックを 9個選べばよいので、₄Ｈ₉＝₁₂Ｃ₉＝220 、

　３個のブロック ○○○●●●○○○ に 石を 12個を増やす方法は、

　 増やすブロックを 12個選べばよいので、₃Ｈ₁₂＝₁₄Ｃ₁₂＝91 、

　２個のブロック ○○○●●● に 石を 15個を増やす方法は、

　 増やすブロックを 15個選べばよいので、₂Ｈ₁₅＝₁₆Ｃ₁₅＝16 、

　１個のブロック ○○○○○○○○○○○○○○○○○○○○○ が 1通り、

　よって、2(1＋56＋210＋220＋91＋16＋1)＝1190 通りです。


[解答2]

　いちばん左が ○でも●でも同じだけの並べ方があるので、○の場合を求め、２倍します。

　○から始まり、○も●も３個以上続くようにｎ個を横１列に並べる方法を a_n 通りとすれば、

　a₁＝a₂＝0 ，a₃＝a₄＝1 で、n≧5 のとき、

　a_n＝1＋a₁＋a₂＋……＋a_n-3 、a_n-1＝1＋a₁＋a₂＋……＋a_n-4 、

　よって、a_n＝a_n-1＋a_n-3 になります。

　a₅＝a₄＋a₂＝1 ，a₆＝a₅＋a₃＝2 ，a₇＝a₆＋a₄＝3 ，a₈＝a₇＋a₅＝4 ，a₉＝a₈＋a₆＝6 ，a₁₀＝a₉＋a₇＝9 ，

　a₁₁＝a₁₀＋a₈＝13 ，a₁₂＝a₁₁＋a₉＝19 ，a₁₃＝a₁₂＋a₁₀＝28 ，a₁₄＝a₁₃＋a₁₁＝41 ，a₁₅＝a₁₄＋a₁₂＝60 ，

　a₁₆＝a₁₅＋a₁₃＝88 ，a₁₇＝a₁₆＋a₁₄＝129 ，a₁₈＝a₁₇＋a₁₅＝189 ，a₁₉＝a₁₈＋a₁₆＝277 ，a₂₀＝a₁₉＋a₁₇＝406 ，

　a₂₁＝a₂₀＋a₁₈＝595 、よって、求める場合の数は 2a₂₁＝1190 通りです。

.