作者XII (Mathkid)
看板Math
標題Re: [中學] 排列組合
時間Thu Jun 25 19:00:47 2020
※ 引述《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://webptt.com/m.aspx?n=bbs/Math/M.1593082850.A.2B2.html
1F：推 pmove : 跟我在推文，最後的答案一樣 06/25 19:28
2F：→ XII : 現在高中不知是否有教(法二).. 06/25 19:33
3F：推 DrMeredith : 謝謝!^^ 06/26 20:03
4F：→ freePrester : 回 XII 沒有 06/26 20:56
5F：→ musicbox810 : 高中應該連特徵方程式都沒有教 06/27 00:53
6F：→ XII : 法一是偏大學作法, 法二是以前高中作法 06/27 09:02
7F：推 DrMeredith : 謝謝您，請問法2的做法有什麼名稱嗎？我想學習怎麼 06/27 13:04
8F：→ DrMeredith : 做><，謝謝 06/27 13:04