Re: [中學] 排列組合
※ 引述《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
推
06/25 19:28,
5年前
, 1F
06/25 19:28, 1F
→
06/25 19:33,
5年前
, 2F
06/25 19:33, 2F
推
06/26 20:03,
5年前
, 3F
06/26 20:03, 3F
→
06/26 20:56,
5年前
, 4F
06/26 20:56, 4F
→
06/27 00:53,
5年前
, 5F
06/27 00:53, 5F
→
06/27 09:02,
5年前
, 6F
06/27 09:02, 6F
推
06/27 13:04,
5年前
, 7F
06/27 13:04, 7F
→
06/27 13:04,
5年前
, 8F
06/27 13:04, 8F
討論串 (同標題文章)
