Re: [中學] 排列組合

[XII (Mathkid)]

※ 引述《DrMeredith (Meredith)》之銘言：
: 有n位數字，每一位都可以選0，1，2，3放進去，但3的右邊不可以放0，請問有幾種呢？
: 不好意思毫無頭緒><，倒扣的話又扣不完@@
: -----
: Sent from JPTT on my Samsung SM-N9750.

設
a(n)=#{滿足條件且最右邊為0,1,2的n位數個數}
b(n)=#{滿足條件且最右邊為3的n位數個數}
c(n)=#{滿足條件的n位數個數}=a(n)+b(n)

易知
a(n)=a(n-1)+2*c(n-1)
b(n)=c(n-1)
c(n)=a(n)+b(n)

故
2*c(n-1)=a(n)-a(n-1)=(c(n)-b(n))+(c(n-1)-b(n-1))
  =(c(n)-c(n-1))-(c(n-1)-c(n-2))

因此 c(n)-4*c(n-1)+c(n-2)=0, c(0)=1, c(1)=4
接下來有兩種方法

(法一)
特徵方程式 x^2-4x+1=0 的根為 2+√3, 2-√3
故 c(n)=a*(2-√3)^n+b*(2+√3)^n
代入 c(0)=1, c(1)=4 可解得
c(n)=(1/6)((3+2√3)(2+√3)^n+(3-2√3)(2-√3)^n)

(法二)
令 c(n)-a*c(n-1)=b(c(n-1)-a*c(n-2))...(1)
則 a+b=4, ab=1, 故 {a,b}={2-√3,2+√3}
(1)可推得
c(n)-a*c(n-1)=b^{n-1}(c(1)-a*c(0))=4*b^{n-1}-b^{n-2}=b^n
故
c(n)-(2-√3)*c(n-1)=(2+√3)^n...(2)
c(n)-(2+√3)*c(n-1)=(2-√3)^n...(3)
(2)*(2+√3)-(3)*(2-√3) 可得
2√3*c(n)=(2+√3)(2+√3)^n-(2-√3)(2-√3)^n
故
c(n)=(1/6)((3+2√3)(2+√3)^n+(3-2√3)(2-√3)^n)

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.48.102 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1593082850.A.2B2.html
推 pmove       : 跟我在推文，最後的答案一樣
→ XII         : 現在高中不知是否有教(法二)..
推 DrMeredith  : 謝謝!^^
→ freePrester : 回 XII 沒有
→ musicbox810 : 高中應該連特徵方程式都沒有教
→ XII         : 法一是偏大學作法, 法二是以前高中作法
推 DrMeredith  : 謝謝您，請問法2的做法有什麼名稱嗎？我想學習怎麼
→ DrMeredith  : 做><，謝謝