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

Author

R. H. Hardin, Apr 04 2011

Keywords

• nonn
• easy

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)

Examples

			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
		

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

Crossrefs

Cf. A188553.

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)

Extensions

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