OFFSET
0,2
COMMENTS
There are 12 valid row states: (0,1,0), (0,1,2), (0,2,0), (0,2,1), (1,0,1), (1,0,2), (1,2,0), (1,2,1), (2,0,1), (2,0,2), (2,1,0), (2,1,2).
The recurrence can be shown by observing ((T')^2 - 5*T' + 2*I)e = 0.
a(n) ~ c * r^n, where r = 4.561553... is the largest root of x^2 - 5*x + 2 and c = 2.591410....
The initial term a(0)=1 counts the unique empty 0 X 3 array, which vacuously satisfies the adjacency restrictions.
LINKS
Adam Reichert, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-2).
FORMULA
a(0) = 1. For n >= 1, a(n) = e' * T^(n-1) * e, where T is the 12 X 12 transfer matrix on the valid row states: T[i,j] = 1 if row state i = (x,y,z) can follow row state j = (u,v,w) (i.e., u != x, v != y, and w != z), and T[i,j] = 0 otherwise. e is the vector of all ones.
a(0) = 1, a(1) = 12, a(2) = 54, and a(n) = 5*a(n-1) - 2*a(n-2) for n >= 3.
From Alois P. Heinz, Jun 23 2026: (Start)
G.f.: -(4*x^2-7*x-1)/(2*x^2-5*x+1).
a(n) = A206144(n-1) for n>=3.
a(n) = 3 * A052913(n) for n>=1. (End)
MAPLE
a:= n-> `if`(n=0, 1, (<<0|1>, <-2|5>>^n.<<3, 12>>)[1, 1]):
seq(a(n), n=0..24); # Alois P. Heinz, Jun 23 2026
MATHEMATICA
LinearRecurrence[{5, -2}, {1, 12, 54}, 25] (* Paolo Xausa, Jul 01 2026 *)
PROG
(Python)
import numpy as np
def a396257(n):
if n == 0:
return 1
T = np.array([
[0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0],
], dtype=object)
e = np.ones(12, dtype=object)
return int(e @ np.linalg.matrix_power(T, n - 1) @ e)
CROSSREFS
KEYWORD
nonn,easy,new
AUTHOR
Adam Reichert, Jun 22 2026
STATUS
approved