|
%I M1816 #157 Apr 11 2024 11:25:59
%S 1,2,7,63,1234,55447,5598861,1280128950,660647962955,770548397261707,
%T 2030049051145980050,12083401651433651945979,
%U 162481813349792588536582997,4935961285224791538367780371090,338752110195939290445247645371206783,52521741712869136440040654451875316861275
%N 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.
%C A two-dimensional generalization of the Fibonacci numbers.
%C Also the number of vertex covers in the n X n grid graph P_n X P_n.
%C 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.
%C 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
%D Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 342-349.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Jin-Guo Liu, <a href="/A006506/b006506.txt">Table of n, a(n) for n = 0..39</a> (terms 1..33 from Robert Gerbicz, 34..35 from P. Butera and M. Pernici, 37..38 from Casey Mills Davis)
%H P. Butera and M. Pernici, <a href="http://arxiv.org/abs/1406.5337">Sums of permanental minors using Grassmann algebra</a>, arXiv preprint arXiv:1406.5337 [hep-lat], 2014.
%H Casey Mills Davis, <a href="/A006506/a006506.txt">C++ program used to generate a(n) for n = 36..37</a>
%H Steven R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/square/square.html">Hard Square Entropy Constant</a> [Broken link]
%H Steven R. Finch, <a href="http://web.archive.org/web/20010605012506/http://www.mathsoft.com/asolve/constant/square/square.html">Hard Square Entropy Constant</a> [From the Wayback machine]
%H Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p.372.
%H Jin-Guo Liu, Xun Gao, Madelyn Cain, Mikhail D. Lukin and Sheng-Tao Wang, <a href="https://arxiv.org/abs/2205.03718">Computing solution space properties of combinatorial optimization problems via generic tensor networks</a>, arXiv:2205.03718 [cond-mat.stat-mech], 2022. Terms 38..39.
%H I. Mezo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Mezo/mezo19.html">Periodicity of the Last Digits of Some Combinatorial Sequences</a>, J. Int. Seq. 17 (2014) #14.1.1.
%H B. D. Stosic, T. Stosic, I. P. Fittipaldi and J. J. P. Veerman, <a href="http://dx.doi.org/10.1088/0305-4470/30/10/006">Residual entropy of the square Ising antiferromagnet in the maximum critical field: the Fibonacci matrix</a>, Journal of Physics A: Mathematical and General, Volume 30, Number 10, 1997, pp. L331-L337.
%H Peter Tittmann, <a href="https://web.archive.org/web/20050318211110/http://www.htwm.de/peter/research/enumeration.html">Enumeration in Graphs</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/01-Matrix.html">(0,1)-Matrix</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HardSquareEntropyConstant.html">Hard Square Entropy Constant</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>
%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>
%F Limit_{n->oo} a(n)^(1/n^2) = c1 = 1.50304... is the hard square entropy constant A085850. - _Benoit Cloitre_, Nov 16 2003
%F 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
%F From n up to 39 we have A = 1.06608266035... - _Vaclav Kotesovec_, Jan 29 2024
%p A006506 := proc(N) local i,j,p,q; p := 1+x11;
%p if n=0 then return 1 fi;
%p for i from 2 to N do
%p q := p-select(has,p,x||(i-1)||1);
%p p := p+expand(q*x||i||1)
%p od;
%p for j from 2 to N do
%p q := p-select(has,p,x1||(j-1));
%p p := subs(x1||(j-1)=1,p)+expand(q*x1||j);
%p for i from 2 to N do
%p q := p-select(has,p,{x||(i-1)||j,x||i||(j-1)});
%p p := subs(x||i||(j-1)=1,p)+expand(q*x||i||j);
%p od
%p od;
%p map(icontent,p)
%p end:
%p seq(A006506(n), n=0..15);
%t 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. *)
%t 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 *)
%o (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
%Y Cf. A027683 for toroidal version.
%Y Table of values for n x m matrices: A089934.
%Y Cf. A232833 for refinement by number of 1's.
%Y Cf. also A191779.
%Y Cf. A201511, A212270.
%K nonn,nice,hard,changed
%O 0,2
%A _N. J. A. Sloane_, _R. H. Hardin_, _Paul Zimmermann_
%E Sequence extended by _Paul Zimmermann_, Mar 15 1996
%E Maple program updated and sequence extended by _Robert Israel_, Jun 16 2011
%E a(0)=1 prepended by _Alois P. Heinz_, Jan 29 2024
| 