A271507 -id:A271507 - cp's OEIS frontend

A007764 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid.

1, 2, 12, 184, 8512, 1262816, 575780564, 789360053252, 3266598486981642, 41044208702632496804, 1568758030464750013214100, 182413291514248049241470885236, 64528039343270018963357185158482118, 69450664761521361664274701548907358996488

Offset: 1

David Radcliffe and Don Knuth

The length of the path varies.

			Suppose we start at (1,1) and end at (n,n). Let U, D, L, R denote steps that are up, down, left, right.
a(2) = 2: UR or RU.
a(3) = 12: UURR, UURDRU, UURDDRUU, URUR, URRU, URDRUU and their reflections in the x=y line.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, section 5.10, pp. 331-338.
Guttmann A J and Jensen I 2022 Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices Journal of Physics A: Mathematical and Theoretical 55 012345, (33pp) ; arXiv:2208.06744, Aug 2022.
D. E. Knuth, 'Things A Computer Scientist Rarely Talks About,' CSLI Publications, Stanford, CA, 2001, pages 27-28.
D. E. Knuth, The Art of Computer Programming, Section 7.1.4.
Shin-ichi Minato, The power of enumeration - BDD/ZDD-based algorithms for tackling combinatorial explosion, Chapter 3 of Applications of Zero-Suppressed Decision Diagrams, ed. T. Satsoa and J. T. Butler, Morgan & Claypool Publishers, 2014
Shin-ichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 1-6.
Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file. (Science Section).

I. Jensen, H. Iwashita, and R. Spaans, Table of n, a(n) for n = 1..27 (I. Jensen computed terms 1 to 20, H. Iwashita computed 21 and 22, R. Spaans computed 23 to 25, and H. Iwashita computed 26 and 27)
M. Bousquet-Mélou, A. J. Guttmann and I. Jensen, Self-avoiding walks crossing a square, arXiv:cond-mat/0506341 [cond-mat.stat-mech], 2005.
Doi, Maeda, Nagatomo, Niiyama, Sanson, Suzuki, et al., Time with class! Let's count! [Youtube-animation demonstrating this sequence. In Japanese with English translation]
Steven R. Finch, Self-Avoiding-Walk Connective Constants
Anthony J. Guttmann and Iwan Jensen, The gerrymander sequence, or A348456, arXiv:2211.14482 [math.CO], 2022.
H. Iwashita, J. Kawahara, and S. Minato, ZDD-Based Computation of the Number of Paths in a Graph, TCS Technical Report, TCS-TR-A-12-60, Hokkaido University, September 18, 2012.
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, Hokkaido University, April 26, 2013.
I. Jensen, Series Expansions for Self-Avoiding Walks
Shin-ichi Minato, Power of Enumeration - Recent Topics on BDD/ZDD-Based Techniques for Discrete Structure Manipulation, IEICE Transactions on Information and Systems, Volume E100.D (2017), Issue 8, p. 1556-1562.
Shin-ichi Minato, Motivating Problems and Algorithmic Solutions, Algorithmic Foundations for Social Advancement, Springer, Singapore (2025), 17-29.
OEIS Wiki, Self-avoiding_walks
Kohei Shinohara, Atsuto Seko, Takashi Horiyama, Masakazu Ishihata, Junya Honda, and Isao Tanaka, Derivative structure enumeration using binary decision diagram, arXiv:2002.12603 [physics.comp-ph], 2020.
Ruben Grønning Spaans, C program
Jens Weise, Evolutionary Many-Objective Optimisation for Pathfinding Problems, Ph. D. Dissertation, Otto von Guercke Univ., Magdeburg (Germany, 2022), see p. 53.
Eric Weisstein's World of Mathematics, Self-Avoiding Walk

Main diagonal of A064298.

Cf. A064297, A271507, A001184, A000532.

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

Computed to n=12 by John Van Rosendale in 1981
Extended to n=13 by Don Knuth, Dec 07 1995
Extended to n=20 by Mireille Bousquet-Mélou, A. J. Guttmann and I. Jensen
Extended to n=22 using ZDD technique based on Knuth's The Art of Computer Programming (exercise 225 in 7.1.4) by H. Iwashita, J. Kawahara, and S. Minato, Sep 18 2012
Extended to n=25 using state space compression (with rank/unrank) and dynamic programming (based in I. Jensen) by Ruben Grønning Spaans, Feb 22 2013
Extended to n=26 by Hiroaki Iwashita, Apr 11 2013
Extended to n=27 by Hiroaki Iwashita, Nov 18 2013

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

