A222202 -id:A222202 - cp's OEIS frontend

A231829 Square array read by antidiagonals: T(m,n) = number of ways of creating a closed, simple loop on an m X n rectangular lattice.

1, 3, 3, 6, 13, 6, 10, 40, 40, 10, 15, 108, 213, 108, 15, 21, 275, 1049, 1049, 275, 21, 28, 681, 5034, 9349, 5034, 681, 28, 36, 1664, 23984, 80626, 80626, 23984, 1664, 36, 45, 4040, 114069, 692194, 1222363, 692194, 114069, 4040, 45

Offset: 1

Douglas Boffey, Nov 14 2013

This sequence is read in a table, thus:
    m ->
    1,  3,  6, 10, …
n   3, 13, 40, …
|   6, 40, …
v  10, …
    …
This sequence gives the number of closed, simple loops on a rectangular lattice of dots, where the edges of the loop can be horizontal or vertical.
This is also the number of solutions to an unclued slitherlink puzzle.
Main diagonal is A140517. - Joerg Arndt, Sep 01 2014
Equivalently, the number of cycles in the grid graph P_{m+1} X P_{n+1}. - Andrew Howroyd, Jun 12 2017

			Table starts:
=================================================================
m\n|  1    2      3       4         5           6            7
---|-------------------------------------------------------------
1  |  1    3      6      10        15          21           28...
2  |  3   13     40     108       275         681         1664...
3  |  6   40    213    1049      5034       23984       114069...
4  | 10  108   1049    9349     80626      692194      5948291...
5  | 15  275   5034   80626   1222363    18438929    279285399...
6  | 21  681  23984  692194  18438929   487150371  12947640143...
7  | 28 1664 114069 5948291 279285399 12947640143 603841648931...
... - _Andrew Howroyd_, Jun 12 2017
a(2,2) = 13, thus:
1)        2)        3)        4)        5)
+-+ +     + +-+     + + +     + + +     +-+ +
| |         | |                         | |
+-+ +     + +-+     +-+ +     + +-+     + + +
                    | |         | |     | |
+ + +     + + +     +-+ +     + +-+     +-+ +
6)        7)        8)        9)        10)
+ +-+     +-+-+     + + +     +-+ +     + +-+
  | |     |   |               | |         | |
+ + +     +-+-+     +-+-+     + +-+     +-+ +
  | |               |   |     |   |     |   |
+ +-+     + + +     +-+-+     +-+-+     +-+-+
11)       12)       13)
+-+-+     +-+-+     +-+-+
|   |     |   |     |   |
+-+ +     + +-+     + + +
  | |     | |       |   |
+ +-+     +-+ +     +-+-+

Douglas Boffey and Andrew Howroyd, Table of n, a(n) for n = 1..325 (terms 1..70 from Douglas Boffey)
Wikipedia, Slitherlink

Rows 2..10 are A059020, A288637, A339117, A339118, A339119, A339120, A339121, A358707, A358785.
Main diagonal is A140517.
Cf. A288518, A003763, A222202.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A231829(n, k):
    universe = tl.grid(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A231829(j + 1, i - j + 1) for i in range(9) for j in range(i + 1)])  # Seiichi Manyama, Nov 24 2020

A222203 Number of ways to cover the n X n+1 grid graph by vertex disjoint cycles.

Original entry on oeis.org

1, 3, 54, 1140, 99051, 13049563, 6044482889, 4738211572702, 11986520595161863, 54755153078468134960, 764291947227525464744293, 20119942924108379011391597989, 1558052539448513320447263528275071, 234788223520702255614480389250160811898, 101199388044301804167035198499446336399419451, 86918369741985767628242106496018767545685968221295

Offset: 2

N. J. A. Sloane, Feb 14 2013

nonn

Andrew Howroyd, Table of n, a(n) for n = 2..24
Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles [Archived link]
Robert Israel, The 54 solutions for n=4

Cf. A222202, A222204.

A003693 Number of 2-factors in P_4 X P_n.

Original entry on oeis.org

0, 2, 3, 18, 54, 222, 779, 2953, 10771, 40043, 147462, 545603, 2013994, 7442927, 27490263, 101563680, 375176968, 1386004383, 5120092320, 18914660608, 69873991466, 258127586367, 953569519203, 3522660270539

Offset: 1

Frans J. Faase

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Andrew Howroyd, Table of n, a(n) for n = 1..200
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Index entries for linear recurrences with constant coefficients, signature (2, 7, -2, -3, 1).

