A085850 -id:A085850 - 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

A067964 Number of binary arrangements without adjacent 1's on n X n array connected n-s nw-se.

Original entry on oeis.org

2, 8, 90, 1876, 103484, 11462588, 3118943536, 1808994829500, 2465526600093372, 7394315828592829424, 50975951518289853305508, 784977037926751747674903856, 27509351187362150581313065415008, 2167705218542258344490649896364635660, 387057670485382113845659790427906287869964

Offset: 1

R. H. Hardin, Feb 02 2002

			Neighbors for n=4 (dots represent spaces):
. o..o..o..o
. |\ |\ |\ |
. | \| \| \|
. o..o..o..o
. |\ |\ |\ |
. | \| \| \|
. o..o..o..o
. |\ |\ |\ |
. | \| \| \|
. o..o..o..o

Vaclav Kotesovec, Table of n, a(n) for n = 1..21
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69-71.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, ne-sw n-s nw-se A067959, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

Limit n->infinity (a(n))^(1/n^2) = 1.503048082... (see A085850)

Terms a(14)-a(18) from Vaclav Kotesovec, May 01 2012

A244593 Decimal expansion of z_c = phi^5 (where phi is the golden ratio), a lattice statistics constant which is the exact value of the critical activity of the hard hexagon model.

Original entry on oeis.org

1, 1, 0, 9, 0, 1, 6, 9, 9, 4, 3, 7, 4, 9, 4, 7, 4, 2, 4, 1, 0, 2, 2, 9, 3, 4, 1, 7, 1, 8, 2, 8, 1, 9, 0, 5, 8, 8, 6, 0, 1, 5, 4, 5, 8, 9, 9, 0, 2, 8, 8, 1, 4, 3, 1, 0, 6, 7, 7, 2, 4, 3, 1, 1, 3, 5, 2, 6, 3, 0, 2, 3, 1, 4, 0, 9, 4, 5, 1, 2, 2, 4, 8, 5, 3, 6, 0, 3, 6, 0, 2, 0, 9, 4, 6, 9, 5, 5, 6, 8, 7, 4, 2

Offset: 2

Jean-François Alcover, Jul 01 2014

Essentially the same digit sequence as A239798, A019863 and A019827. - R. J. Mathar, Jul 03 2014

The minimal polynomial of this constant is x^2 - 11*x - 1. - Joerg Arndt, Jan 01 2017

			11.09016994374947424102293417182819058860154589902881431067724311352630...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.12.1 Phase transitions in Lattice Gas Models, p. 347.
Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, pages 138-139.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 83.

Eric Weisstein's MathWorld, Hard Hexagon Entropy Constant.
Wikipedia, Hard Hexagon Model.
D. W. Wood and R. W. Turnbull, z^2-11z-1 as an algebraic invariant for the hard-hexagon model, 1988 J. Phys. A: Math. Gen. 21 L989.

Cf. A019863, A019827, A085850, A239798.

Cf. A001622, A014176, A098316, A098317, A098318, A176398, A176439, A176458 A176522, A176537 (metallic means).

RealDigits[GoldenRatio^5, 10, 103] // First

(5*sqrt(5)+11)/2 \\ Charles R Greathouse IV, Aug 10 2016

Equals ((1 + sqrt(5))/2)^5 = (11 + 5*sqrt(5))/2.
Equals phi^5 = 11 + 1/phi^5 = 3 + 5*phi, an integer in the quadratic number field Q(sqrt(5)). - Wolfdieter Lang, Nov 11 2023
Equals lim_{n->infinity} S(n, 5*(-1 + 2*phi))/ S(n-1, 5*(-1 + 2*phi)), with the S-Chebyshev polynomials (see A049310). - Wolfdieter Lang, Nov 15 2023

A212270 Number of ways to place k non-attacking wazirs on an n x n cylindrical chessboard, summed over all k >= 0.

Original entry on oeis.org

2, 7, 43, 933, 36211, 3557711, 746156517, 363549830913, 394677987525997, 974602314570939359, 5418730454986467701985, 68176187476467835406646029, 1936241516342334422813929891295, 124281423643836238320564876791634465, 18018270577720149773239661332878801006033

Offset: 1

Vaclav Kotesovec, May 12 2012

Wazir is a leaper [0,1].

Vaclav Kotesovec, Table of n, a(n) for n = 1..32
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.414

Main diagonal of A286513.

Cf. A006506, A027683, A182407, A212269, A212271.

Limit n ->infinity (a(n))^(1/n^2) is the hard square entropy constant A085850.

A085851 Decimal expansion of hard hexagon entropy constant.

Original entry on oeis.org

1, 3, 9, 5, 4, 8, 5, 9, 7, 2, 4, 7, 9, 3, 0, 2, 7, 3, 5, 2, 2, 9, 5, 0, 0, 6, 6, 3, 5, 6, 6, 8, 8, 8, 0, 6, 8, 9, 5, 4, 1, 0, 3, 7, 2, 8, 1, 4, 4, 6, 6, 1, 1, 9, 0, 8, 1, 7, 4, 7, 2, 1, 5, 6, 1, 3, 5, 7, 6, 0, 8, 8, 0, 3, 5, 8, 6, 9, 7, 7, 7, 4, 6, 8, 9, 8, 3, 7, 8, 7, 3, 0, 8, 5, 2, 7, 5, 4, 2, 7, 9, 0

Offset: 1

Eric W. Weisstein, Jul 05 2003

			1.395485972...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 5.12, p. 343.

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69.
Eric Weisstein's World of Mathematics, Hard Hexagon Entropy Constant.

Cf. A085850, A247413, A066864.

RealDigits[N[Root[-32751691810479015985152 + 97143135277377575190528*#1^4 - 73347491183630103871488*#1^6 - 71220809441400405884928*#1^8 + 107155448150443388043264*#1^10 - 72405670285649161617408*#1^12 + 2958015038376958230528*#1^14 + 7449488310131083100160*#1^16 + 797726698866658379776*#1^18 + 2505062311720673792* #1^20 + 2013290651222784*#1^22 + 25937424601*#1^24 & , 2], 200]][[1]] (* Vaclav Kotesovec, Apr 03 2014 *)

A212271 Number of ways to place k non-attacking ferses on an n x n cylindrical chessboard, summed over all k >= 0.

Original entry on oeis.org

2, 9, 80, 1600, 79033, 8156736, 2055960192, 1108756350625, 1411080429618656, 3943472747846953216, 25425527581172360096017, 365481944233773616212640000, 11980566143208960475692367828480, 882106482533191605447029340350009049, 147314997388032765439791110273770608260928

Offset: 1

Vaclav Kotesovec, May 12 2012

Fers is a leaper [1,1].

Vaclav Kotesovec, Table of n, a(n) for n = 1..18
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.443

Cf. A067965, A067960, A182407, A212269, A212270.

Limit n ->infinity (a(n))^(1/n^2) is the hard square entropy constant A085850.

A247413 Decimal expansion of the entropy constant related to A063443.

Original entry on oeis.org

1, 3, 4, 2, 6, 4, 3, 9, 5, 1, 1, 2, 4

Offset: 1

Vaclav Kotesovec, Sep 16 2014

			1.342643951124...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 343.
B. D. McKay, On Calkin and Wilf's limit theorem for grid graphs, unpublished note, 1996.

N. J. Calkin, K. James, and S. Purvis, Counting Kings, 2006, p.9.
N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, preprint, 1995.
N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math, 11 (1998) 54-60.
Steven R. Finch, Several Constants Arising in Statistical Mechanics, arXiv:math/9810155 [math.CO], 1999, p.8.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p.68-69.
D. E. Knuth, Nonattacking kings on a chessboard, 1994.
M. Larsen, The Problem of Kings, The Electronic Journal of Combinatorics 2, 1995.
Kai Liang, Independent Set Enumeration in King Graphs by Tensor Network Contractions, arXiv:2505.12776 [math.CO], 2025. See p. 6.
Eric Weisstein's World of Mathematics, Hard Hexagon Entropy Constant
Eric Weisstein's World of Mathematics, Hard Square Entropy Constant
H. S. Wilf, The problem of the kings, Elec. J. Combin. 2, 1995.

Cf. A063443, A212269.

Cf. A085850, A085851.

Equals limit n->infinity (A063443(n))^(1/n^2).

Equals limit n->infinity (A212269(n))^(1/n^2).

cp's OEIS Frontend

A379041 Decimal expansion of log(A085850).

Views

Author

Keywords

Examples

References

Crossrefs

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

A067964 Number of binary arrangements without adjacent 1's on n X n array connected n-s nw-se.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A244593 Decimal expansion of z_c = phi^5 (where phi is the golden ratio), a lattice statistics constant which is the exact value of the critical activity of the hard hexagon model.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A212270 Number of ways to place k non-attacking wazirs on an n x n cylindrical chessboard, summed over all k >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A085851 Decimal expansion of hard hexagon entropy constant.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

A212271 Number of ways to place k non-attacking ferses on an n x n cylindrical chessboard, summed over all k >= 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A247413 Decimal expansion of the entropy constant related to A063443.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula