A000532 -id:A000532 - 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

A271592 Array read by antidiagonals: T(n,m) = number of directed Hamiltonian walks from NW to SW corners on a grid with n rows and m columns.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 2, 1, 1, 0, 1, 0, 4, 0, 1, 0, 1, 4, 8, 8, 1, 1, 0, 1, 0, 23, 0, 16, 0, 1, 0, 1, 8, 55, 86, 47, 32, 1, 1, 0, 1, 0, 144, 0, 397, 0, 64, 0, 1, 0, 1, 16, 360, 948, 1770, 1584, 264, 128, 1, 1, 0, 1, 0, 921, 0, 11658, 0, 6820, 0, 256, 0, 1

Offset: 1

Andrew Howroyd, Apr 10 2016

			The start of the sequence as table:
* 1 0   0   0     0     0       0       0          0 ...
* 1 1   1   1     1     1       1       1          1 ...
* 1 0   2   0     4     0       8       0         16 ...
* 1 1   4   8    23    55     144     360        921 ...
* 1 0   8   0    86     0     948       0      10444 ...
* 1 1  16  47   397  1770   11658   59946     359962 ...
* 1 0  32   0  1584     0   88418       0    4999752 ...
* 1 1  64 264  6820 52387  909009 8934966  130373192 ...
* 1 0 128   0 28002     0 7503654       0 2087813834 ...
* ...

Andrew Howroyd, Antidiagonals n = 1..27, flattened

