Question

用12345组成可以重复的n位数中,相邻的两个数字之差的绝对值不超过1,问：这样的n位数有几个?

Answer 1

A(n,i)表示高位是i的统计结果.

A(n+1,1)=A(n,1)+A(n,2)

A(n+1,2)=A(n,1)+A(n,2)+A(n,3)

A(n+1,3)=　　　　A(n,2)+A(n,3)+A(n,4)

A(n+1,4)=　　　　　　　A(n,3)+A(n,4)+A(n,5)

A(n+1,5)=　　　　　　　　　　A(n,4)+A(n,5)

汇总：An+1 =3An-A(n,1)-A(n,5),由对称性,A(n,1)=A(n,5) A(n,2)=A(n,4)

=3An -2A(n,1)

很难出公式