A003763 -id:A003763 - cp's OEIS frontend

A158651 Number of directed Hamiltonian paths on the n X n king graph.

1, 24, 784, 343184, 729237344, 13089822163800, 1659110130720710584, 1635069460917798701270872, 12308784500036123518164726610224, 721833220650131890343295654587745095696, 330596986686626406483380599328509951896788808144

Offset: 1

Eric W. Weisstein, Mar 23 2009

Number of open directed king's tours on the n X n board.

Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, King Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A096969, A137891, A140521.

a(5) from Max Alekseyev, May 03 2009

a(6)-a(11) from Andrew Howroyd, Nov 15 2015

A333466 Number of self-avoiding closed paths on an n X n grid which pass through four corners ((0,0), (0,n-1), (n-1,n-1), (n-1,0)).

Original entry on oeis.org

1, 1, 11, 373, 44930, 17720400, 22013629316, 84579095455492

Offset: 2

Seiichi Manyama, Mar 22 2020

a(11) = 36061721109572407840288. - Seiichi Manyama, Apr 07 2020

			a(2) = 1;
   +--+
   |  |
   +--+
a(3) = 1;
   +--*--+
   |     |
   *     *
   |     |
   +--*--+
a(4) = 11;
   +--*--*--+   +--*--*--+   +--*--*--+
   |        |   |        |   |        |
   *--*--*  *   *--*  *--*   *--*     *
         |  |      |  |         |     |
   *--*--*  *   *--*  *--*   *--*     *
   |        |   |        |   |        |
   +--*--*--+   +--*--*--+   +--*--*--+
   +--*--*--+   +--*--*--+   +--*--*--+
   |        |   |        |   |        |
   *  *--*--*   *  *--*  *   *     *--*
   |  |         |  |  |  |   |     |
   *  *--*--*   *  *  *  *   *     *--*
   |        |   |  |  |  |   |        |
   +--*--*--+   +--*  *--+   +--*--*--+
   +--*--*--+   +--*--*--+   +--*  *--+
   |        |   |        |   |  |  |  |
   *        *   *        *   *  *--*  *
   |        |   |        |   |        |
   *  *--*  *   *        *   *  *--*  *
   |  |  |  |   |        |   |  |  |  |
   +--*  *--+   +--*--*--+   +--*  *--+
   +--*  *--+   +--*  *--+
   |  |  |  |   |  |  |  |
   *  *--*  *   *  *  *  *
   |        |   |  |  |  |
   *        *   *  *--*  *
   |        |   |        |
   +--*--*--+   +--*--*--+

Main diagonal of A333513.