Cf. A003776, A145400, A145415, A145417, A222202, A222203.

LinearRecurrence[{2, 7, -2, -3, 1}, {0, 2, 3, 18, 54}, 30] (* Jean-François Alcover, Sep 21 2019 *)

a(n) = 2a(n-1) + 7a(n-2) - 2a(n-3) - 3a(n-4) + a(n-5), n > 5.

G.f.: (-x*(x-1)*(x-2)*(x+1))/(-1 + x^5 - 3*x^4 - 2*x^3 + 7*x^2 + 2*x). - Maksym Voznyy (voznyy(AT)mail.ru), Aug 10 2009

A145400 Number of 2-factors in P_6 X P_n.

Original entry on oeis.org

0, 5, 9, 222, 1140, 13903, 99051, 972080, 7826275, 71053230, 599141127, 5285091303, 45349095730, 395755191515, 3418116104881, 29709767180643, 257232791130155, 2232466696767889, 19346930092499853, 167813061128260612, 1454798219804865516, 12616086588695738786

Offset: 1

N. J. A. Sloane, Feb 03 2009

nonn

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Andrew Howroyd, Table of n, a(n) for n = 1..200
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
F. Faase, Counting Hamiltonian cycles in product graphs.
F. Faase, Results from the counting program

Cf. A003693, A222202.

a(n) = 5*a(n-1) + 49*a(n-2) - 116*a(n-3) - 363*a(n-4) + 627*a(n-5) + 544*a(n-6) - 1061*a(n-7) + 133*a(n-8) + 264*a(n-9) - 47*a(n-10) - 26*a(n-11) + 3*a(n-12) + a(n-13) for n > 13.

G.f.: x^2*(5 - 16*x - 68*x^2 + 169*x^3 + 184*x^4 - 440*x^5 + 41*x^6 + 159*x^7 - 24*x^8 - 21*x^9 + 2*x^10 + x^11)/(1 - 5*x - 49*x^2 + 116*x^3 + 363*x^4 - 627*x^5 - 544*x^6 + 1061*x^7 - 133*x^8 - 264*x^9 + 47*x^10 + 26*x^11 - 3*x^12 - x^13). - Andrew Howroyd, Oct 04 2017

Terms a(14) and beyond from Andrew Howroyd, Oct 04 2017

A145417 Number of 2-factors in P_8 X P_n.

Original entry on oeis.org

0, 13, 27, 2953, 24360, 972080, 13049563, 360783593, 6044482889, 142205412782, 2645920282312, 57787769198498, 1130122135817708, 23838761889677477, 477334902804794530, 9905649696435264827, 200572437515846530901, 4130348948437378850158

Offset: 1

N. J. A. Sloane, Feb 03 2009

nonn

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Andrew Howroyd, Table of n, a(n) for n = 1..200
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
F. Faase, Counting Hamiltonian cycles in product graphs.
F. Faase, Results from the counting program

Cf. A003693, A222202.

