# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a228285
Showing 1-1 of 1

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

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE