A003763 -id:A003763 - cp's OEIS frontend

A238115 Number of states arising in matrix method for enumerating Hamiltonian cycles on a 2n X 2n grid.

1, 6, 32, 182, 1117, 7280, 49625, 349998, 2535077, 18758264, 141254654, 1079364104, 8350678169, 65298467486, 515349097712, 4100346740510, 32858696386765, 265001681344568, 2149447880547398, 17524254766905368, 143540915998174577, 1180736721910617182

Offset: 1

N. J. A. Sloane, Mar 05 2014

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..500
Ed Wynn, Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs, arXiv preprint arXiv:1402.0545 [math.CO], 2014.

Cf. A000108, A003763, A086618, A143246, A209077, A222065, A238116, A238117, A238118.

a := n -> hypergeom([1/2, -n, -n], [1, 2], 4) - 1:
seq(simplify(a(n)), n = 1..22);  # Peter Luschny, Dec 13 2024

a(n)=sum(k=1,n,binomial(n,k)^2*binomial(2*k,k)/(k+1)) \\ Andrew Howroyd, Dec 13 2024

From Andrew Howroyd, Dec 13 2024: (Start)
a(n) = Sum_{k=1..n} binomial(n,k)^2 * A000108(k).
a(n) = A086618(n) - 1. (End)

A268894 Number of Hamiltonian paths in C_n X P_n.

Original entry on oeis.org

1, 4, 144, 4016, 152230, 14557092, 1966154260, 761411682704, 411068703517542, 684434716944151900, 1572754514153890134760, 11579615738168536799184984, 117186519917858266359631481672, 3877921919790491112398750141807648, 176258463464553583688099296874564393850, 26493868301658838913487471166447301509560736

Offset: 1

Andrew Howroyd, Feb 15 2016

nonn

This is the number of undirected paths.

Artem M. Karavaev, Hamilton Paths
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Stacked Prism Graph

Cf. A003763, A222197, A120443, A268838.

Cf. A003752, A003732.

A222200 Number of Hamiltonian cycles on n X n+1 square grid of points.

Original entry on oeis.org

1, 2, 14, 154, 5320, 301384, 49483138, 13916993782, 10754797724124, 14746957510647992, 53540340738182687296, 354282765498796010420944, 6040964455632840415885507728, 191678405883294971709423926242394, 15351055042300622367048024911122943712

Offset: 2

N. J. A. Sloane, Feb 14 2013

nonn

Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles [Broken link?]
Peter Tittman, Illustration of a(4) = 14 [Taken from preceding link]
Peter Tittmann, Enumeration in graphs: counting Hamiltonian cycles [Backup copy of top page only, on the Internet Archive]
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A321172.

a(n) = A321172(n,n+1) = A321172(n+1,n). - Robert FERREOL, Apr 01 2019

a(16) from Huaide Cheng, Jul 02 2025

A227301 Number of Hamiltonian circuits in a 2n node X 2n node square lattice, reduced for symmetry, where the orbits under the symmetry group of the square, D4, have 8 elements.

Original entry on oeis.org

0, 0, 121, 578937, 58407351059, 134528360800075421, 7015812452559988037073365, 8235314565328229497795808499821534, 216740797236120772990968348272561831275923059, 127557553423846099192878370706037904215158660401579043097

Offset: 1

Christopher Hunt Gribble, Jul 05 2013

			When n = 3 there are 121 Hamiltonian circuits in a 6 X 6  square lattice where the orbits under the symmetry group of the square have 8 elements.  One of these circuits is shown below with its 8 distinct transformations under rotation and reflection:
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  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__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  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  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__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    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  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  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__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__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  o
|              |    |  |  |  |  |  |
o__o__o__o__o__o    o__o  o__o  o__o

Giovanni Resta, Simple C program for computing a(1)-a(4)
Ed Wynn, Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs, arXiv:1402.0545 [math.CO], 2014.

Cf. A003763, A209077, A063524, A227005, A227257.

A063524 + A227005 + A227257 + A227301 = A209077.

1*A063524 + 2*A227005 + 4*A227257 + 8*A227301 = A003763.

a(4) from Giovanni Resta, Jul 11 2013

a(5)-a(10) from Ed Wynn, Feb 05 2014

A269561 Number of (undirected) Hamiltonian cycles in the n X n rook graph K_n X K_n.

Original entry on oeis.org

1, 48, 284112, 335750676480, 112249362914249932800, 14994936423694913432308324761600

Offset: 2

Andrew Howroyd, Feb 29 2016

Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Rook Graph

Cf. A269562, A096970, A003763, A222199.

Name adjusted by Eric W. Weisstein, May 06 2019

A333651 Triangle T(n,k), n >= 2, 0 <= k <= floor(n^2/2)-2, read by rows, where T(n,k) is the number of 2*(k+2)-cycles in the n X n grid graph which pass through NW corner (0,0).

Original entry on oeis.org

1, 1, 2, 4, 1, 2, 6, 18, 40, 24, 6, 1, 2, 6, 20, 72, 248, 698, 1100, 1096, 662, 206, 1, 2, 6, 20, 74, 298, 1228, 4762, 15984, 40026, 75524, 109150, 121130, 99032, 51964, 11996, 1072, 1, 2, 6, 20, 74, 300, 1300, 5844, 26148, 110942, 427388, 1393796, 3790524, 8648638, 16727776, 27529284, 38120312, 43012614, 37385280, 23166526, 9496426, 2286972, 242764

Offset: 2

Seiichi Manyama, Apr 01 2020

			T(3,0) = 1;
   +--*
   |  |
   *--*
T(3,1) = 2;
   +--*--*   +--*
   |     |   |  |
   *--*--*   *  *
             |  |
             *--*
T(3,2) = 4;
   +--*--*   +--*--*   +--*--*   +--*
   |     |   |     |   |     |   |  |
   *     *   *  *--*   *--*  *   *  *--*
   |     |   |  |         |  |   |     |
   *--*--*   *--*         *--*   *--*--*
Triangle starts:
===================================================
n\k| 0  1  2   3   4    5     6 ...     10 ...  16
---|-----------------------------------------------
2  | 1;
3  | 1, 2, 4;
4  | 1, 2, 6, 18, 40,  24,    6;
5  | 1, 2, 6, 20, 72, 248,  698, ... , 206;
6  | 1, 2, 6, 20, 74, 298, 1228, .......... , 1072;
7  | 1, 2, 6, 20, 74, 300, 1300, ...
8  | 1, 2, 6, 20, 74, 300, 1302, ...
9  | 1, 2, 6, 20, 74, 300, 1302, ...

Seiichi Manyama, Rows n = 2..9, flattened

Row sums give A333246.

