A007764 -id:A007764 - cp's OEIS frontend

A120443 Number of (undirected) Hamiltonian paths in the n X n grid graph.

1, 4, 20, 276, 4324, 229348, 13535280, 3023313284, 745416341496, 730044829512632, 786671485270308848, 3452664855804347354220, 16652005717670534681315580, 331809088406733654427925292528, 7263611367960266490262600117251524

Offset: 1

David Bevan, Jul 19 2006

			From _Robert FERREOL_, Apr 03 2019: (Start)
a(3) = 20:
there are 4 paths similar to
  + - + - +
          |
  + - + - +
  |
  + - + - +
8 paths similar to
  + - + - +
  |       |
  +   + - +
  |   |
  +   + - +
and 8 paths similar to
  + - + - +
  |       |
  +   +   +
  |   |   |
  +   + - +
(End)

Jesper L. Jacobsen, Table of n, a(n) for n = 1..17
J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor. 40 (2007) 14667-14678.
J.-M. Mayer, C. Guez and J. Dayantis, Exact computer enumeration of the number of Hamiltonian paths in small square plane lattices, Physical Review B, Vol. 42 Number 1, 1990.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path
Index entries for sequences related to graphs, Hamiltonian

Main diagonal of A332307.
Cf. A003685, A003695, A003778, A145402.
Cf. A003763, A000532, A001184, A145157, A271507, A007764, A121785, A121789.

a(n) = A096969(n) / 2 for n > 1.

More terms from Jesper L. Jacobsen (jesper.jacobsen(AT)u-psud.fr), Dec 12 2007

A140517 Number of cycles in an n X n grid.

Original entry on oeis.org

0, 1, 13, 213, 9349, 1222363, 487150371, 603841648931, 2318527339461265, 27359264067916806101, 988808811046283595068099, 109331355810135629946698361371, 36954917962039884953387868334644457, 38157703688577845304445530851242055267353, 120285789340533859558405124213592877516931371715

Offset: 0

Don Knuth, Jul 26 2008

nonn

Or, number of simply connected and rookwise connected regions of an (n-1) X (n-1) grid.

D. E. Knuth, The Art of Computer Programming, Volume 4A, Section 7.1.4.

Artem M. Karavaev and Hiroaki Iwashita, Table of n, a(n) for n = 0..26 (A. Karavaev computed terms 10 to 19)
Fawaz Alazemi, Arash Azizimazreah, Bella Bose, and Lizhong Chen, Routerless Networks-on-Chip, U.S. Patent Application No. 15,445,736, 2017.
H. Iwashita, Y. Nakazawa, J. Kawahara, T. Uno, and S. Minato, Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions, TCS Technical Report, TCS -TR-A-13-64, Division of Computer Science, Hokkaido University, Report Series A, April 26 2013.
Artem M. Karavaev, FlowProblem.Ru: All Simple Cycles
Kimberly Villalobos, Vilim Štih, Amineh Ahmadinejad, Shobhita Sundaram, Jamell Dozier, Andrew Francl, Frederico Azevedo, Tomotake Sasaki, and Xavier Boix, Do Neural Networks for Segmentation Understand Insideness?, MIT Center for Brains, Minds + Machines, CBMM Memo (2020) No. 105.
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Grid Graph
Wikipedia, ZDD

Corner-to-corner paths in this grid are enumerated in A007764.

Main diagonal of A231829.

Table[Length[FindCycle[GridGraph[{n, n}], Infinity, All]], {n, 6}] (* Eric W. Weisstein, Mar 07 2023 *)

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A140517(n):
    if n == 0: return 0
    universe = tl.grid(n, n)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A140517(n) for n in range(9)])  # Seiichi Manyama, Mar 23 2020

a(9) calculated using the ZDD technique described in Knuth's The Art of Computer Programming, Exercises 7.1.4, by Ashutosh Mehra, Dec 19 2008
a(10)-a(19) calculated using a transfer matrix method by Artem M. Karavaev, Jun 03 2009, Oct 20 2009
a(20)-a(26) calculated by Hiroaki Iwashita, Apr 26 2013, Nov 18 2013
Edited by Max Alekseyev, Jan 24 2018

A000532 Number of Hamiltonian paths from NW to SW corners in an n X n grid.

Original entry on oeis.org

1, 1, 2, 8, 86, 1770, 88418, 8934966, 2087813834, 1013346943033, 1111598871478668, 2568944901392936854, 13251059359839620127088, 145194816279817259193401518, 3524171261632305641165676374930, 182653259988707123426135593460533473

Offset: 1

Russ Cox, Mar 15 1996

