login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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

R. H. Hardin, Table of n, a(n) for n = 1..1300

Doron Zeilberger, Maple code for columns of A228285 and A226444

Doron Zeilberger, Maple output for columns of A228285

FORMULA

Empirical for column k:

k=1: a(n) = a(n-1) + a(n-2).

k=2: a(n) = a(n-1) + 2*a(n-2) + a(n-3).

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

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

k=5: [order 13] - see A228280.

k=6: [order 21]

k=7: [order 34]

k=8: [order 55]

k=9: [order 89]

From Doron Zeilberger, Aug 19 2013 and Aug 22 2013: (Start)

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.

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 <= k-1) 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 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.

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) (I-A*x)^(-1)(1, ...., 1)^T

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.

If we impose that restriction then the answer (A228285) is

[0-1-Vector 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

Column 1 is A000045.

Column 2 is A002478(n-1).

For columns 3 through 9 see A228278, A228279, A228280, A228281, A228282, A228283, A228284.

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 "nw-se" condition in the definition is changed to "ne-sw", we get A228476-A228482.

See also A228390 and A228506 for other variants.

Sequence in context: A003986 A123603 A228506 * A020908 A240873 A208882

Adjacent sequences:  A228282 A228283 A228284 * A228286 A228287 A228288

KEYWORD

nonn,tabl

AUTHOR

R. H. Hardin, Aug 19 2013

EXTENSIONS

Edited by N. J. A. Sloane, Aug 22 2013

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 15 02:19 EDT 2019. Contains 327062 sequences. (Running on oeis4.)