急ぎです、大学数学再帰の問題難しくてがわからないです。 以下の4つの文字列を連結して新たに生成できる

急ぎです、大学数学再帰の問題難しくてがわからないです。
以下の4つの文字列を連結して新たに生成できる文字列を作る
：w”, "xx", "yy", "zzz"
例えば、"xxww "という文字列は生成可能であるが、”xxxw"は不可能である
各整数n≧1に対して、n個の文字を持つ文字列の数をtnとする
例えば、t1 = 1("w "のみ)
1. t2 t3　を求めよ
2. Tn = a tn-1 + b tn-2 + c tn-3(n>= 4)において a,b,cを求めよ
3. 各整数n≧1に対してpnをn個の文字を持つ回文(右から左に読むのと左から読んでも同じ)の文字列であるとする。pK101と等しい式は何か

t2, t3 = 3,6まではできたのですがそこからわからないです。

No.1 回答者： stomachman 回答日時： 2023/05/17 22:31

> n個の文字を持つ文字列の数をtnとする

　透視能力によれば、これはきっと「長さがnの生成可能な列がt[n]通りある」という意味なのだろうと。そして、大ヒントとして

　　t[n] = a t[n-1] + b t[n-2] + c t[n-3]

という式が与えてある。この式の意味は：
　　「長さnの生成可能な列が何通りあるかというと、
　　　　長さn-1の生成可能な列の後ろに1文字くっつけたやつがa t[n-1]通り
　　　　長さn-2の生成可能な列の後ろに2文字くっつけたやつが b t[n-2]通り
　　　　長さn-3の生成可能な列の後ろに3文字くっつけたやつがc t[n-3]通り
　　それだけである」
って意味です。a, b, cは簡単にわかるでしょう。
　そうすると、t[n]は4項間漸化式で表された。これを解けばいいんです。

　p[n] については：
　nが偶数の (n=2m)のときは、単に長さmの生成可能な列（t[n]通りある）のひとつをコピーして裏返して後ろにくっつけるだけで、生成可能な回文の列になる。逆に、長さ2mの生成可能な回文の列は、真ん中でぶった切って後ろ半分を捨てれば長さmの生成可能な列になる。だから、両者は1:1対応しており、つまりp[2m]=t[m]である。
　しかしnが奇数 (n=2m+1)のときはそう簡単にはいかない。なぜなら、生成可能な回文の列は、真ん中の1文字が"w"の場合と、真ん中の3文字が"zzz"の場合に限られる。だから、それぞれの場合について何通りあるかを検討する必要がある。（どってことないですがね。）