A188555 Number of 4 X n binary arrays without the pattern 0 1 diagonally, vertically, antidiagonally or horizontally.

1, 5, 9, 16, 28, 48, 80, 129, 201, 303, 443, 630, 874, 1186, 1578, 2063, 2655, 3369, 4221, 5228, 6408, 7780, 9364, 11181, 13253, 15603, 18255, 21234, 24566, 28278, 32398, 36955, 41979, 47501, 53553, 60168, 67380, 75224, 83736, 92953, 102913, 113655, 125219

Offset

0,2

Comments

Row 4 of A188553.

From Miquel A. Fiol, Feb 06 2024: (Start)

a(n) is the number of words of length n, x(1)x(2)...x(n), on the alphabet {0,1,...4}, such that, for i=2,...,n, x(i)=either x(i-1) or x(i-1)-1.

For the bijection between arrays and words, notice that the i-th column consists of 1's and then 0's, and there are x(i)=0 to 4 of 1's.

The number of such words satisfy the recurrence given below and, hence, the empirical/conjectured formulas become true. (End)

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (terms n = 1..200 from R. H. Hardin)

Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Formula

Empirical: a(n) = (1/24)*n^4 - (1/12)*n^3 + (23/24)*n^2 + (13/12)*n + 3.

Conjectures from Colin Barker, Apr 27 2018: (Start)

G.f.: -(2*x^5 - 7*x^4 + 11*x^3 - 6*x^2 + 1)/(x - 1)^5.

a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n > 5. (End)

Example

Some solutions for 4 X 3:
  1 1 1    1 1 1    1 1 1    1 1 1    1 0 0    1 1 1    1 1 0
  1 1 0    1 1 1    1 1 1    1 1 1    0 0 0    1 1 1    0 0 0
  0 0 0    1 1 0    0 0 0    1 1 1    0 0 0    1 1 1    0 0 0
  0 0 0    1 0 0    0 0 0    1 1 0    0 0 0    0 0 0    0 0 0
For these solutions, the corresponding words are 221, 432, 222, 443, 100, 333, 110. - Miquel A. Fiol, Feb 06 2024

Crossrefs

Cf. A188553.

Sequence in context: A233184 A356675 A072174 * A020958 A020750 A020713

Adjacent sequences: A188552 A188553 A188554 * A188556 A188557 A188558

Keyword

nonn,easy

Author

R. H. Hardin, Apr 04 2011

Extensions

a(0)=1 prepended by Alois P. Heinz, Feb 10 2024

Status

approved