

A228285


T(n,k) = Number of n X k binary arrays with top left value 1 and no two ones adjacent horizontally, vertically or nwse diagonally.


22



1, 1, 1, 2, 1, 2, 3, 3, 3, 3, 5, 6, 13, 6, 5, 8, 13, 35, 35, 13, 8, 13, 28, 112, 133, 112, 28, 13, 21, 60, 337, 587, 587, 337, 60, 21, 34, 129, 1034, 2448, 3631, 2448, 1034, 129, 34, 55, 277, 3154, 10414, 21166, 21166, 10414, 3154, 277, 55, 89, 595, 9637, 44024, 126119
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Table starts
1 1 2 3 5 8 13 21 34
1 1 3 6 13 28 60 129 277
2 3 13 35 112 337 1034 3154 9637
3 6 35 133 587 2448 10414 44024 186414
5 13 112 587 3631 21166 126119 745178 4416695
8 28 337 2448 21166 172082 1428523 11771298 97268701
13 60 1034 10414 126119 1428523 16566199 190540884 2197847780
21 129 3154 44024 745178 11771298 190540884 3057290265 49208639399
34 277 9637 186414 4416695 97268701 2197847780 49208639399 1105411581741


LINKS



FORMULA

Empirical for column k:
k=1: a(n) = a(n1) + a(n2).
k=2: a(n) = a(n1) + 2*a(n2) + a(n3).
k=3: a(n) = a(n1) + 5*a(n2) + 4*a(n3)  a(n5) with g.f. x(2+xx^3)/((1+x)(12x3x^2x^3+x^4)).
k=4: a(n) = a(n1) +10*a(n2) +15*a(n3) +4*a(n4) 6*a(n5) a(n6) +3*a(n7) a(n8) with g.f. x *(x1) *(2*x^3 5*x^2 6*x 3) / ( 1 x 10*x^2 15*x^3 4*x^4 +6*x^5 +x^6 3*x^7 +x^8 ).
k=6: [order 21]
k=7: [order 34]
k=8: [order 55]
k=9: [order 89]
Using the Cfinite Ansatz one can show that the kth column satisfies a recurrence of order F_{k+2} for all k. For k <= 11, this is the minimal order. The empirical g.f.'s given above are correct. For further g.f.'s and Maple code, see the links.
In more detail: Every k X n Hardin matrix can be viewed as a walk, of length n, on a graph with F_{k+2} vertices (labeled by the set of {0,1} vectors of length k that avoid two consecutive 1's, which is well known and fairly easy to see has cardinality F_{k+2}).
Then the computer constructs the adjacency matrix.
There is an edge between vertex v1 and vertex v2 only if it NOT the case that there exists an i (1 <= i <= k) such that v1[i]=1 and v2[i]=1 AND it is not the case that there exists an i (1 <= i <= k1) such that v1[i]=1 and v2[i+1]=1.
Let us call this matrix A(k).
Then the number of k X n Hardin matrices (without the restriction that the topleft entry is 1, A226444) is the sum of the entries (i,j) of A(k)^n, or equivalently (1,...., 1) A(k)^n (1, ...., 1)^T.
So
f_k(x) = Sum_{n>=0} a(n)*x^n
= (1,...., 1) Sum_{n>=0} A(k)^n*x^n (1, ...., 1)^T
= (1,...., 1) (IA*x)^(1)(1, ...., 1)^T
and Maple knows how to invert the symbolic matrix (IA*x), and this explains why the characteristic polynomial is the symbol for the recurrence.
If we impose that restriction then the answer (A228285) is
[01Vector with 1's for those whose first entry is 1] A(k)^n (1, ...., 1)^T.
(End)


EXAMPLE

Some solutions for n=4, k=4:
1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0


CROSSREFS

For the main diagonal (n X n matrices) see A228277.
If the requirement that the top corner is 1 is omitted we get A226444.
If the "nwse" condition in the definition is changed to "nesw", we get A228476A228482.


KEYWORD



AUTHOR



EXTENSIONS

Minor corrections and further edits by M. F. Hasler, Apr 28 2014


STATUS

approved



