A126362 Number of base 8 n-digit numbers with adjacent digits differing by one or less.

1, 8, 22, 62, 176, 502, 1436, 4116, 11814, 33942, 97582, 280676, 807574, 2324116, 6689624, 19257202, 55439298, 159611886, 459545688, 1323132230, 3809653732, 10969153364, 31583803574, 90940708414, 261850874726, 753964626300

Offset: 0

Author

R. H. Hardin, Dec 26 2006

Keywords

• nonn
• base

Comments

[Empirical] a(base,n) = a(base-1,n) + 3^(n-1) for base >= n; a(base,n) = a(base-1,n) + 3^(n-1)-2 when base=n-1.

Links

• Robert Israel, Table of n, a(n) for n = 0..2174
• Jim Bumgardner, Variations of the Componium, 2013.

Programs

Maple

f:= gfun:-rectoproc({a(n)=5*a(n-1)-6*a(n-2)-a(n-3)+2*a(n-4),a(0)=1,a(1)=8,a(2)=22,a(3)=62,a(4)=176},a(n),remember):
map(f, [$0..30]); # Robert Israel, Aug 12 2019

Formula

From Colin Barker, Nov 26 2012: (Start)

Conjecture: a(n) = 5*a(n-1) - 6*a(n-2) - a(n-3) + 2*a(n-4) for n > 4.

G.f.: -(4*x^4 + x^3 - 12*x^2 + 3*x + 1)/((2*x - 1)*(x^3 - 3*x + 1)). (End)

From Robert Israel, Aug 12 2019: (Start)

a(n) = e^T A^(n-1) e for n>=1, where A is the 8 X 8 matrix with 1 on the main diagonal and first super- and subdiagonals, 0 elsewhere, and e the column vector (1,1,1,1,1,1,1,1). Barker's conjecture follows from the fact that (A^4 - 5*A^3 + 6*A^2 + A - 2*I)*e = 0. (End)