Cf. A003763, A034010, A302337, A333652, A333667, A333668.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333651(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles().including(1)
    return [cycles.len(2 * k).len() for k in range(2, n * n // 2 + 1)]
print([i for n in range(2, 8) for i in A333651(n)])

T(n,k) = A034010(k+2) for k <= n-2.

A333652 Triangle T(n,k), n >= 2, 0 <= k <= floor(n^2/2)-n, read by rows, where T(n,k) is the number of 2*(k+n)-cycles in the n X n grid graph which pass through NW and SW corners.

Original entry on oeis.org

1, 1, 3, 1, 6, 17, 17, 6, 1, 10, 45, 167, 404, 570, 460, 186, 1, 15, 100, 506, 2164, 7726, 20483, 39401, 56015, 57632, 37450, 10340, 1072, 1, 21, 196, 1316, 7066, 33983, 147377, 546400, 1656592, 4099732, 8394433, 14227675, 19443270, 20239262, 14767415, 7007270, 1926990, 230440

Offset: 2

Seiichi Manyama, Apr 01 2020

			T(3,0) = 1;
   +--*
   |  |
   *  *
   |  |
   +--*
T(3,1) = 3;
   +--*--*   +--*--*   +--*
   |     |   |     |   |  |
   *     *   *  *--*   *  *--*
   |     |   |  |      |     |
   +--*--*   +--*      +--*--*
Triangle starts:
====================================================================
n\k| 0   1    2     3      4 ...      7 ...  12 ...    17 ...    24
---|----------------------------------------------------------------
2  | 1;
3  | 1,  3;
4  | 1,  6,  17,   17,     6;
5  | 1, 10,  45,  167,   404, ... , 186;
6  | 1, 15, 100,  506,  2164, .......... , 1072;
7  | 1, 21, 196, 1316,  7066, .................. , 230440;
8  | 1, 28, 350, 3038, 20317, ............................ , 4638576;

Seiichi Manyama, Rows n = 2..9, flattened

Row sums give A333247.

Cf. A000217, A003763, A302337, A333651, A333667, A333668.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333652(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles().including(1).including(n)
    return [cycles.len(2 * k).len() for k in range(n, n * n // 2 + 1)]
print([i for n in range(2, 8) for i in A333652(n)])

T(n,0) = 1.

T(n,1) = A000217(n-1) for n > 2.

A333667 Triangle T(n,k), n >= 2, 0 <= k <= floor(n^2/2)-2n+2, read by rows, where T(n,k) is the number of 2(k+2*n-2)-cycles in the n X n grid graph which pass through NW and SE corners ((0,0),(n-1,n-1)).

Original entry on oeis.org

1, 3, 20, 16, 6, 175, 420, 562, 456, 186, 1764, 8064, 21224, 39500, 55376, 57248, 37586, 10260, 1072, 19404, 138600, 569768, 1717152, 4151965, 8371428, 14126846, 19364732, 20241450, 14759356, 6998166, 1927724, 230440

Offset: 2

Seiichi Manyama, Apr 01 2020

			T(3,0) = 3;
   +--*--*   +--*--*   +--*
   |     |   |     |   |  |
   *--*  *   *     *   *  *--*
      |  |   |     |   |     |
      *--+   *--*--+   *--*--+
Triangle starts:
=======================================================================
n\k|      0        1         2 ...      4 ...   8 ...    12 ...     18
---|-------------------------------------------------------------------
2  |      1;
3  |      3;
4  |     20,      16,        6;
5  |    175,     420,      562, ... , 186;
6  |   1764,    8064,    21224, .......... , 1072;
7  |  19404,  138600,   569768, .................. , 230440;
8  | 226512, 2265120, 12922446, ............................ , 4638576;

Seiichi Manyama, Rows n = 2..9, flattened

Row sums give A333323.

Cf. A003763, A302337, A333651, A333652, A333668.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333667(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles().including(1).including(n * n)
    return [cycles.len(2 * k).len() for k in range(2 * n - 2, n * n // 2 + 1)]
print([i for n in range(2, 8) for i in A333667(n)])

T(n,0) = A000891(n-2).

A333668 Triangle T(n,k), n >= 2, 0 <= k <= floor(n^2/2)-2n+2, read by rows, where T(n,k) is the number of 2(k+2*n-2)-cycles in the n X n grid graph which pass through four corners ((0,0), (0,n-1), (n-1,n-1), (n-1,0)).

Original entry on oeis.org

1, 1, 1, 4, 6, 1, 12, 58, 156, 146, 1, 24, 244, 1416, 5435, 12976, 16654, 7108, 1072, 1, 40, 696, 7076, 47965, 236628, 873610, 2348664, 4335724, 4958224, 3407276, 1298704, 205792

Offset: 2

Seiichi Manyama, Apr 01 2020

			T(4,1) = 4;
   +--*--*--+   +--*--*--+   +--*--*--+   +--*  *--+
   |        |   |        |   |        |   |  |  |  |
   *--*     *   *     *--*   *        *   *  *--*  *
      |     |   |     |      |        |   |        |
   *--*     *   *     *--*   *  *--*  *   *        *
   |        |   |        |   |  |  |  |   |        |
   +--*--*--+   +--*--*--+   +--*  *--+   +--*--*--+
Triangle starts:
=================================================================
n\k| 0   1     2      3       4 ...       8 ...    12 ...     18
---|-------------------------------------------------------------
2  | 1;
3  | 1;
4  | 1,  4,    6;
5  | 1, 12,   58,   156,    146;
6  | 1, 24,  244,  1416,   5435, ... , 1072;
7  | 1, 40,  696,  7076,  47965, ........... , 205792;
8  | 1, 60, 1590, 24960, 263770, ..................... , 4638576;

Seiichi Manyama, Rows n = 2..9, flattened

Row sums give A333466.

Cf. A003763, A046092, A302337, A333651, A333652, A333667.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333668(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    for i in [1, n, n * (n - 1) + 1, n * n]:
        cycles = cycles.including(i)
    return [cycles.len(2 * k).len() for k in range(2 * n - 2, n * n // 2 + 1)]
print([i for n in range(2, 8) for i in A333668(n)])

T(n,0) = 1.

T(n,1) = A046092(n-3).

A238116 Number of continuations arising in matrix method for enumerating Hamiltonian cycles on 2n X 2n grid.

Original entry on oeis.org

1, 14, 162, 1966, 25567, 351880, 5056350, 75100735, 1144833705, 17821104101

Offset: 1

N. J. A. Sloane, Mar 05 2014

Ed Wynn, Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs, arXiv preprint arXiv:1402.0545 [math.CO], 2014.

Cf. A003763, A143246, A209077, A222065, A238115, A238117, A238118.

cp's OEIS Frontend

A238115 Number of states arising in matrix method for enumerating Hamiltonian cycles on a 2n X 2n grid.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A268894 Number of Hamiltonian paths in C_n X P_n.

Views

Author

Keywords

Comments

Links

Crossrefs

A222200 Number of Hamiltonian cycles on n X n+1 square grid of points.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A227301 Number of Hamiltonian circuits in a 2n node X 2n node square lattice, reduced for symmetry, where the orbits under the symmetry group of the square, D4, have 8 elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A269561 Number of (undirected) Hamiltonian cycles in the n X n rook graph K_n X K_n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A333651 Triangle T(n,k), n >= 2, 0 <= k <= floor(n^2/2)-2, read by rows, where T(n,k) is the number of 2*(k+2)-cycles in the n X n grid graph which pass through NW corner (0,0).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A333652 Triangle T(n,k), n >= 2, 0 <= k <= floor(n^2/2)-n, read by rows, where T(n,k) is the number of 2*(k+n)-cycles in the n X n grid graph which pass through NW and SW corners.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A333667 Triangle T(n,k), n >= 2, 0 <= k <= floor(n^2/2)-2*n+2, read by rows, where T(n,k) is the number of 2*(k+2*n-2)-cycles in the n X n grid graph which pass through NW and SE corners ((0,0),(n-1,n-1)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A333668 Triangle T(n,k), n >= 2, 0 <= k <= floor(n^2/2)-2*n+2, read by rows, where T(n,k) is the number of 2*(k+2*n-2)-cycles in the n X n grid graph which pass through four corners ((0,0), (0,n-1), (n-1,n-1), (n-1,0)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

A333667 Triangle T(n,k), n >= 2, 0 <= k <= floor(n^2/2)-2n+2, read by rows, where T(n,k) is the number of 2(k+2*n-2)-cycles in the n X n grid graph which pass through NW and SE corners ((0,0),(n-1,n-1)).

A333668 Triangle T(n,k), n >= 2, 0 <= k <= floor(n^2/2)-2n+2, read by rows, where T(n,k) is the number of 2(k+2*n-2)-cycles in the n X n grid graph which pass through four corners ((0,0), (0,n-1), (n-1,n-1), (n-1,0)).