二項定理を使いたくないんですが・・

質問

横一列に並んだ２ｎ人(ｎは自然数)の子供から
(ⅰ)どの子供も赤青黄のカードを持っている
(ⅱ)左端の子供から順に赤青黄のいずれかのカードを出していき、同じ色のカードを出した2人をペアにする。同じカードの色が3枚以上出る場合は左から順に2人ずつをペアにする。
という条件をみたして2人ずつのペアにする。
(１)黄のカードを出した子供がいないとき、ｎ組のペアができるカードの出し方は何通りあるか。
(２)ペアをつくれない子供が2人いるカードの出し方は何通りか
という問題なんですが、解答には二項定理を使っています。わからなくはないんですが得意ではないから違う解法を考えています。解答にも(１)は　１番目から２ｎ－１番目までは２^２ｎ－１通りある。このとき赤と青の一方が偶数枚、他方が奇数枚だから、２ｎ番目は奇数枚の色を出せばよいから　２^２ｎ－１×１＝２^２ｎ－１通り…答
とありこれはわかったんですが(２)は二項定理を使ったものしかないんです。なにかほかの解法をできたら教えてください。

回答No.1

noname#71195 · ベストアンサー

全て出し終わったとき、R,G,Bのうち一つが偶数枚で、他二つは奇数枚であればよいわけです。状態遷移の考え方で解きます。

2k枚出し終わったときのそれぞれの色の偶奇は、次の二つの背反な場合に分類され、これらは全ての場合を尽くしています。

(A-2k)R,G,B全てが偶数枚。
(B-2k)R,G,Bのうち一つが偶数枚で、他二つは奇数枚。

(B-2k)の場合の数をX(2k)としましょう。このとき、(A-2k)の場合の数は3^2k-X(2k)であり、求める場合の数、すなわち(B-2n)の場合の数はX(2n)です。

では状態遷移を考えましょう。図が書けないのでわかりにくいですが、(A-2k)から(B-2k+2)への遷移は6通り、(B-2k)から(B-2k+2)への遷移は7通りあります。すなわち、

X(2k+2)=6(3^2k-X(2k))+7X(2k)
=6(3^2k)+X(2k)

が成り立ちます。これは階差の形をしているので、一般項はすぐ求まります。X(0)=0と考えます(R=G=B=0なので。)

X(2n)=0+Σ(k=0 to n-1){6(3^2k)}
=6*((3^2n)-1)/(3^2-1)
=(3/4)((3^2n)-1) ...(答)

お礼

ありがとうございます！これでもう一回やってみます！