Recurrence:
a(1) = 0,
a(2) = 13,
a(3) = 27,
a(4) = 2953,
a(5) = 24360,
a(6) = 972080,
a(7) = 13049563,
a(8) = 360783593,
a(9) = 6044482889,
a(10) = 142205412782,
a(11) = 2645920282312,
a(12) = 57787769198498,
a(13) = 1130122135817708,
a(14) = 23838761889677477,
a(15) = 477334902804794530,
a(16) = 9905649696435264827,
a(17) = 200572437515846530901,
a(18) = 4130348948437378850158,
a(19) = 84074883624291031055071,
a(20) = 1725061733607816846672084,
a(21) = 35201911945083165877105598,
a(22) = 721041937227213471236222936,
a(23) = 14731026760739434523775920272,
a(24) = 301492247130186410656766864436,
a(25) = 6162966556594442193757310209147,
a(26) = 126086101870795129720839096783333,
a(27) = 2578070083185284447937587182277129,
a(28) = 52734387801729163635906223494385644,
a(29) = 1078388240037660942562424414577181926,
a(30) = 22056541466571843558470704997624920958,
a(31) = 451070070689312442562501030339580527821,
a(32) = 9225477593066296020350369342487285559224,
a(33) = 188671988477305551144936342851950180268541,
a(34) = 3858726953408688228729004487413425843715888,
a(35) = 78916582053879579831149431468113368147807393,
a(36) = 1613990623415047770881237325964870382681263773,
a(37) = 33008659899083829723098251801948045543305771504,
a(38) = 675085532254115719882540973806685632932538969963,
a(39) = 13806606434855907791563611600265129790934630275875,
a(40) = 282368982002683765432041412891639191366286828541983,
a(41) = 5774916734695662624117282233886060904936699004411462,
a(42) = 118106924720040350256778966063911938302901243885821967,
a(43) = 2415485198293035324333076932461513145106982243926222725, and
a(n) = 10a(n-1) + 397a(n-2) - 2280a(n-3) - 41718a(n-4) + 171740a(n-5)
+ 1774768a(n-6) - 6621030a(n-7) - 36498440a(n-8) + 142302403a(n-9) + 378226103a(n-10)
- 1722824637a(n-11) - 1841136643a(n-12) + 11820333398a(n-13) + 2592291604a(n-14) - 47333298485a(n-15)
+ 11152811093a(n-16) + 115741226920a(n-17) - 56392421244a(n-18) - 180338596048a(n-19) + 113066783284a(n-20)
+ 185447332605a(n-21) - 129254123956a(n-22) - 129334594126a(n-23) + 92695904156a(n-24) + 62261558431a(n-25)
- 43387609685a(n-26) - 20799137282a(n-27) + 13474013361a(n-28) + 4776521864a(n-29) - 2787760272a(n-30)
- 734922053a(n-31) + 383508601a(n-32) + 72495666a(n-33) - 34918980a(n-34) - 4271202a(n-35)
+ 2078603a(n-36) + 129022a(n-37) - 77626a(n-38) - 773a(n-39) + 1644a(n-40)
- 54a(n-41) - 15a(n-42) + a(n-43).
a(n) = 14*a(n-1) + 331*a(n-2) - 3474*a(n-3) - 24357*a(n-4) + 237534*a(n-5) + 541266*a(n-6) - 6604103*a(n-7) - 1905497*a(n-8) + 85855152*a(n-9) - 60009003*a(n-10) - 545836271*a(n-11) + 672927757*a(n-12) + 1747850343*a(n-13) - 2763674623*a(n-14) - 2917536240*a(n-15) + 5513512152*a(n-16) + 2653029943*a(n-17) - 5852097578*a(n-18) - 1465977019*a(n-19) + 3471750395*a(n-20) + 568784352*a(n-21) - 1167520145*a(n-22) - 154667330*a(n-23) + 221656480*a(n-24) + 23823457*a(n-25) - 24542626*a(n-26) - 1818710*a(n-27) + 1646233*a(n-28) + 57030*a(n-29) - 66339*a(n-30) + 348*a(n-31) + 1479*a(n-32) - 61*a(n-33) - 14*a(n-34) + a(n-35) for n > 35. - Andrew Howroyd, Oct 04 2017

Terms a(17) and beyond from Andrew Howroyd, Oct 04 2017

A222204 Write n=3i+j, 0<=j<3; a(n) = number of ways to cover the r X s grid graph by vertex disjoint cycles, where (r,s) = (2i+2, 2i+2) (if j=0), (2i+2, 2i+3) (if j=1) or (2i+3, 2i+4) (if j=2).

Original entry on oeis.org

1, 1, 3, 18, 54, 1140, 13903, 99051, 13049563, 360783593, 6044482889, 4738211572702, 303872744726644, 11986520595161863, 54755153078468134960, 8217125138015950451626, 764291947227525464744293, 20119942924108379011391597989, 7095967027221343377167292602835, 1558052539448513320447263528275071

Offset: 0

N. J. A. Sloane, Feb 14 2013

nonn

An interleaving of A222202 and A222203.

Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles [Broken link?]
Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles [Backup copy of top page only, on the Internet Archive]

Cf. A222202, A222203.

cp's OEIS Frontend

A231829 Square array read by antidiagonals: T(m,n) = number of ways of creating a closed, simple loop on an m X n rectangular lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A222203 Number of ways to cover the n X n+1 grid graph by vertex disjoint cycles.

Views

Author

Keywords

Links

Crossrefs

A003693 Number of 2-factors in P_4 X P_n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A145400 Number of 2-factors in P_6 X P_n.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A145417 Number of 2-factors in P_8 X P_n.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A222204 Write n=3i+j, 0<=j<3; a(n) = number of ways to cover the r X s grid graph by vertex disjoint cycles, where (r,s) = (2i+2, 2i+2) (if j=0), (2i+2, 2i+3) (if j=1) or (2i+3, 2i+4) (if j=2).

Views

Author

Keywords

Comments

Links

Crossrefs