A126474 Number of arrays in [1..6]^n with adjacent elements differing by three or less.

1, 6, 30, 154, 788, 4034, 20650, 105708, 541122, 2770018, 14179796, 72586754, 371573530, 1902094812, 9736874082, 49843318162, 255149275268, 1306115946338, 6686042370634, 34226029248972, 175203956722818

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

Original name: Number of base 6 n-digit numbers with adjacent digits differing by three or less.

Links

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

Formula

Conjectures from Colin Barker, Jan 20 2017: (Start)

a(n) = 5*a(n-1) + a(n-2) - 2*a(n-3) for n>2.

G.f.: (1 + x - x^2) / (1 - 5*x - x^2 + 2*x^3).

(End)

From Robert Israel, Jan 23 2018: (Start)

a(n) = e^T M^(n-1) e where e = [1,1,1,1,1,1]^T and M is the 6 X 6 matrix with entries M(i,j) = 1 if |i-j|<=3, 0 otherwise.

The fact that (M^3-5*M^2-M+2I) e = 0 implies Colin Barker's recursion, and the G.f. follows. (End)

Example

For n=2 the a(2)=30 solutions are [1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 3], [6, 4], [6, 5], [6, 6]. - Robert Israel, Jan 23 2018

Maple

f:= gfun:-rectoproc({a(n) = 5*a(n-1) + a(n-2) - 2*a(n-3), a(0)=1, a(1)=6, a(2)=30}, a(n), remember):
map(f, [$0..30]); # Robert Israel, Jan 23 2018

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 6 differing by two or less A126393, one or less A126360.

Sequence in context: A033132 A022023 A066534 * A127017 A152223 A152224

Adjacent sequences: A126471 A126472 A126473 * A126475 A126476 A126477

Keyword

nonn,base

Author

R. H. Hardin, Dec 27 2006

Status

approved