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

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.

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.

Programs

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

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)