A027683 -id:A027683 - cp's OEIS frontend

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

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

A286513 Array read by antidiagonals: T(m,n) is the number of independent sets in the stacked prism graph C_m X P_n.

Original entry on oeis.org

1, 1, 3, 1, 7, 4, 1, 17, 13, 7, 1, 41, 43, 35, 11, 1, 99, 142, 181, 81, 18, 1, 239, 469, 933, 621, 199, 29, 1, 577, 1549, 4811, 4741, 2309, 477, 47, 1, 1393, 5116, 24807, 36211, 26660, 8303, 1155, 76, 1, 3363, 16897, 127913, 276561, 307983, 143697, 30277, 2785, 123

Offset: 1

Andrew Howroyd, May 10 2017

Equivalently, the number of vertex covers in the stacked prism graph C_m X P_n.

			Table starts:
=============================================================
m\n|   1    2     3      4        5         6           7
---|---------------------------------------------------------
1  |   1    1     1      1        1         1           1 ...
2  |   3    7    17     41       99       239         577 ...
3  |   4   13    43    142      469      1549        5116 ...
4  |   7   35   181    933     4811     24807      127913 ...
5  |  11   81   621   4741    36211    276561     2112241 ...
6  |  18  199  2309  26660   307983   3557711    41097664 ...
7  |  29  477  8303 143697  2488431  43089985   746156517 ...
8  |  47 1155 30277 788453 20546803 535404487 13951571713 ...
...

Liang Kai, Table of n, a(n) for n = 1..704 (terms up to a(435) from Andrew Howroyd)
Kai Liang, Independent Set Enumeration and Estimation of Related Constants of Grid Graphs, arXiv:2507.04007 [math.CO], 2025. See p. 13.
Eric Weisstein's World of Mathematics, Independent Vertex Set.
Eric Weisstein's World of Mathematics, Stacked Prism Graph.
Wikipedia, Independent set.

Rows 3..8 are A003688(n+1), A051926, A181989, A181961, A182014, A182019.
Columns 1..4 are A000032, A051927, A050400, A050401.
Main diagonal is A212270.
Cf. A089934 (P_m X P_n), A027683, A286514.

A067959 Number of binary arrangements without adjacent 1's on n X n torus connected ne-sw n-s nw-se.

Original entry on oeis.org

1, 7, 22, 547, 9021, 812830, 70046159, 24082448515, 10363980496342, 14228018243052057, 29400555005986658803, 166705587265151114516638, 1606507128309318588452521527, 38505096862341023166325442747581, 1696028983502674228038462924646464012

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
./|\/|\/|\/|\

Sean A. Irvine, Table of n, a(n) for n = 1..17
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 73.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, n-s nw-se A067964, 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, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

a(13) from Vaclav Kotesovec, Aug 22 2016
a(14) from Vaclav Kotesovec, May 24 2021
a(15) from Sean A. Irvine, Jan 14 2024

A066865 Number of binary arrangements without adjacent 1's on n X n staggered hexagonal torus bent for odd n.

Original entry on oeis.org

1, 5, 22, 217, 4726, 164258, 14840533, 1834600977, 669877863205, 296979228487760, 434542100979981567, 692625866382651263578, 4053364289624915167879497, 23237986479606982160703729647, 543749373021017146939376423644362, 11213018647250714014261414954480048385

Offset: 1

R. H. Hardin, Jan 25 2002

nonn

			Neighbors for n=4:
\|/ | \|/ |
-o--o--o--o-
 | /|\ | /|\
\|/ | \|/ |
-o--o--o--o-
 | /|\ | /|\
\|/ | \|/ |
-o--o--o--o-
 | /|\ | /|\
\|/ | \|/ |
-o--o--o--o-
 | /|\ | /|\
Neighbors for n=5:
\|/ | \|/ | \|/
 o--o--o--o--o
/| /|\ | /|\ |\
\|/ | \|/ | \|/
 o--o--o--o--o
/| /|\ | /|\ |\
\|/ | \|/ | \|/
 o--o--o--o--o
/| /|\ | /|\ |\
\|/ | \|/ | \|/
 o--o--o--o--o
/| /|\ | /|\ |\
\|/ | \|/ | \|/
 o--o--o--o--o
/| /|\ | /|\ |\

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 342-349.
J. Katzenelson and R. P. Kurshan, S/R: A Language for Specifying Protocols and Other Coordinating Processes, pp. 286-292 in Proc. IEEE Conf. Comput. Comm., 1986.

Steven R. Finch, Hard Square Entropy Constant [Broken link]
Steven R. Finch, Hard Square Entropy Constant [From the Wayback machine]

Cf. A006506, A027683, A066863, A066864, A066866, A067967 (shifted instead of bent).

Row sums of A067015.

More terms from Sean A. Irvine, Nov 18 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.

