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

Links

R. H. Hardin, Table of n, a(n) for n = 1..210

Robert Israel, Maple-assisted proof of recurrence

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

Example

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

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

Crossrefs

Column 2 of A269656.

Sequence in context: A090401 A181137 A113041 * A266497 A291020 A282087

Adjacent sequences: A269647 A269648 A269649 * A269651 A269652 A269653

Keyword

nonn

Author

R. H. Hardin, Mar 02 2016

Status

approved