

A188555


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


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

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(i1) or x(i1)1.
For the bijection between arrays and words, notice that the ith 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



FORMULA

Empirical: a(n) = (1/24)*n^4  (1/12)*n^3 + (23/24)*n^2 + (13/12)*n + 3.
G.f.: (2*x^5  7*x^4 + 11*x^3  6*x^2 + 1)/(x  1)^5.
a(n) = 5*a(n1)  10*a(n2) + 10*a(n3)  5*a(n4) + a(n5) 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



KEYWORD

nonn,easy


AUTHOR



EXTENSIONS



STATUS

approved



