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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
(Formerly M1816)
33
2, 7, 63, 1234, 55447, 5598861, 1280128950, 660647962955, 770548397261707, 2030049051145980050, 12083401651433651945979, 162481813349792588536582997, 4935961285224791538367780371090, 338752110195939290445247645371206783, 52521741712869136440040654451875316861275 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

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 (A006506) 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

REFERENCES

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

LINKS

Robert Gerbicz and P. Butera and M. Pernici, Table of n, a(n) for n = 1..35 (terms 34..35 from P. Butera and M. Pernici)

P. Butera, M. Pernici, Sums of permanental minors using Grassmann algebra, arXiv preprint arXiv:1406.5337, 2014

S. R. Finch, Hard Square Entropy Constant

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.372

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

FORMULA

Limit n ->infty (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

MAPLE

A006506 := proc(N) local i, j, p, q; p := 1+x11;

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:

MATHEMATICA

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

PROG

(PARI) 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

CROSSREFS

Cf. A027683 for toroidal version.

Table of values for n x m matrices: A089934.

Cf. also A191779.

Cf. A201511, A212270.

Sequence in context: A228906 A100523 A181030 * A011821 A117263 A046855

Adjacent sequences:  A006503 A006504 A006505 * A006507 A006508 A006509

KEYWORD

nonn,nice,hard

AUTHOR

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

EXTENSIONS

Sequence extended by Paul Zimmermann, Mar 15 1996

Maple program updated and sequence extended by Robert Israel, Jun 16 2011

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified October 18 10:28 EDT 2017. Contains 293507 sequences.