Number of walks reaching each cell exactly once.

Oliver R. Bellwood, Table of n, a(n) for n = 1..20 (first 19 terms from KeyTo9(AT)Fans, Ed Wynn)
KeyTo9(AT)Fans, Counting paths in a grid - Chinese web page giving the sequence up to 18 items.
Douglas M. McKenna, Tendril Motifs for Space-Filling, Half-Domino Curves, in: Bridges Finland Conference Proceedings, 2016, pp. 119-126.
Douglas M. McKenna, Are Maximally Unbalanced Hilbert-Style Square-Filling Curve Motifs a Drawing Medium?, Bridges Conf. Proc.; Math., Art, Music, Architecture, Culture (2023) 91-98.

Main diagonal of A271592.
Cf. A181688, A181689, A014524, A014585.
Cf. A001184, A145157, A120443, A003763, A271507, A007764, A121785, A121789.
See also A350148.

More terms from Zhao Hui Du, Jul 08 2008
Edited by Franklin T. Adams-Watters, Jul 03 2009
Name clarified by Andrew Howroyd, Apr 10 2016

A064298 Square array read by antidiagonals of self-avoiding rook paths joining opposite corners of n X k board.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 12, 8, 1, 1, 16, 38, 38, 16, 1, 1, 32, 125, 184, 125, 32, 1, 1, 64, 414, 976, 976, 414, 64, 1, 1, 128, 1369, 5382, 8512, 5382, 1369, 128, 1, 1, 256, 4522, 29739, 79384, 79384, 29739, 4522, 256, 1, 1, 512, 14934, 163496, 752061, 1262816, 752061, 163496, 14934, 512, 1

Offset: 1

Henry Bottomley, Sep 05 2001

			The start of the sequence as table:
* 1  1    1     1      1        1         1 ...
* 1  2    4     8     16       32        64 ...
* 1  4   12    38    125      414      1369 ...
* 1  8   38   184    976     5382     29739 ...
* 1 16  125   976   8512    79384    752061 ...
* 1 32  414  5382  79384  1262816  20562673 ...
* 1 64 1369 29739 752061 20562673 575780564 ...

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 331-339.