A066863 Number of binary arrangements without adjacent 1's on n X n staggered hexagonal grid.

Original entry on oeis.org

2, 6, 43, 557, 14432, 719469, 70372090, 13351521479, 4941545691252, 3559349503024593, 4993739972681894885, 13642580224488264353504, 72582736229683196932680697, 751993955499337790653321567382, 15172223086707160824288341875907978

Offset: 1

R. H. Hardin, Jan 25 2002

nonn

			Neighbors for n=4:
o--o--o--o
| /|\ | /|
|/ | \|/ |
o--o--o--o
| /|\ | /|
|/ | \|/ |
o--o--o--o
| /|\ | /|
|/ | \|/ |
o--o--o--o

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 342-349.
J. Katzenelson and R. P. Kurshan, S/R: A Language for Specifying Protocols and Other Coordinating Processes, pp. 286-292 in Proc. IEEE Conf. Comput. Comm., 1986.

Steven R. Finch, Hard Square Entropy Constant [Broken link]
Steven R. Finch, Hard Square Entropy Constant [From the Wayback machine]
Sean A. Irvine, Java program (github)
Eric Weisstein's World of Mathematics, Hard Hexagon Entropy Constant

Cf. A006506, A027683, A066864, A066865, A066866.

More terms from Sean A. Irvine, Nov 15 2023

A182408 Number of ways to place k non-attacking knights on an n x n toroidal chessboard, summed over all k >= 0.

Original entry on oeis.org

2, 7, 34, 743, 1546, 598078, 6027057, 10163241031, 242407820869

Offset: 1

Vaclav Kotesovec, May 09 2012

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

Cf. A141243, A182407, A067958, A027683, A067960.

A270247 Number of matchings in the n X n torus grid graph C_n X C_n.

Original entry on oeis.org

1, 7, 370, 41025, 15637256, 23079663560, 127193770624285, 2645142169931308801, 206932904585998805434690, 60953421285412135689567940992, 67583556205239600880061198746186383, 282092296203355454009618109524478429807744

Offset: 1

Andrew Howroyd, Mar 13 2016

nonn

C_{n} X C_{n} is also known as the (n,n)-torus grid graph.

Eric Weisstein's World of Mathematics, Matching.
Eric Weisstein's World of Mathematics, Torus Grid Graph.

Cf. A270246, A102080, A028420, A270228, A027683, A228316, A222199.

A201626 Number of ways to place n nonattacking wazirs on an n X n toroidal board.

Original entry on oeis.org

1, 2, 6, 228, 6745, 252792, 11281312, 585632520, 34690541994, 2309813476870, 170797663069044, 13888215374348892, 1231730727253607451, 118329596584708240732, 12241103359460777972760, 1356712722052907806912016

Offset: 1

Vaclav Kotesovec, Dec 03 2011

Wazir is a leaper [0,1].

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

Cf. A027683, A201511.

Asymptotics: a(n) ~ n^(2n)/n!*exp(-5/2).

A321250 Number of maximal independent vertex sets in the n X n torus grid graph.

Original entry on oeis.org

1, 2, 6, 42, 220, 3644, 62272, 1794762, 83280570, 6210321492

Offset: 1

Eric W. Weisstein, Nov 01 2018

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set.
Eric Weisstein's World of Mathematics, Torus Grid Graph.

Cf. A027683.

Table[Length@FindIndependentVertexSet[GraphProduct[CycleGraph[n], CycleGraph[n], "Cartesian"], Infinity, All], {n, 3, 8}] (* Eric W. Weisstein, Jan 26 2024 *)

from networkx import find_cliques, complement, cartesian_product, cycle_graph
def A321250(n): return sum(1 for c in find_cliques(complement(cartesian_product(cycle_graph(n),cycle_graph(n))))) # Chai Wah Wu, Jan 11 2024

a(1), a(2), and a(10) from Andrew Howroyd, Nov 01 2018

cp's OEIS Frontend

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

A286513 Array read by antidiagonals: T(m,n) is the number of independent sets in the stacked prism graph C_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A067959 Number of binary arrangements without adjacent 1's on n X n torus connected ne-sw n-s nw-se.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A066865 Number of binary arrangements without adjacent 1's on n X n staggered hexagonal torus bent for odd n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

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

A066863 Number of binary arrangements without adjacent 1's on n X n staggered hexagonal grid.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A182408 Number of ways to place k non-attacking knights on an n x n toroidal chessboard, summed over all k >= 0.

Views

Author

Keywords

Links

Crossrefs

A270247 Number of matchings in the n X n torus grid graph C_n X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

A201626 Number of ways to place n nonattacking wazirs on an n X n toroidal board.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A321250 Number of maximal independent vertex sets in the n X n torus grid graph.

Views

Author

Keywords

Links

Crossrefs

Programs