A089980 -id:A089980 - cp's OEIS frontend

A006506 Number of n X n binary matrices with no 2 adjacent 1's, or number of configurations of non-attacking princes on an n X n board, where a "prince" attacks the four adjacent (non-diagonal) squares. Also number of independent vertex sets in an n X n grid.

1, 2, 7, 63, 1234, 55447, 5598861, 1280128950, 660647962955, 770548397261707, 2030049051145980050, 12083401651433651945979, 162481813349792588536582997, 4935961285224791538367780371090, 338752110195939290445247645371206783, 52521741712869136440040654451875316861275

Offset: 0

N. J. A. Sloane, R. H. Hardin, Paul Zimmermann

A two-dimensional generalization of the Fibonacci numbers.
Also the number of vertex covers in the n X n grid graph P_n X P_n.
A181030 (Number of n X n binary matrices with no leading bitstring in any row or column divisible by 4) is the same sequence. Proof from Steve Butler, Jan 26 2015: This is trivially true. A181030 is equivalent to this sequence by interchanging the roles of 0 and 1. In particular, A181030 looks for binary matrices with no leading bitstring divisible by 4, but a bitstring is divisible by 4 if and only if its last two digits is 0; in a binary matrix this can only be avoided if there are no two adjacent 0's (i.e., for any two adjacent 0's take the bitstring starting in that row or column and we are done); the present sequence looks for no two adjacent 1's. Similar reasons show that the array A181031 is equivalent to the array A089980.
Let R(n) be the set of squares that have vertices at integer coordinates and lie in the region of the plane |x|+|y| <= n+1, and let S(n) be the set of squares that have vertices at integer coordinates and lie in the region of the plane |x|+|y-1/2| <= n+2.  Further let T be the collection of rectangular tiles with dimensions i X 1 or 1 X i with i arbitrary.  Then a(2n) is the number of ways to tile R(n) using tiles from T and a(2n+1) is the number of ways to tile S(n) using tiles from T. (Note R(n) is the Aztec diamond of order n.) - Steve Butler, Jan 26 2015

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 342-349.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jin-Guo Liu, Table of n, a(n) for n = 0..39 (terms 1..33 from Robert Gerbicz, 34..35 from P. Butera and M. Pernici, 37..38 from Casey Mills Davis)
P. Butera and M. Pernici, Sums of permanental minors using Grassmann algebra, arXiv preprint arXiv:1406.5337 [hep-lat], 2014.
Casey Mills Davis, C++ program used to generate a(n) for n = 36..37
Steven R. Finch, Hard Square Entropy Constant [Broken link]
Steven R. Finch, Hard Square Entropy Constant [From the Wayback machine]
Xuanzhao Gao, Xiaofeng Li, and Jinguo Liu, Programming guide for solving constraint satisfaction problems with tensor networks, arXiv:2501.00227 [physics.comp-ph], 2024. See p. 24.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.372.
Jin-Guo Liu, Xun Gao, Madelyn Cain, Mikhail D. Lukin and Sheng-Tao Wang, Computing solution space properties of combinatorial optimization problems via generic tensor networks, arXiv:2205.03718 [cond-mat.stat-mech], 2022. Terms 38..39.
I. Mezo, Periodicity of the Last Digits of Some Combinatorial Sequences, J. Int. Seq. 17 (2014) #14.1.1.
B. D. Stosic, T. Stosic, I. P. Fittipaldi and J. J. P. Veerman, Residual entropy of the square Ising antiferromagnet in the maximum critical field: the Fibonacci matrix, Journal of Physics A: Mathematical and General, Volume 30, Number 10, 1997, pp. L331-L337.
Peter Tittmann, Enumeration in Graphs
Eric Weisstein's World of Mathematics, (0,1)-Matrix
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hard Square Entropy Constant
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover
Index entries for sequences related to binary matrices

Cf. A027683 for toroidal version.
Table of values for n x m matrices: A089934.
Cf. A232833 for refinement by number of 1's.
Cf. also A191779.
Cf. A201511, A212270.

A006506 := proc(N) local i,j,p,q; p := 1+x11;
if n=0 then return 1 fi;
for i from 2 to N do
   q := p-select(has,p,x||(i-1)||1);
   p := p+expand(q*x||i||1)
