問題13582(友人問)
赤い玉、青い玉、黄色い玉合わせて12個を横一列に並べるとき、以下の条件をみたす並べ方は何通りあるか。ただし、並べる玉の色が2種類以下の場合も考えるものとする。
条件:どの玉に対しても、その玉と同じ色で、その玉に隣接するような玉が存在する。
解答
・わたしの…
左か右が同じ色…
間の11ヶ所が...同じ色同士を結ぶとき0, 異なるとき1とすると、
両端は0で、1-1はありえないので…
1が0個…3
1が1個…2H8=9C1=9
1が2個…3H6=8C2=28
1が3個…4H4=7C3=35
1が4個…5H2=6C2=15
1が5個…6H0=5C0=1
so…
3*(1+2*9+2^2*28+2^3*35+2^4*15+2^5*1)
=2049 通り
だと思う ^^
↑
ミスってましたわ ^^;
赤字で訂正 Orz〜
(鍵コメT様ご指摘グラッチェ〜m(_ _)m〜)
・鍵コメT様からのもの Orz〜♪
次の方法も有力です. 「合わせて12個」でなく「合わせてn個」のときの場合の数をa[n]とする. n≧3のときを考える. a[n]通りのそれぞれは,右端2個は必ず同色である. ・これらa[n]通りのうち,右端3個が同色である並べ方は, 玉n-1個で条件を満たす並べ方に,右端と同色の玉を付け加えて得られ, その数はa[n-1]通り. ・それ以外の並べ方は,玉n-2個で条件を満たす並べ方を元に, 右端以外の色(2通り)の玉を2つ付け加えて得られ, その数は2a[n-2]通り. よって,a[n]=a[n-1]+2a[n-2]である.
a[1]=0,a[2]=3より,順次求めることができて, a[3]=3,a[4]=9,a[5]=15,a[6]=33,a[7]=63,a[8]=129, a[9]=255,a[10]=513,a[11]=1023,a[12]=2049. 以上より,求める数は,2049通り.
なお,一般項は,a[n]=2^(n-1)+(-1)^nとなります.
*一般項はたしかにそのように推測できますが…
わたしにゃ、求められましぇん…^^;…
・鍵コメT様からの一般項の求め方のご呈示 Orz〜♪
一般項の求め方も書いておきます.
a[n]=a[n-1]+2a[n-2]は a[n]+a[n-1]=2(a[n-1]+a[n-2])と変形される. これより,a[2]+a[1],a[3]+a[2],a[4]+a[3],…は公比2の等比数列となり, a[n+1]+a[n]=(a[2]+a[1])*(2^(n-1))=3*2^(n-1).…[1] また, a[n]-2a[n-1]=-(a[n-1]-2a[n-2])とも変形され, a[2]-2a[1],a[3]-2a[2],a[4]-2a[3],…は公比-1の等比数列となり, a[n+1]-2a[n]=(a[2]-2a[1])*((-1)^(n-1))=3*(-1)^(n-1).…[2]
[1]-[2]から,3a[n]=3*2^(n-1)+3*(-1)^nとなって, a[n]=2^(n-1)+(-1)^n.
*なるほどぉ〜☆
but...こんなのわたしにゃやっぱり無理だす…^^;v
|