Cf. A003763, A140517, A333246, A333247, A333323.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333466(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()
print([A333466(n) for n in range(2, 10)])

def search(x, y, n, used)
  return 0 if x < 0 || n <= x || y < 0 || n <= y || used[x + y * n]
  return 1 if x == 0 && y == 1 && [n - 1, n * (n - 1), n * n - 1].all?{|i| used[i] == true}
  cnt = 0
  used[x + y * n] = true
  @move.each{|mo|
    cnt += search(x + mo[0], y + mo[1], n, used)
  }
  used[x + y * n] = false
  cnt
end
def A(n)
  return 1 if n < 3
  @move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  used = Array.new(n * n, false)
  search(0, 0, n, used)
end
def A333466(n)
  (2..n).map{|i| A(i)}
end
p A333466(6)

A222199 Number of Hamiltonian cycles in the graph C_n X C_n.

Original entry on oeis.org

48, 1344, 23580, 3273360, 257165468, 171785923808, 61997157648756, 196554899918485160

Offset: 3

N. J. A. Sloane, Feb 14 2013

C_n X C_n is also known as the (n,n)-torus grid graph.

Artem M. Karavaev, Hamilton Cycles.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Eric Weisstein's World of Mathematics, Torus Grid Graph.

Cf. A270273, A003763, A222197, A268838, A222198, A193153, A270247.

Table[Length[FindHamiltonianCycle[GraphProduct[CycleGraph[n], CycleGraph[n], "Cartesian"], All]], {n, 3, 6}] (* Eric W. Weisstein, Dec 16 2023 *)

A268838 Number of (undirected) Hamiltonian paths in the torus grid graph C_n X C_n.

Original entry on oeis.org

1, 4, 756, 45696, 2955700, 560028096, 126412047692, 93784124187136

Offset: 1

Andrew Howroyd, Feb 14 2016

Here, X (sometimes also written \square) is the graph Cartesian product.

Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Torus Grid Graph

Cf. A003763, A222199, A120443, A268894.

A297664 Number of chordless cycles in the n X n grid graph.

Original entry on oeis.org

0, 1, 5, 24, 229, 3436, 65772, 1743247, 78586742, 7234839185, 1330059590925, 421587920205546, 212201572752086670, 170288846375423693683, 227570453486998336648738, 527014715702923506908210573, 2140337449056844246626590305042, 15055309813180236733267168372538873

Offset: 1

Eric W. Weisstein, Jan 02 2018

nonn

Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360196.

Cf. A003763, A140517, A360200, A360914.

a(7)-a(18) from Andrew Howroyd, Jan 08 2018

A302337 Triangle read by rows: T(n,k) is the number of 2k-cycles in the n X n grid graph (2 <= k <= floor(n^2/2), n >= 2).

Original entry on oeis.org

1, 4, 4, 5, 9, 12, 26, 52, 76, 32, 6, 16, 24, 61, 164, 446, 1100, 2102, 2436, 1874, 900, 226, 25, 40, 110, 332, 1070, 3504, 11144, 32172, 77874, 146680, 217470, 255156, 233786, 158652, 69544, 13732, 1072, 36, 60, 173, 556, 1942, 7092, 26424, 97624, 346428, 1136164, 3313812, 8342388, 18064642, 33777148, 54661008, 76165128, 89790912, 86547168, 64626638, 34785284, 12527632, 2677024, 255088

Offset: 2

Eric W. Weisstein, Apr 05 2018

			Triangle begins:
   1;
   4,  4,  5;
   9, 12, 26,  52,  76,   32,    6;
  16, 24, 61, 164, 446, 1100, 2102, 2436, 1874, 900, 226;
  ...
So for example, the 3 X 3 grid graph has 4 4-cycles, 4 6-cycles, and 5 8-cycles.

Seiichi Manyama, Rows n = 2..9, flattened
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Grid Graph

Cf. A003763 (number of Hamiltonian cycles in 2n X 2n grid graph).
Cf. A140517 (number of cycles).
Cf. A301648 (number of longest cycles).

Flatten[Table[Tally[Length /@ FindCycle[GridGraph[{n, n}], Infinity, All]][[All, 2]], {n, 6}]] (* Eric W. Weisstein, Mar 26 2021 *)

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A302337(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    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 A302337(n)])  # Seiichi Manyama, Mar 29 2020

Row sums equal A140517(n).
Length of row n equals A047838(n) = floor(n^2/2) - 1.
T(n,2) =    1 -   2*n +     n^2 = (n-1)^2.
T(n,3) =    4 -   6*n +   2*n^2 = A046092(n-2).
T(n,4) =   26 -  28*n +   7*n^2 for n > 2.
T(n,5) =  164 - 140*n +  28*n^2 for n > 3.
T(n,6) = 1046 - 740*n + 124*n^2 for n > 4.
T(n,k) = A302335(k) - A302336(k)*n + A002931(k)*n^2 for n > k-2.
T(n,floor(n^2/2)) = A301648(n).
T(n,n^2/2) = A003763(n) for n even.

A112675 Number of directed Hamiltonian paths on a triangular grid, n vertices on each side.

Original entry on oeis.org

1, 6, 24, 228, 3936, 132624, 8762040, 1156532424, 306700450536, 164818597404924, 180360080611682424, 403600060221250880496, 1853096813379189131728692, 17504763708306471241857275208

