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

1, 6, 16, 44, 122, 340, 950, 2658, 7442, 20844, 58392, 163594, 458356, 1284250, 3598338, 10082246, 28249720, 79153804, 221783810, 621424108, 1741191198, 4878708658, 13669836930, 38302030548, 107319902744, 300703682402

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.

Leading 0's are allowed. - Robert Israel, Aug 12 2019

Links

Robert Israel, Table of n, a(n) for n = 0..2231

Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, and Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Formula

From Colin Barker, Nov 26 2012: (Start)

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

G.f.: -(x^3 + 5*x^2 - 2*x - 1)/(x^3 + 3*x^2 - 4*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 6 X 6 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).

Barker's conjecture follows from the fact that (A^3 - 4*A^2 + 3*A + 1) e = 0. (End)

Maple

A:=LinearAlgebra:-ToeplitzMatrix([1, 1, 0, 0, 0, 0], symmetric):
e:= Vector(6, 1):
1, seq(e^%T . A^n . e, n=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: A010915 A352115 A260384 * A264545 A296855 A105465

Adjacent sequences: A126357 A126358 A126359 * A126361 A126362 A126363

Keyword

nonn,base

Author

R. H. Hardin, Dec 26 2006

Status

approved