Andrew Howroyd, Table of n, a(n) for n = 1..378
Steven R. Finch, Self-Avoiding Walks of a Rook on a Chessboard [From Steven Finch, Apr 20 2019]
Steven R. Finch, Self-Avoiding Walks of a Rook [From Steven Finch, Apr 20 2019; mentioned in Finch's "Gammel" link above]
Steven R. Finch, Table of Non-Overlapping Rook Paths [From Steven Finch, Apr 20 2019; mentioned in Finch's "Gammel" link above]

A064297 together with its transpose.
Rows and columns include A000012, A000079, A006192, A007786, A007787, A145403, A333812.
Main diagonal is A007764.
Cf. A271465.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A064298(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, k * n
    paths = GraphSet.paths(start, goal)
    return paths.len()
print([A064298(j + 1, i - j + 1) for i in range(11) for j in range(i + 1)])  # Seiichi Manyama, Apr 06 2020

A145157 Number of Greek-key tours on an n X n board; i.e., self-avoiding walks on n X n grid starting in top left corner.

Original entry on oeis.org

1, 2, 8, 52, 824, 22144, 1510446, 180160012, 54986690944, 29805993260994, 41433610713353366, 103271401574007978038, 660340630211753942588170, 7618229614763015717175450784, 225419381425094248494363948728158

Offset: 1

Nathaniel Johnston, Oct 03 2008

The sequence may be enumerated using standard methods for counting Hamiltonian cycles on a modified graph with two additional nodes, one joined to a corner vertex and the other joined to all other vertices. - Andrew Howroyd, Nov 08 2015

Nathaniel Johnston, On Maximal Self-Avoiding Walks
Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.

Main diagonal of A378938.
Cf. A046994, A046995, A145156, A160240, A160241.
Cf. A000532, A001184, A120443, A003763, A271507, A007764.

a(9)-a(15) from Andrew Howroyd, Nov 08 2015

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

Original entry on oeis.org

1, 5, 235, 96371, 447544629, 22132498074021, 10621309947362277575, 50819542770311581606906543, 2460791237088492025876789478191411, 1207644919895971862319430895789323709778193, 5996262208084349429209429097224046573095272337986011

Offset: 1

Don Knuth, Jul 26 2008

This graph is the "strong product" of P_n with P_n, where P_n is a path of length n. Sequence A007764 is what we get when we restrict ourselves to rook moves of unit length.

Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

			For example, when n=8 this is the number of ways to move a king from a1 to h8 without occupying any cell twice.

Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 2009.

Jens Weise, Evolutionary Many-Objective Optimisation for Pathfinding Problems, Ph. D. Dissertation, Otto von Guercke Univ., Magdeburg (Germany, 2022), see p. 53.

Main diagonal of A329118.
Cf. A140519, A158651, A234622, A007764, A038496.
Cf. A220638 (Hosoya index).

a(9)-a(11) from Andrew Howroyd, Apr 07 2016

A271507 Number of self-avoiding walks of any length from NW to SW corners on an n X n grid or lattice.

Original entry on oeis.org

1, 2, 11, 178, 8590, 1246850, 550254085, 741333619848, 3046540983075504, 38141694646516492843, 1453908228148524205711098, 168707605740228097581729005751, 59588304533380500951726150179910606, 64061403305026776755367065417308840021540

Offset: 1

Andrew Howroyd, Apr 08 2016

nonn

Main diagonal of A271465.

Cf. A007764, A000532, A001184, A145157, A120443, A003763.

A271465 = Cases[Import["https://oeis.org/A271465/b271465.txt", "Table"], {, }][[All, 2]];
a[n_] := A271465[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 14}] (* Jean-François Alcover, Sep 23 2019 *)

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A271507(n):
    if n == 1: return 1
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n
    paths = GraphSet.paths(start, goal)
    return paths.len()
print([A271507(n) for n in range(1, 10)])  # Seiichi Manyama, Mar 21 2020

A007786 Number of nonintersecting rook paths joining opposite corners of 4 X n board.

Original entry on oeis.org

1, 8, 38, 184, 976, 5382, 29739, 163496, 896476, 4913258, 26932712, 147657866, 809563548, 4438573234, 24335048679, 133419610132, 731487691902, 4010463268476, 21987818897998, 120550710615560, 660932932108467

Offset: 1

Heiner Marxen

Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file. (Science Section).

Harvey P. Dale, Table of n, a(n) for n = 1..1000
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
F. Faase, Rook path problem
D. G. Radcliffe, N. J. A. Sloane, C. Cole, J. Gillogly, & D. Dodson, Emails, 1994
Index entries for linear recurrences with constant coefficients, signature (12,-54,124,-133,-16,175,-94,-69,40,12,-4,-1).

Row 4 of A064298.

Cf. A006192, A007764, A007787.

LinearRecurrence[{12,-54,124,-133,-16,175,-94,-69,40,12,-4,-1},{1,8,38,184,976,5382,29739,163496,896476,4913258,26932712,147657866},30] (* Harvey P. Dale, Jun 27 2012 *)

a(n) = 12*a(n - 1) - 54*a(n - 2) + 124*a(n - 3) - 133*a(n - 4) - 16*a(n - 5) + 175*a(n - 6) - 94*a(n - 7) - 69*a(n - 8) + 40*a(n - 9) + 12*a(n - 10) - 4*a(n - 11) - a(n - 12). - Vladeta Jovovic, Mar 20 2000

G.f.: x*(x^10-15*x^8+6*x^7+50*x^6-26*x^5-39*x^4+36*x^3-4*x^2-4*x+1) / ((x^6+2*x^5-9*x^4-5*x^3+15*x^2-8*x+1)*(x^6+2*x^5-7*x^4-3*x^3+7*x^2-4*x+1)). [Colin Barker, Nov 24 2012]

More terms from Vladeta Jovovic, Mar 20 2000

A007787 Number of nonintersecting rook paths joining opposite corners of 5 X n board.

Original entry on oeis.org

1, 16, 125, 976, 8512, 79384, 752061, 7110272, 67005561, 630588698, 5933085772, 55827318685, 525343024814, 4943673540576, 46521924780255, 437788749723725, 4119750109152730, 38768318191017931, 364823700357765771, 3433121323699285343

Offset: 1

Heiner Marxen

Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file (Science Section).

Seiichi Manyama, Table of n, a(n) for n = 1..1000
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
D. G. Radcliffe, N. J. A. Sloane, C. Cole, J. Gillogly, & D. Dodson, Emails, 1994

Row 5 of A064298.

Cf. A007764, A007786.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A064298(n, k):
    if n == 1 or k == 1: return 1
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, k * n
    paths = GraphSet.paths(start, goal)
    return paths.len()
def A007787(n):
    return A064298(n, 5)
print([A007787(n) for n in range(1, 20)])  # Seiichi Manyama, Apr 06 2020

Faase gives a 27-term linear recurrence on his web page:
a(1) = 1,
a(2) = 16,
a(3) = 125,
a(4) = 976,
a(5) = 8512,
a(6) = 79384,
a(7) = 752061,
a(8) = 7110272,
a(9) = 67005561,
a(10) = 630588698,
a(11) = 5933085772,
a(12) = 55827318685,
a(13) = 525343024814,
a(14) = 4943673540576,
a(15) = 46521924780255,
a(16) = 437788749723725,
a(17) = 4119750109152730,
a(18) = 38768318191017931,
a(19) = 364823700357765771,
a(20) = 3433121323699285343,
a(21) = 32306898830469680384,
a(22) = 304019468350280601960,
a(23) = 2860931888452842047170,
a(24) = 26922391858409506569346,
a(25) = 253349332040459400463497,
a(26) = 2384107785665647075602841,
a(27) = 22435306570786253414376286 and
a(n) = 30a(n-1) - 383a(n-2) + 2772a(n-3) - 12378a(n-4) + 33254a(n-5)
- 40395a(n-6) - 44448a(n-7) + 239776a(n-8) - 274256a(n-9) - 180404a(n-10)
+ 678758a(n-11) - 301650a(n-12) - 542266a(n-13) + 492472a(n-14) + 184306a(n-15)
- 225284a(n-16) - 102314a(n-17) + 25534a(n-18) + 97396a(n-19) + 10392a(n-20)
- 40292a(n-21) - 13218a(n-22) + 5328a(n-23) + 5376a(n-24) + 1822a(n-25)
+ 319a(n-26) + 24a(n-27).
Asymptotics: a(n) ~ 0.115762181699251 * 9.4103574958247159212^n [From Vaclav Kotesovec, Aug 31 2012]

More terms from Ralf Stephan, Mar 29 2004

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009

A006192 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of 3 X n board.

Original entry on oeis.org

1, 4, 12, 38, 125, 414, 1369, 4522, 14934, 49322, 162899, 538020, 1776961, 5868904, 19383672, 64019918, 211443425, 698350194, 2306494009, 7617832222, 25159990674, 83097804242, 274453403399, 906458014440

Offset: 1

N. J. A. Sloane

H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 331-339.
Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file. (Science Section).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..150
H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178. (Annotated scanned copy)
F. Faase, Counting Hamiltonian cycles in product graphs
F. Faase, Results from the counting program
Steven R. Finch, Self-Avoiding Walks of a Rook on a Chessboard [From Steven Finch, Apr 20 2019]
Steven R. Finch, Self-Avoiding Walks of a Rook [From Steven Finch, Apr 20 2019; mentioned in Finch's "Gammel" link above]
Steven R. Finch, Table of Non-Overlapping Rook Paths [From Steven Finch, Apr 20 2019; mentioned in Finch's "Gammel" link above]
D. G. Radcliffe, N. J. A. Sloane, C. Cole, J. Gillogly, & D. Dodson, Emails, 1994
Index entries for linear recurrences with constant coefficients, signature (4,-3,2,1).

Cf. A064297, A064298, A007786, A007787, A007764.

I:=[1,4,12,38]; [n le 4 select I[n] else 4*Self(n-1)-3*Self(n-2)+2*Self(n-3)+Self(n-4): n in [1..30]]; // Vincenzo Librandi, Oct 06 2011

LinearRecurrence[{4,-3,2,1},{1,4,12,38},40] (* Harvey P. Dale, Oct 05 2011 *)

a(n) = 4*a(n-1) - 3*a(n-2) + 2*a(n-3) + a(n-4) with a(0) = 0, a(1) = 1, a(2) = 4 and a(3) = 12. - Henry Bottomley, Sep 05 2001

G.f.: x*(1-x^2)/(1 - 4*x + 3*x^2 - 2*x^3 - x^4). - Emeric Deutsch, Dec 22 2004

cp's OEIS Frontend

A120443 Number of (undirected) Hamiltonian paths in the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A140517 Number of cycles in an n X n grid.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A000532 Number of Hamiltonian paths from NW to SW corners in an n X n grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A064298 Square array read by antidiagonals of self-avoiding rook paths joining opposite corners of n X k board.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Python

A145157 Number of Greek-key tours on an n X n board; i.e., self-avoiding walks on n X n grid starting in top left corner.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A140518 Number of simple paths from corner to corner of an n X n grid with king-moves allowed.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A271507 Number of self-avoiding walks of any length from NW to SW corners on an n X n grid or lattice.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Python

A007786 Number of nonintersecting rook paths joining opposite corners of 4 X n board.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A007787 Number of nonintersecting rook paths joining opposite corners of 5 X n board.

Views

Author