[答1190] 碁石の並べ方
'
[答1190] 碁石の並べ方
白黒の碁石がたくさんあって、○○○○○●●●●○○○●●●●●●○○○ のように、
○も●も どこも3個以上続くように、全部で 21個を横1列に並べる方法の数は?
[解答1]
いちばん左が ○でも●でも同じだけの並べ方があるので、○の場合を求め、2倍します。
7個のブロック ○○○●●●○○○●●●○○○●●●○○○ が 1通り、
6個のブロック ○○○●●●○○○●●●○○○●●● に 石を 3個を増やす方法は、
増やすブロックを 3個選べばよいので、6H3=6・7・8/3!=56 、
5個のブロック ○○○●●●○○○●●●○○○ に 石を 6個を増やす方法は、
増やすブロックを 6個選べばよいので、5H6=10C6=210 、
4個のブロック ○○○●●●○○○●●● に 石を 9個を増やす方法は、
増やすブロックを 9個選べばよいので、4H9=12C9=220 、
3個のブロック ○○○●●●○○○ に 石を 12個を増やす方法は、
増やすブロックを 12個選べばよいので、3H12=14C12=91 、
2個のブロック ○○○●●● に 石を 15個を増やす方法は、
増やすブロックを 15個選べばよいので、2H15=16C15=16 、
1個のブロック ○○○○○○○○○○○○○○○○○○○○○ が 1通り、
よって、2(1+56+210+220+91+16+1)=1190 通りです。
[解答2]
いちばん左が ○でも●でも同じだけの並べ方があるので、○の場合を求め、2倍します。
○から始まり、○も●も3個以上続くようにn個を横1列に並べる方法を an 通りとすれば、
a1=a2=0 ,a3=a4=1 で、n≧5 のとき、
an=1+a1+a2+……+an-3 、an-1=1+a1+a2+……+an-4 、
よって、an=an-1+an-3 になります。
a5=a4+a2=1 ,a6=a5+a3=2 ,a7=a6+a4=3 ,a8=a7+a5=4 ,a9=a8+a6=6 ,a10=a9+a7=9 ,
a11=a10+a8=13 ,a12=a11+a9=19 ,a13=a12+a10=28 ,a14=a13+a11=41 ,a15=a14+a12=60 ,
a16=a15+a13=88 ,a17=a16+a14=129 ,a18=a17+a15=189 ,a19=a18+a16=277 ,a20=a19+a17=406 ,
a21=a20+a18=595 、よって、求める場合の数は 2a21=1190 通りです。
.