Column 4 is aerated A014524, column 5 is A014585.
Rows include A181688, A181689.
Main diagonal is A000532.
Cf. A333580.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A271592(n, k):
    if k == 1: return 1
    universe = tl.grid(k - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
print([A271592(j + 1, i - j + 1) for i in range(12) for j in range(i + 1)])  # Seiichi Manyama, Mar 28 2020

T(n,m)=0 for n odd and m even, T(1,n)=0 for n>1.

T(2,n)=T(n,1)=T(2*n,2)=1, T(3,2*n+1)=T(n+1,3)=2^n.

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

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

A121785 "Spanning walks" on the square lattice (see Jensen web site for further information).

Original entry on oeis.org

8, 95, 2320, 154259, 30549774, 17777600753, 30283708455564, 152480475641255213, 2287842813828061810244, 102744826737618542833764649, 13848270995235582268846758977770

Offset: 1

N. J. A. Sloane, Aug 30 2006

nonn

Number of Hamiltonian paths in the graph P_{n+1} X P_{n+1} starting at any of the n+1 vertices on one side of the graph and terminating at any of the n+1 vertices on the opposite side. - Andrew Howroyd, Apr 10 2016

Anthony J. Guttmann and Iwan Jensen, Table of n, a(n) for n = 1..26
Anthony J. Guttmann and Iwan Jensen, Self-avoiding walks and polygons crossing a domain on the square and hexagonal lattices, arXiv:2208.06744 [math-ph], Aug 13 2022, table D1.
I. Jensen, Series Expansions for Self-Avoiding Walks
I. Jensen, Spanning walks (terms)

Cf. A000532, A001184, A121789, A215527.

Cf. A333323, A356610-A356616, A354511.

A014585 Number of Hamiltonian paths in a 5 X n grid starting in the lower left corner and ending in the lower right.

Original entry on oeis.org

0, 0, 1, 4, 23, 86, 397, 1584, 6820, 28002, 117852, 488824, 2043133, 8502298, 35463855, 147729456, 615817511, 2566065066, 10694840588, 44568760860, 185743671308, 774073998864, 3225960662493, 13444082934608

Offset: 0

N. J. A. Sloane

nonn

The difference between A014584 and A014585 needs to be clarified. - N. J. A. Sloane, Feb 08 2013

The difference is that A014584 counts paths starting in the LL finishing in the UR. A014585 counts paths starting in the LL finishing the LR. - Ruben Zilibowitz, Jul 05 2015

K. L. Collins and L. B. Krompart, The number of Hamiltonian paths in a rectangular grid, Discrete Math. 169 (1997), 29-38.
Index entries for sequences related to graphs, Hamiltonian

Column 5 of A271592.

Cf. A000532, A181689, A014584, A014524, A003778, A006865.

The reference gives a generating function.

Definition clarified by Ruben Zilibowitz, Jul 05 2015

A181688 Number of maximal self-avoiding walks from NW to SW corners of a 4-by-n grid.

Original entry on oeis.org

1, 1, 4, 8, 23, 55, 144, 360, 921, 2329, 5924, 15024, 38159, 96847, 245888, 624176, 1584593, 4022609, 10211940, 25924088, 65811431, 167069767, 424126160, 1076693080, 2733310377, 6938824361, 17615009476, 44717740000, 113521160607, 288186606623

Offset: 1

Sean A. Irvine, Nov 17 2010

			Illustration of a(1)=a(2)=1:
   .    .__.
   |    .__|
   |    |__
   |    .__|
Illustration of a(3)=4:
   .__.__.    .  .__.    .  .__.    .__.__.
   .__.__|    |__|  |    |  |  |    .__.  |
   |__.__.    .__.  |    |__|  |    |  |  |
   .__.__|    |  |__|    .__.__|    |  |__|

Index entries for linear recurrences with constant coefficients, signature (2, 2, -2, 1).

Row 4 of A271592.

Cf. A000532, A014524, A014523, A181689, A003695, A006864.

LinearRecurrence[{2, 2, -2, 1}, {1, 1, 4, 8}, 30] (* T. D. Noe, Nov 06 2013 *)

G.f.: (x^2-x)/(x^4-2*x^3+2*x^2+2*x-1).

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

G.f. formula reverted to the original (correct) value by Stefan Bühler, Nov 06 2013

A014524 Number of Hamiltonian paths from NW to SW corners in a grid with 2n rows and 4 columns.

Original entry on oeis.org

0, 1, 8, 47, 264, 1480, 8305, 46616, 261663, 1468752, 8244304, 46276385, 259755560, 1458042831, 8184190168, 45938958232, 257861540369, 1447411446840, 8124514782015, 45603992276896, 255981331487648

Offset: 0

N. J. A. Sloane

			Illustration of a(1)=1:
   .__.__.__.
   .__.__.__|
Illustration of a few of the 8 solutions to a(2):
   .__.__.__.    .  .__.__.    .  .__.__.    .__.__.__.
   .__.__.  |    |  |  .__|    |__|  .__|    .__.__.__|
   |__   |  |    |__|  |__.    .__.  |__.    |__.__.__.
   .__|  |__|    .__.__.__|    |  |__.__|    .__.__.__|

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
K. L. Collins and L. B. Krompart, The number of Hamiltonian paths in a rectangular grid, Discrete Math. 169 (1997), 29-38.
Index entries for sequences related to graphs, Hamiltonian
Index entries for linear recurrences with constant coefficients, signature (7,-9,7,-1).

Even bisection of column 4 of A271592.

Cf. A000532, A181688, A014523, A014585, A003695, A006864.

CoefficientList[Series[x (x + 1)/(x^4 - 7 x^3 + 9 x^2 - 7 x + 1), {x, 0, 50}], x] (* Vincenzo Librandi, Oct 15 2013 *)

From Colin Barker, May 20 2013: (Start)
a(n) = 7*a(n-1)-9*a(n-2)+7*a(n-3)-a(n-4).
G.f.: x*(x+1)/(x^4-7*x^3+9*x^2-7*x+1). (End)

Name clarified by Andrew Howroyd, Apr 10 2016

A181689 Number of maximal self-avoiding walks from NW to SW corners of a 5 X n grid.

Original entry on oeis.org

1, 0, 8, 0, 86, 0, 948, 0, 10444, 0, 115056, 0, 1267512, 0, 13963520, 0, 153828832, 0, 1694652176, 0, 18669100976, 0, 205667768400, 0, 2265734756752, 0, 24960420526224, 0, 274975961325264, 0, 3029267044091408, 0, 33371858326057936, 0, 367640393509287824, 0, 4050102862690348880, 0, 44617875206245953552, 0, 491531908055724064720, 0, 5414951194338345409680, 0, 59653698888134291413584, 0, 657173751585588653678864, 0, 7239741169830151881286864

Offset: 1

Sean A. Irvine, Nov 17 2010

All even terms are 0.

Index entries for linear recurrences with constant coefficients, signature (0,11,0,0,0,2).

Row 5 of A271592.

Cf. A000532, A003778, A006865, A014584, A014585, A181688.

I:=[1,0,8,0,86,0]; [n le 6 select I[n] else 11*Self(n-2)+2*Self(n-6): n in [1..50]]; // Wesley Ivan Hurt, Apr 10 2016

A181689:=proc(n) option remember:
if n mod 2 = 0 then 0 elif n=1 then 1 elif n=3 then 8 elif n=5 then 86 else 11*a(n-2)+2*a(n-6); fi; end: seq(A181689(n), n=1..50); # Wesley Ivan Hurt, Apr 10 2016

CoefficientList[Series[(1 - 3*x^2 - 2*x^4)/(1 - 11*x^2 - 2*x^6), {x, 0, 50}], x] (* Wesley Ivan Hurt, Apr 10 2016 *)

x='x+O('x^99); Vec(x*(1-3*x^2-2*x^4)/(1-11*x^2-2*x^6)) \\ Altug Alkan, Apr 11 2016

G.f.: x*(1 - 3*x^2 - 2*x^4)/(1 - 11*x^2 - 2*x^6).

a(n) = 11*a(n-2) + 2*a(n-6) for n>6. - Wesley Ivan Hurt, Apr 10 2016

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

A271592 Array read by antidiagonals: T(n,m) = number of directed Hamiltonian walks from NW to SW corners on a grid with n rows and m columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

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

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

A121785 "Spanning walks" on the square lattice (see Jensen web site for further information).

Views

Author

Keywords

Comments

Links

Crossrefs

A014585 Number of Hamiltonian paths in a 5 X n grid starting in the lower left corner and ending in the lower right.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A181688 Number of maximal self-avoiding walks from NW to SW corners of a 4-by-n grid.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A014524 Number of Hamiltonian paths from NW to SW corners in a grid with 2n rows and 4 columns.

Views

Author

Keywords

Examples