login
A126480
Number of base 12 n-digit numbers with adjacent digits differing by three or less.
3
1, 12, 72, 448, 2816, 17780, 112440, 711504, 4503320, 28505304, 180439880, 1142206528, 7230339936, 45769222384, 289726772704, 1834018988272, 11609648360160, 73491027329888, 465210573030272, 2944861245639136
OFFSET
0,2
COMMENTS
Empirical: a(base,n) = a(base-1,n)+7^(n-1) for base>=3n-2; a(base,n) = a(base-1,n)+7^(n-1)-2 when base=3n-3.
Note that this allows leading 0's.
For n >= 1, a(n) = e' M^(n-1) e where M is the 12 x 12 matrix with M[i,j] = 1 for |i-j| <= 3, 0 otherwise, and e is the column vector of 12 1's. The recurrence follows from the fact that (M^5 - 8 M^4 + 8 M^3 + 18 M^2 - 10 M - 6 I) e = 0. - Robert Israel, May 08 2014
FORMULA
G.f.: (1+4*x-16*x^2-14*x^3+14*x^4+6*x^5)/(1-8*x+8*x^2+18*x^3-10*x^4-6*x^5). - Robert Israel, May 08 2014
Recurrence: a(n+5) = 8*a(n+4)-8*a(n+3)-18*a(n+2)+10*a(n+1)+6*a(n) for n >= 1. - Robert Israel, May 08 2014
MAPLE
M:= Matrix(12, 12, (i, j) -> `if`(abs(i-j)<=3, 1, 0));
e:= Vector(12, 1);
A126480:= n -> e^%T . M^(n-1) . e;
A126480(0):= 1;
seq(A126480(n), n=0..100); # Robert Israel, May 08 2014
MATHEMATICA
LinearRecurrence[{8, -8, -18, 10, 6}, {1, 12, 72, 448, 2816, 17780}, 30] (* Harvey P. Dale, Jun 12 2017 *)
PROG
(S/R) stvar $[N]:(0..M-1) init $[]:=0 asgn $[]->{*} kill +[i in 0..N-2](($[i]`-$[i+1]`>3)+($[i+1]`-$[i]`>3))
CROSSREFS
Cf. Base 12 differing by two or less A126399, one or less A126366.
Sequence in context: A035472 A036398 A125322 * A030235 A088166 A138402
KEYWORD
nonn,base
AUTHOR
R. H. Hardin, Dec 27 2006
STATUS
approved