Original entry on oeis.org

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

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

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

A271465 Array read by antidiagonals: T(n,m) = number of self-avoiding walks of any length from NW to SW corners on a grid with n rows and m columns.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 11, 8, 1, 1, 5, 28, 38, 16, 1, 1, 6, 69, 178, 126, 32, 1, 1, 7, 168, 844, 1008, 415, 64, 1, 1, 8, 407, 4012, 8590, 5493, 1369, 128, 1, 1, 9, 984, 19072, 74148, 81445, 29879, 4521, 256, 1

Offset: 1

Andrew Howroyd, Apr 08 2016

			The start of the sequence as table:
*  1   1    1     1        1         1         1 ...
*  1   2    3     4        5         6         7 ...
*  1   4   11    28       69       168       407 ...
*  1   8   38   178      844      4012     19072 ...
*  1  16  126  1008     8590     74148    638472 ...
*  1  32  415  5493    81445   1246850  19011465 ...
*  1  64 1369  29879  761047  20477490 550254085 ...
*  ...

Andrew Howroyd, Table of n, a(n) for n = 1..378

Main diagonal is A271507. Rows include A005409, A214931. Columns include A006189, A216211. Cf. A064298 (paths from NW to SE).

T(1,n)=1, T(2,n)=n, T(n,1)=1, T(n,2)=2^(n-1).

A333247 Number of self-avoiding closed paths on an n X n grid which pass through NW and SW corners.

Original entry on oeis.org

1, 4, 47, 1843, 232905, 92729439, 115234959344, 442748883422394

Offset: 2

Seiichi Manyama, Mar 23 2020

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

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

