A269650 Number of length-n 0..2 arrays with no adjacent pair x,x+1 repeated.

3, 9, 27, 79, 225, 626, 1710, 4605, 12259, 32320, 84504, 219356, 565816, 1451349, 3704271, 9412153, 23818707, 60055275, 150913073, 378064818, 944442242, 2353140149, 5848794543, 14504575980, 35894673012, 88654500384, 218560230944

Offset: 1

Author

R. H. Hardin, Mar 02 2016

Keywords

• nonn

Examples

			Some solutions for n=9:
..1. .2. .2. .0. .0. .2. .1. .2. .2. .2. .0. .0. .2. .1. .1. .0
..1. .1. .0. .0. .0. .0. .2. .1. .1. .2. .2. .2. .0. .1. .2. .0
..1. .2. .2. .0. .0. .1. .0. .0. .0. .1. .2. .2. .1. .1. .2. .0
..1. .1. .1. .0. .2. .0. .2. .1. .2. .2. .0. .2. .2. .1. .1. .1
..0. .1. .0. .2. .1. .0. .2. .1. .2. .0. .2. .2. .1. .2. .0. .1
..0. .0. .1. .0. .1. .2. .2. .2. .2. .2. .2. .0. .1. .2. .0. .1
..2. .2. .2. .2. .2. .0. .2. .2. .1. .2. .2. .2. .0. .0. .2. .0
..0. .2. .0. .0. .2. .0. .1. .2. .2. .0. .2. .0. .0. .0. .2. .2
..2. .2. .0. .1. .0. .2. .1. .0. .2. .1. .2. .2. .0. .1. .2. .1
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..210
• Robert Israel, Maple-assisted proof of recurrence

Crossrefs

Column 2 of A269656.

Programs

Maple

T:= Matrix(12,12):
for i from 1 to 12 do T[i,i]:= 1 od:
T[1,6]:= 1: T[3,8]:= 1:
T[5,11]:= 1: T[6,12]:= 1:
for i from 1 to 4 do T[i,i+8]:= 1; T[i+4,i]:= 1; T[i+8,i]:= 1; T[i+8,i+4]:= 1 od:
u:= <1,0,0,0,1,0,0,0,1,0,0,0>: v:= <1$12>:
seq(u^%T . T^i . v, i = 0 .. 50); # Robert Israel, Apr 19 2023

Formula

Empirical: a(n) = 9*a(n-1) - 33*a(n-2) + 66*a(n-3) - 84*a(n-4) + 75*a(n-5) - 47*a(n-6) + 21*a(n-7) - 6*a(n-8) + a(n-9).

Empirical g.f.: x*(1 - 2*x + x^2 - x^3)*(3 - 12*x + 18*x^2 - 14*x^3 + 5*x^4 - x^5) / (1 - 3*x + 2*x^2 - x^3)^3. - Colin Barker, Jan 25 2019

Empirical recurrence verified (see link). - Robert Israel, Apr 19 2023