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
References
- 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).
Links
- 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
Crossrefs
Programs
-
Maple
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);
-
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 *) -
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
Formula
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
Extensions
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
Comments