A209041 Number of n X 2 0..3 arrays with no element equal to the average of its immediate neighbors vertically above and horizontally left.

12, 124, 1300, 13644, 143212, 1503212, 15778340, 165616044, 1738375148, 18246711388, 191525101396, 2010327432972, 21101236121548, 221487384867980, 2324824070641124, 24402324144347820, 256136983080016460, 2688520720946518588, 28219836042578578708, 296207181914391723468

Offset

1,1

Comments

a(n) ~ c * r^n, where r = 10.4964175365... is the largest root of x^3 - 11*x^2 + 5*x + 3 and c = 1.1240189192... . - Adam Reichert, Jun 04 2026

The recurrence can be shown by observing ((T')^3 - 11*(T')^2 + 5*T' + 3*I)e = 0. - Adam Reichert, Jun 05 2026

Links

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

Index entries for linear recurrences with constant coefficients, signature (11,-5,-3)

Formula

a(n) = 11*a(n-1) - 5*a(n-2) - 3*a(n-3).

G.f.: 4*x*(1 - x)*(3 + x) / (1 - 11*x + 5*x^2 + 3*x^3). - Colin Barker, Jul 08 2018

a(n) = e' * T^(n-1) * x0, where T is the 16 X 16 transfer matrix on the row states (0..3)^2: T[i][j] = 1 if row state i = (c,d) can follow row state j = (a,b); i.e., c != a and 2*d != c + b. x0 marks the valid first rows (those with differing values) and e is the all-ones vector. - Adam Reichert, Jun 05 2026

Example

Some solutions for n=4:
..3..1....1..0....2..3....1..0....1..2....0..1....0..1....2..3....1..3....2..0
..1..2....0..1....1..0....2..3....2..3....3..0....1..3....1..0....0..1....1..0
..3..3....1..3....3..2....1..3....3..0....1..1....3..0....0..3....1..0....2..0
..0..1....2..2....2..0....3..1....2..0....2..0....0..1....1..0....2..0....1..2

Prog

(Python)
import numpy as np
def a209041(n):
    T = np.array([
        [0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1],
        [0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1],
        [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1],
        [1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0],
        [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1],
        [0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1],
        [1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
        [1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0],
        [1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0],
    ], dtype=object)
    x0 = np.array([0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0], dtype=object)
    e = np.ones(16, dtype=object)
    return int(e @ np.linalg.matrix_power(T, n - 1) @ x0)
print([a209041(n) for n in range(1, 21)]) # Adam Reichert, Jun 04 2026

Crossrefs

Column 2 of A209047.

Sequence in context: A045507 A288350 A331396 * A155595 A070312 A153427

Adjacent sequences: A209038 A209039 A209040 * A209042 A209043 A209044

Keyword

nonn,easy

Author

R. H. Hardin, Mar 04 2012

Extensions

Removed qualifier "empirical" from the recurrence and generating function. - Adam Reichert, Jun 05 2026

Status

approved