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,2

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.

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)

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

Prog

(S/R) stvar $[N]:(0..M-1) init $[]:=0 asgn $[]->{*} kill +[i in 0..N-2](($[i]`-$[i+1]`>1)+($[i+1]`-$[i]`>1))

Crossrefs

Sequence in context: A211479 A318034 A326162 * A140418 A200081 A199110

Adjacent sequences: A126359 A126360 A126361 * A126363 A126364 A126365

Keyword

nonn,base

Author

R. H. Hardin, Dec 26 2006

Status

approved