A396257 - OEIS

%I #38 Jul 01 2026 17:10:01

%S 1,12,54,246,1122,5118,23346,106494,485778,2215902,10107954,46107966,

%T 210323922,959403678,4376370546,19963045374,91062485778,415386338142,

%U 1894806719154,8643260919486,39426691159122,179846933956638,820381287464946,3742212569411454,17070300272127378

%N Number of n X 3 arrays over {0,1,2} such that orthogonally adjacent entries are distinct.

%C 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).

%C The recurrence can be shown by observing ((T')^2 - 5*T' + 2*I)e = 0.

%C a(n) ~ c * r^n, where r = 4.561553... is the largest root of x^2 - 5*x + 2 and c = 2.591410....

%C The initial term a(0)=1 counts the unique empty 0 X 3 array, which vacuously satisfies the adjacency restrictions.

%H Adam Reichert, <a href="/A396257/b396257.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (5,-2).

%F 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.

%F a(0) = 1, a(1) = 12, a(2) = 54, and a(n) = 5*a(n-1) - 2*a(n-2) for n >= 3.

%F From _Alois P. Heinz_, Jun 23 2026: (Start)

%F G.f.: -(4*x^2-7*x-1)/(2*x^2-5*x+1).

%F a(n) = A206144(n-1) for n>=3.

%F a(n) = 3 * A052913(n) for n>=1. (End)

%p a:= n-> `if`(n=0, 1, (<<0|1>, <-2|5>>^n.<<3,12>>)[1,1]):

%p seq(a(n), n=0..24);  # _Alois P. Heinz_, Jun 23 2026

%t LinearRecurrence[{5, -2}, {1, 12, 54}, 25] (* _Paolo Xausa_, Jul 01 2026 *)

%o (Python)

%o import numpy as np

%o def a396257(n):

%o     if n == 0:

%o         return 1

%o     T = np.array([

%o         [0,0,0,0,1,1,0,1,1,1,0,0],

%o         [0,0,0,0,1,0,1,1,1,0,0,0],

%o         [0,0,0,0,1,1,0,0,1,1,0,1],

%o         [0,0,0,0,0,1,0,0,0,1,1,1],

%o         [1,1,1,0,0,0,0,0,0,0,1,1],

%o         [1,0,1,1,0,0,0,0,0,0,1,0],

%o         [0,1,0,0,0,0,0,0,1,1,0,1],

%o         [1,1,0,0,0,0,0,0,0,1,1,1],

%o         [1,1,1,0,0,0,1,0,0,0,0,0],

%o         [1,0,1,1,0,0,1,1,0,0,0,0],

%o         [0,0,0,1,1,1,0,1,0,0,0,0],

%o         [0,0,1,1,1,0,1,1,0,0,0,0],

%o     ], dtype=object)

%o     e = np.ones(12, dtype=object)

%o     return int(e @ np.linalg.matrix_power(T, n - 1) @ e)

%Y Cf. A052913, A206144, A209042, A232922.

%K nonn,easy,new

%O 0,2

%A _Adam Reichert_, Jun 22 2026