Cf. A271507, A333246, A333323, A333466.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333247(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles().including(1).including(n)
    return cycles.len()
print([A333247(n) for n in range(2, 10)])

A333438 Number of self-avoiding walks of any length from NW corner to its adjacent points on an n X n grid or lattice.

Original entry on oeis.org

4, 16, 196, 8224, 1064540, 424745876, 527417814424, 2026136052712752, 23910840138416191440, 864203211903812503254788, 95556814333495667660116008300, 32299777937527326896385272155961508, 33351573725052992639783414388307775101504, 105136332761744656894957880833209728891149151420

Offset: 2

Seiichi Manyama, Mar 21 2020

nonn

			a(2) = 4;
   S--E   S  E
          |  |
          *--*
   S      S--*
   |         |
   E      E--*
a(3) = 16;
   S--E      S  E      S  E--*   S  E--*
             |  |      |     |   |     |
             *--*      *--*--*   *     *
                                 |     |
                                 *--*--*
   S  E      S  E--*   S  E--*   S  E
   |  |      |     |   |     |   |  |
   *  *      *  *--*   *--*  *   *  *--*
   |  |      |  |         |  |   |     |
   *--*      *--*         *--*   *--*--*
   S         S--*      S--*      S--*--*
   |            |         |            |
   E         E--*      E  *      E     *
                       |  |      |     |
                       *--*      *--*--*
   S--*--*   S--*--*   S--*      S--*--*
         |         |      |            |
   E--*--*   E  *--*   E  *--*   E--*  *
             |  |      |     |      |  |
             *--*      *--*--*      *--*

Ed Wynn, Table of n, a(n) for n = 2..19

Cf. A271507, A333439.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333438(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, 2
    paths = GraphSet.paths(start, goal)
    return paths.len() * 2
print([A333438(n) for n in range(2, 10)])

a(11) and a(13) from Seiichi Manyama

More terms from Ed Wynn, Jun 29 2023

A333439 a(n) = A333438(n)/2.

Original entry on oeis.org

2, 8, 98, 4112, 532270, 212372938, 263708907212, 1013068026356376, 11955420069208095720, 432101605951906251627394, 47778407166747833830058004150, 16149888968763663448192636077980754, 16675786862526496319891707194153887550752, 52568166380872328447478940416604864445574575710

Offset: 2

Seiichi Manyama, Mar 21 2020

nonn

Ed Wynn, Table of n, a(n) for n = 2..19

Cf. A271507, A333246, A333438.

a(11) and a(13) from Seiichi Manyama

More terms from Ed Wynn, Jun 29 2023

A329633 Triangle read by rows: T(n,k) is the number of self-avoiding paths of length n-1+2*k from NW to SW corners in the n X n grid graph (0 <= k <= A000217(n-1), n >= 1).

Original entry on oeis.org

1, 1, 1, 1, 3, 5, 2, 1, 6, 16, 39, 61, 47, 8, 1, 10, 40, 125, 400, 1048, 1905, 2372, 1839, 764, 86, 1, 15, 85, 335, 1237, 4638, 15860, 44365, 99815, 181995, 262414, 285086, 218011, 104879, 26344, 1770

Offset: 1

Seiichi Manyama, Mar 30 2020

			T(3,0) = 1;
   S
   |
   *
   |
   E
T(3,1) = 3;
   S--*      S--*      S
      |         |      |
   *--*         *      *--*
   |            |         |
   E         E--*      E--*
T(3,2) = 5;
   S--*--*   S--*--*   S--*--*   S--*      S
         |         |         |      |      |
   *--*--*      *--*         *      *--*   *--*--*
   |            |            |         |         |
   E         E--*      E--*--*   E--*--*   E--*--*
T(3,3) = 2;
   S--*--*   S  *--*
         |   |  |  |
   *--*  *   *--*  *
   |  |  |         |
   E  *--*   E--*--*
Triangle starts:
==========================================================
n\k| 0   1    2    3     4     5      6 ...    10 ...  15
---|------------------------------------------------------
1  | 1;
2  | 1,  1;
3  | 1,  3,   5,   2;
4  | 1,  6,  16,  39,   61,   47,     8;
5  | 1, 10,  40, 125,  400, 1048,  1905, ... , 86;
6  | 1, 15,  85, 335, 1237, 4638, 15860, ......... , 1770;

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

Row sums give A271507.
T(n,(n-1)*n/2) gives A000532(n).
Cf. A000217, A333520.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A329633(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(n - 1 + 2 * k).len() for k in range(n * (n - 1) // 2 + 1)]
print([i for n in range(1, 7) for i in A329633(n)])

T(n,0) = 1.

T(n,1) = A000217(n-1).

A363577 Number of inequivalent Hamiltonian paths starting in the lower left corner of an n X n grid graph (paths differing only by rotations and reflections are regarded as equivalent).

Original entry on oeis.org

1, 1, 3, 23, 347, 10199, 683227, 85612967, 25777385143, 14396323278040, 19799561204761862, 50351228336401026361, 319210377672595552740369, 3736517399241599771428011100, 109790442395888863208285555153329, 5952238893391106787883489313797219949

Offset: 1

Lars Blomberg, Jun 10 2023

Equivalently, number of inequivalent Hamiltonian paths starting in a corner of an n X n grid graph (paths differing only by rotations and reflections are regarded as equivalent). - Martin Ehrenstein, Jul 08 2023

			There are 3 paths for n=3:
  +--+--+    +--+--+    +--+  +
  |     |    |     |    |  |  |
  +  +  +    +  +--+    +  +  +
  |  |  |    |  |       |  |  |
  +  +--+    +  +--+    +  +--+
A fourth path:
  +--+--+
        |
  +--+  +
  |  |  |
  +  +--+
is the same as the second one in the row above after a 90-degree rotation.
All paths starting E are the same as the corresponding ones starting N after reflection in the forward diagonal.

Oliver R. Bellwood, Heitor P. Casagrande, and William J. Munro, Fractal Path Strategies for Efficient 2D DMRG Simulations, arXiv:2507.11820 [cond-mat.str-el], 2025. See p. 4.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path
Index entries for sequences related to graphs, Hamiltonian

Cf. A000532, A001184, A003763, A007764, A120443, A121785, A121789, A145157, A271507, A384173.

a(1) added by N. J. A. Sloane, Jun 10 2023
a(8)-a(9) from Martin Ehrenstein, Jul 08 2023
a(10)-a(16) from Oliver R. Bellwood, Jun 06 2025

cp's OEIS Frontend

A007764 Number of nonintersecting (or self-avoiding) rook paths joining opposite corners of an n X n grid.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

A271465 Array read by antidiagonals: T(n,m) = number of self-avoiding walks of any length from NW to SW corners on a grid with n rows and m columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A333247 Number of self-avoiding closed paths on an n X n grid which pass through NW and SW corners.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

A333438 Number of self-avoiding walks of any length from NW corner to its adjacent points on an n X n grid or lattice.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Extensions

A333439 a(n) = A333438(n)/2.

Views

Author

Keywords

Links

Crossrefs

Extensions

A329633 Triangle read by rows: T(n,k) is the number of self-avoiding paths of length n-1+2*k from NW to SW corners in the n X n grid graph (0 <= k <= A000217(n-1), n >= 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs