作者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/cn.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