|
%I #43 Mar 18 2018 17:34:26
%S 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,
%T 13,21,60,337,587,587,337,60,21,34,129,1034,2448,3631,2448,1034,129,
%U 34,55,277,3154,10414,21166,21166,10414,3154,277,55,89,595,9637,44024,126119
%N T(n,k) = Number of n X k binary arrays with top left value 1 and no two ones adjacent horizontally, vertically or nw-se diagonally.
%C Table starts
%C 1 1 2 3 5 8 13 21 34
%C 1 1 3 6 13 28 60 129 277
%C 2 3 13 35 112 337 1034 3154 9637
%C 3 6 35 133 587 2448 10414 44024 186414
%C 5 13 112 587 3631 21166 126119 745178 4416695
%C 8 28 337 2448 21166 172082 1428523 11771298 97268701
%C 13 60 1034 10414 126119 1428523 16566199 190540884 2197847780
%C 21 129 3154 44024 745178 11771298 190540884 3057290265 49208639399
%C 34 277 9637 186414 4416695 97268701 2197847780 49208639399 1105411581741
%H R. H. Hardin, <a href="/A228285/b228285.txt">Table of n, a(n) for n = 1..1300</a>
%H Doron Zeilberger, <a href="/A228285/a228285.txt">Maple code for columns of A228285 and A226444</a>
%H Doron Zeilberger, <a href="/A228285/a228285_2.txt">Maple output for columns of A228285</a>
%F Empirical for column k:
%F k=1: a(n) = a(n-1) + a(n-2).
%F k=2: a(n) = a(n-1) + 2*a(n-2) + a(n-3).
%F k=3: a(n) = a(n-1) + 5*a(n-2) + 4*a(n-3) - a(n-5) with g.f. x(2+x-x^3)/((1+x)(1-2x-3x^2-x^3+x^4)).
%F k=4: a(n) = a(n-1) +10*a(n-2) +15*a(n-3) +4*a(n-4) -6*a(n-5) -a(n-6) +3*a(n-7) -a(n-8) with g.f. x *(x-1) *(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 ).
%F k=5: [order 13] - see A228280.
%F k=6: [order 21]
%F k=7: [order 34]
%F k=8: [order 55]
%F k=9: [order 89]
%F From _Doron Zeilberger_, Aug 19 2013 and Aug 22 2013: (Start)
%F Using the C-finite Ansatz one can show that the k-th 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.
%F 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}).
%F Then the computer constructs the adjacency matrix.
%F 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 <= k-1) such that v1[i]=1 and v2[i+1]=1.
%F Let us call this matrix A(k).
%F Then the number of k X n Hardin matrices (without the restriction that the top-left 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.
%F So
%F f_k(x) = Sum_{n>=0} a(n)*x^n
%F = (1,...., 1) Sum_{n>=0} A(k)^n*x^n (1, ...., 1)^T
%F = (1,...., 1) (I-A*x)^(-1)(1, ...., 1)^T
%F and Maple knows how to invert the symbolic matrix (I-A*x), and this explains why the characteristic polynomial is the symbol for the recurrence.
%F If we impose that restriction then the answer (A228285) is
%F [0-1-Vector with 1's for those whose first entry is 1] A(k)^n (1, ...., 1)^T.
%F (End)
%e Some solutions for n=4, k=4:
%e 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0
%e 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
%e 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
%e 0 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0
%Y Column 1 is A000045.
%Y Column 2 is A002478(n-1).
%Y For columns 3 through 9 see A228278, A228279, A228280, A228281, A228282, A228283, A228284.
%Y For the main diagonal (n X n matrices) see A228277.
%Y If the requirement that the top corner is 1 is omitted we get A226444.
%Y If the "nw-se" condition in the definition is changed to "ne-sw", we get A228476-A228482.
%Y See also A228390 and A228506 for other variants.
%K nonn,tabl
%O 1,4
%A _R. H. Hardin_, Aug 19 2013
%E Edited by _N. J. A. Sloane_, Aug 22 2013
%E Minor corrections and further edits by _M. F. Hasler_, Apr 28 2014
| 