Offset: 1

Gareth McCaughan, Dec 30 2005

This sequence counts paths in a triangular region of the familiar 2-dimensional lattice in which each point has 6 neighbors (sometimes called either the "triangular" or the "hexagonal" lattice), visiting every vertex of the region exactly once. The paths are not assumed to be closed. A path and its reversal are not considered equivalent.

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Triangular Grid Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763, A112676.

a(8)-a(14) from Andrew Howroyd, Nov 02 2015

A143246 Number of (directed) Hamiltonian circuits in the n X n grid graph.

Original entry on oeis.org

0, 2, 0, 12, 0, 2144, 0, 9277152, 0, 934520913216, 0, 2152453777211211412, 0, 112252999240982874562527216, 0, 131765033045251672652319572331061144, 0, 3467852755777932367855581588111341658695967892, 0

Offset: 1

Eric W. Weisstein, Aug 01 2008

nonn

Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Ed Wynn, Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs, arXiv preprint arXiv:1402.0545 [math.CO], 2014.
Index entries for sequences related to graphs, Hamiltonian

Cf. A003763 (number of undirected cycles on 2n X 2n grid graph).
Cf. A222065 (A222065(n) = a(2n)).
Cf. A120443.

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

Original entry on oeis.org

0, 1, 4, 20, 346, 6891, 634172, 47917598, 27622729933, 6998287399637

Offset: 1

Christopher Hunt Gribble, Jul 05 2013

			When n = 2, there is only 1 Hamiltonian circuit in a 4 X 4 square lattice where the orbits under the symmetry group of the square have 2 elements.  The 2 elements are:
            o__o__o__o        o__o  o__o
            |        |        |  |  |  |
            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, A227257, A227301.

A063524 + A227005 + A227257 + A227301 = A209077.
1*A063524 + 2*A227005 + 4*A227257 + 8*A227301 = A003763.
a(2n) = A237431(2n), a(2n+1) = A237431(2n+1) + A237432(n+1). -  Ed Wynn, Feb 07 2014

a(4) from Giovanni Resta, Jul 11 2013

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

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

Original entry on oeis.org

0, 1, 24, 1760, 411861, 551247139, 2883245852086, 85948329517780776, 11001968794030973784902, 7462399462450938863305238264

Offset: 1

Christopher Hunt Gribble, Jul 05 2013

			When n = 2, there is only 1 Hamiltonian circuit in a 4 X 4 square lattice, where the orbits under the symmetry group of the square have 4 elements.  The 4 elements are:
    o__o__o__o    o__o__o__o    o__o__o__o    o__o  o__o
    |        |    |        |    |        |    |  |  |  |
    o  o__o__o    o  o__o  o    o__o__o  o    o  o  o  o
    |  |          |  |  |  |          |  |    |  |  |  |
    o  o__o__o    o  o  o  o    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, A227301.

A063524 + A227005 + A227257 + A227301 = A209077.
1*A063524 + 2*A227005 + 4*A227257 + 8*A227301 = A003763.
a(n) = A237429(n) + A237430(n). - Ed Wynn, Feb 07 2014

a(4) from Giovanni Resta, Jul 11 2013

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

cp's OEIS Frontend

A158651 Number of directed Hamiltonian paths on the n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A333466 Number of self-avoiding closed paths on an n X n grid which pass through four corners ((0,0), (0,n-1), (n-1,n-1), (n-1,0)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Ruby

A222199 Number of Hamiltonian cycles in the graph C_n X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A268838 Number of (undirected) Hamiltonian paths in the torus grid graph C_n X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

A297664 Number of chordless cycles in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A302337 Triangle read by rows: T(n,k) is the number of 2k-cycles in the n X n grid graph (2 <= k <= floor(n^2/2), n >= 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A112675 Number of directed Hamiltonian paths on a triangular grid, n vertices on each side.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A143246 Number of (directed) Hamiltonian circuits in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords