Re: [離散] recurrence

[dqIpb (dqipb)]

※ 引述《mqazz1 (無法顯示)》之銘言：
: let Σ = {a,b,c,d}. A palindrome over Σ is a (possibly empty) sequence of
: symbols from Σ such that the sequence is the same as its reverse listing.
: So, for example, aba is a palindrome (of length 3) while aacb is not.
: Now let S(n), n>=0, denote the number of palindromes over Σ of length n
: drive a recurrence relation for S(n) for n>=2
: 請問這要怎麼導呢?
: 謝謝

設 S(n) 為題目中所述 顯然 S(0) = 1、S(1) = 4
接下來，回文有奇數長度與偶數長度的。
若現在是個奇數長度的回文，把最中間的字母砍掉後，剩下的還是回文，
但長度 -= 1；又中間字母無論是 a、b、c、d，砍掉後都形成同一個回文，所以

S(n) = S(n-1)*4，若 n 是奇數

再來偶數長度的回文，把中間兩個字母砍掉任一個會形成奇數長度的回文，所以

S(n) = S(n-1)  ，若 n 是偶數

-

只為了解題的話，可以逆推。長度為 m 的字串共有 4^m 個，而若把回文從中切開，
剩下的就是任意字串了。因此有

       / 4^(n/2)    ，若 n 是偶數
S(n) = |
       \ 4^((n+1)/2)，若 n 是奇數

所以可以得到遞迴式

       / S(n-1)*4，若 n 是奇數
S(n) = |
       \ S(n-1)  ，若 n 是偶數

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.217.34.53
推 mqazz1      :謝謝 可是我看書上寫 S(n) = 4S(n-2)..不知它怎導的
→ dqIpb       :這個顯然. n是奇數時,S(n)=4S(n-1)=4S(n-2)
→ dqIpb       :n是偶數時,S(n)=S(n-1)=4S(n-2)