- 排列组合问题二用1,2,3,4,5组成可以重复的所有n位数,其中
- 用1,2,3,4,5组成可以重复的所有n位数,其中相邻的两个数字之差的绝对值不超过一的数有多少个?
- 用1,2,3,4,5组成可以重复的所有n位数,其中相邻的两个数字之差的绝对值不超过一的数有多少个?
当n=1时，
有1 ； 2 ； 3 ； 4 ； 5。
总数a(1)=5
当n=2时，
有 11,12；21,22,23 ；32,33,34；43,44,45；54,55.
总数a(2)=13
当n=3时，
有 111,112；121,122,123 ；
211,212,221, 222,223,232, 233,234；
321,322,323, 332,333,334，343,344,345；
432,433,344，443,444,445,454,455；
543,544,545，554,555
总数a(3)=35
总数a(4)=95
总数a(5)=259
总数a(6)=707
总数a(7)=1931
...
递推关系：
a(n) = [a(n-1) + a(n-2)]×2 - 1
a(n-1)=[a(n-2) + a(n-3)]×2 - 1
两式想减，得
a(n) = 3×a(n-1) - 2×a(n-3)]
x^3 = 3x^2 - 2
解得：x1=1+√3, x2=1-√3, x3=1,
设
a(n)= u×(1+√3)^n + v×(1-√3)^n + w
由
a(1)= u×(1+√3) + v×(1-√3) + w
a(2)= u×(1+√3)^2 + v×(1-√3)^2 + w
a(3)= u×(1+√3)^3 + v×(1-√3)^3 + w
解得
u=(1/6)×(5+3√3)
v=(1/6)×(5-3√3)
w=1/3
所以通项为：
a(n)
= (1/6)×(5+3√3)×(1+√3)^n
+ (1/6)×(5-3√3)×(1-√3)^n
+ 1/3