順に1から\(n\)までの番号のついた\(n\)両編成の列車がある。\(n\geq2\)とする。各車両を赤色、青色、黄色のいずれか一色で塗るとき、隣あった車両の少なくとも一方が赤色となるような塗り方は何通りか。さぁ、縛りを探そう!隣あった車両の少なくとも一方が赤色ってところだね。それとも最後の一歩かな?う〜ん。今回も\(P(n)\)って置いちゃうと、\(n\)両目が赤色かどうかわからないから、やっぱりはじめの1歩かな。最初が青色か黄色なら次は赤色だし、最初が赤色なら次はなんでもいいしね。よし、じゃあ、図を書いてみよう!うん、完璧だね。これで、漸化式が立てられるよね。\(P_{n-2}\)の方は、黄色か青色の2パターンあるからね。それで、この形は三項間漸化式の典型例だから、解けるんだよ。ちなみに、この漸化式は、\(n\geq3\)で成り立つ漸化式だから、解いたあとで、\(n=2\)の時の確認が必要だよ。2P_{n}$$としておこっか。ようこちゃん、解ける?特性方程式を作って、解を求めて変形する方法だね。-1\)だから、2通りの式ができるね。2^{n+2}$$あとは、\(P_{n+1}\)を消去すればいいんだね。\frac{2^{n+2}-(-1)^{n}}{3}$$かな。次はないの?いいねぇ。Cの3人が色のついた札を1枚ずつ持っている。Cの持っている札の色はそれぞれ、赤、白、青である。Aがさいころを投げて、3の倍数の目が出たら、AはBと持っている札を交換し、その他の目が出たらAはCと札を交換する。c_{n}\)とする。c_{n-1}\)で表せ。\(a_{n}\)を求めよ。この問題が典型的な「縛り」だね。あまりに露骨だから、漸化式を立てることそのものが問題になっちゃってるよ。最後の一歩で場合分け、ていう問題だね。今まで通り、図を書いて調べてみよっか。\(n-1\)回目までの試行を\(a_{n}\)なんてまとめちゃうパターン。今回は、\(n-1\)回目までが3通りあるから、ようこちゃんが書いた図みたいになるんだね。c_{n-1}\)の関係を読み取ってみるね。AとCの札のスイッチは\(\frac{2}{3}\)だね。\frac{2}{3}a_{n-1}+\frac{1}{3}c_{n-1}$$かな。ちなみに、この式って、\(n=1\)でも成り立つことだよね。これって結構重要な確認なんだよ。2\)以上でしか成り立たない漸化式だったら、最後に\(n=1\)でもいいかどうか確認しなきゃならないからね。