od;
for j from 2 to N do
   q := p-select(has,p,x1||(j-1));
   p := subs(x1||(j-1)=1,p)+expand(q*x1||j);
   for i from 2 to N do
      q := p-select(has,p,{x||(i-1)||j,x||i||(j-1)});
      p := subs(x||i||(j-1)=1,p)+expand(q*x||i||j);
   od
od;
map(icontent,p)
end:
seq(A006506(n), n=0..15);

a[n_] := a[n] = (p = 1 + x[1, 1]; Do[q = p - Select[p, ! FreeQ[#, x[i-1, 1]] &]; p = p + Expand[q*x[i, 1]], {i, 2, n}]; Do[q = p - Select[p, ! FreeQ[#, x[1, j-1]] &]; p = (p /. x[i, j-1] :> 1) + Expand[q*x[1, j]]; Do[q = p - Select[ p, ! FreeQ[#, x[i-1, j]] || ! FreeQ[#, x[i, j-1]] &]; p = (p /. x[i, j-1] :> 1) + Expand[q*x[i, j]], {i, 2, n}], {j, 2, n}]; p /. x[, ] -> 1); a /@ Range[14] (* Jean-François Alcover, May 25 2011, after Maple prog. *)
Table[With[{g = GridGraph[{n, n}]}, Count[Subsets[Range[n^2], Length @ First @ FindIndependentVertexSet[g]], ?(IndependentVertexSetQ[g, #] &)]], {n, 5}] (* _Eric W. Weisstein, May 28 2017 *)

a(n)=L=fibonacci(n+2);p=v=vector(L,i,1);c=0; for(i=0,2^n-1,j=i;while(j&&j%4<3,j\=2);if(j%4<3,p[c++]=i)); for(i=2,n,w=vector(L,j,0); for(j=1,L, for(k=1,L,if(bitand(p[j],p[k])==0,w[j]+=v[k])));v=w); sum(i=1,L,v[i]) \\ Robert Gerbicz, Jun 17 2011

Limit_{n->oo} a(n)^(1/n^2) = c1 = 1.50304... is the hard square entropy constant A085850. - Benoit Cloitre, Nov 16 2003
a(n) appears to behave like A * c3^n * c1^(n^2) where c1 is as above, c3 = 1.143519129587 approximately, A = 1.0660826 approximately. This is based on numerical analysis of a(n) for n up to 19. - Brendan McKay, Nov 16 2003
From n up to 39 we have A = 1.06608266035... - Vaclav Kotesovec, Jan 29 2024

Sequence extended by Paul Zimmermann, Mar 15 1996
Maple program updated and sequence extended by Robert Israel, Jun 16 2011
a(0)=1 prepended by Alois P. Heinz, Jan 29 2024

A089934 Table T(n,k) of the number of n X k matrices on {0,1} without adjacent 0's in any row or column.

Original entry on oeis.org

2, 3, 3, 5, 7, 5, 8, 17, 17, 8, 13, 41, 63, 41, 13, 21, 99, 227, 227, 99, 21, 34, 239, 827, 1234, 827, 239, 34, 55, 577, 2999, 6743, 6743, 2999, 577, 55, 89, 1393, 10897, 36787, 55447, 36787, 10897, 1393, 89, 144, 3363, 39561, 200798, 454385, 454385, 200798

Offset: 1

Marc LeBrun, Nov 15 2003

Recurrence orders are A089935. n X 1/1 X n patterns interpreted as binary values is A003714.
Number of independent vertex sets in the P_n X P_k grid graph. - Andrew Howroyd, Jun 06 2017
All columns (or rows) are linear recurrences with constant coefficients and order of the recurrence <= A001224(k+1). - Andrew Howroyd, Dec 24 2019
The enumeration of tiling "W-shaped" polyominoes in a (n+1) X (k+1) rectangle, whose shapes are (no flipping or rotating allowed):
   .. .._.   ...     ...
   || ||_| .||_|   .||_|
       ||   ||_|   .||_|
             ||     ||_|
                     ||       ... - _Liang Kai, Apr 19 2025

			Table starts:
  ========================================================
  n\k|  1   2     3      4       5        6          7
  ---|----------------------------------------------------
  1  |  2   3     5      8      13       21         34 ...
  2  |  3   7    17     41      99      239        577 ...
  3  |  5  17    63    227     827     2999      10897 ...
  4  |  8  41   227   1234    6743    36787     200798 ...
  5  | 13  99   827   6743   55447   454385    3729091 ...
  6  | 21 239  2999  36787  454385  5598861   69050253 ...
  7  | 34 577 10897 200798 3729091 69050253 1280128950 ...
  ... - _Andrew Howroyd_, Jun 06 2017
a(2,2)=7:
  11 11 11 10 10 01 01
  11 10 01 11 01 11 10

Liang Kai, Antidiagonals n = 1..77, flattened (antidiagonals n = 1..49 from Alois P. Heinz)
Kai Liang, Independent Set Enumeration and Estimation of Related Constants of Grid Graphs, arXiv:2507.04007 [math.CO], 2025. See p. 4.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set

T(n, 0) = T(0, m) = 1. Zero based table is A089980.
Rows 1-7 are A000045, A001333, A051736, A051737, A089936, A089937, A089938.
Main diagonal is A006506.
Cf. A089935, A001224, A197054 (maximal independent sets), A218354, A003714.

step(v, S)={vector(#v, i, sum(j=1, #v, v[j]*!bitand(S[i], S[j])))}
mkS(k)={select(b->!bitand(b,b>>1), [0..2^k-1])}
T(n,k)={my(S=mkS(k), v=vector(#S, i, i==1)); for(n=1, n, v=step(v,S)); vecsum(v)} \\ Andrew Howroyd, Dec 24 2019

A181031 Array read by antidiagonals: T(n,k) = number of n X k binary matrices with no initial bit string in any row or column divisible by 4.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 5, 7, 5, 1, 1, 8, 17, 17, 8, 1, 1, 13, 41, 63, 41, 13, 1, 1, 21, 99, 227, 227, 99, 21, 1, 1, 34, 239, 827, 1234, 827, 239, 34, 1, 1, 55, 577, 2999, 6743, 6743, 2999, 577, 55, 1, 1, 89, 1393, 10897, 36787, 55447, 36787, 10897, 1393, 89, 1, 1, 144

Offset: 1

R. H. Hardin, Sep 30 2010

A089980 is essentially the same array (see the Comments by Steve Butler in A006506). - N. J. A. Sloane, Jan 27 2015

			Table starts
.1..1....1......1.......1.........1...........1............1..............1
.1..2....3......5.......8........13..........21...........34.............55
.1..3....7.....17......41........99.........239..........577...........1393
.1..5...17.....63.....227.......827........2999........10897..........39561
.1..8...41....227....1234......6743.......36787.......200798........1095851
.1.13...99....827....6743.....55447......454385......3729091.......30584687
.1.21..239...2999...36787....454385.....5598861.....69050253......851302029
.1.34..577..10897..200798...3729091....69050253...1280128950....23720149995
.1.55.1393..39561.1095851..30584687...851302029..23720149995...660647962955
.1.89.3363.143677.5980913.250916131.10496827403.439621976195.18403310404291
Some solutions for 5X5
..1..1..1..1..1....1..1..1..1..1....1..1..1..1..1....1..1..1..1..1
..1..0..1..0..1....1..0..1..0..1....1..0..1..0..1....1..0..1..0..1
..1..1..0..1..0....1..1..0..1..0....1..1..0..1..0....1..1..0..1..0
..1..0..1..0..1....1..0..1..0..1....1..0..1..0..1....1..0..1..0..1
..1..1..0..1..0....1..1..0..1..1....1..1..1..1..0....1..1..1..1..1

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

Cf. A089980.

cp's OEIS Frontend

A006506 Number of n X n binary matrices with no 2 adjacent 1's, or number of configurations of non-attacking princes on an n X n board, where a "prince" attacks the four adjacent (non-diagonal) squares. Also number of independent vertex sets in an n X n grid.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A089934 Table T(n,k) of the number of n X k matrices on {0,1} without adjacent 0's in any row or column.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A181031 Array read by antidiagonals: T(n,k) = number of n X k binary matrices with no initial bit string in any row or column divisible by 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs