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

A332307 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n grid graph.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 8, 8, 1, 1, 14, 20, 14, 1, 1, 22, 62, 62, 22, 1, 1, 32, 132, 276, 132, 32, 1, 1, 44, 336, 1006, 1006, 336, 44, 1, 1, 58, 688, 3610, 4324, 3610, 688, 58, 1, 1, 74, 1578, 12010, 26996, 26996, 12010, 1578, 74, 1, 1, 92, 3190, 38984, 109722, 229348, 109722, 38984, 3190, 92, 1

Offset: 1

Andrew Howroyd, Feb 09 2020

			Array begins:
================================================
m\n | 1  2   3     4      5       6        7
----+-------------------------------------------
  1 | 1  1   1     1      1       1        1 ...
  2 | 1  4   8    14     22      32       44 ...
  3 | 1  8  20    62    132     336      688 ...
  4 | 1 14  62   276   1006    3610    12010 ...
  5 | 1 22 132  1006   4324   26996   109722 ...
  6 | 1 32 336  3610  26996  229348  1620034 ...
  7 | 1 44 688 12010 109722 1620034 13535280 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435
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

Rows n=1..9 are A000012, A003682, A003685, A003695, A003778, A145402, A358794, A358795, A358796.
Main diagonal is A120443.
Cf. A064298, A231829, A271465, A271592, A288518, A321172.

T(n,m) = T(m,n).

A288518 Array read by antidiagonals: T(m,n) = number of (undirected) paths in the grid graph P_m X P_n.

Original entry on oeis.org

0, 1, 1, 3, 12, 3, 6, 49, 49, 6, 10, 146, 322, 146, 10, 15, 373, 1618, 1618, 373, 15, 21, 872, 7119, 14248, 7119, 872, 21, 28, 1929, 28917, 111030, 111030, 28917, 1929, 28, 36, 4118, 111360, 801756, 1530196, 801756, 111360, 4118, 36

Offset: 1

Andrew Howroyd, Jun 10 2017

Paths of length zero are not counted here.

			Table starts:
=================================================================
m\n|  1    2      3       4         5          6            7
---|-------------------------------------------------------------
1  |  0    1      3       6        10         15           21 ...
2  |  1   12     49     146       373        872         1929 ...
3  |  3   49    322    1618      7119      28917       111360 ...
4  |  6  146   1618   14248    111030     801756      5493524 ...
5  | 10  373   7119  111030   1530196   19506257    235936139 ...
6  | 15  872  28917  801756  19506257  436619868   9260866349 ...
7  | 21 1929 111360 5493524 235936139 9260866349 343715004510 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Grid Graph

Rows 2-7 are A288516, A288527, A358800, A358801, A358802, A358803.
Main diagonal is A288032.
Cf. A231829, A064298, A271465, A271592, A120443, A001184, A145157, A003763.

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).

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

A378938 Array read by antidiagonals: T(m,n) is the number of Hamiltonian paths in an m X n grid which start in the top left corner.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 8, 4, 1, 1, 5, 17, 17, 5, 1, 1, 6, 38, 52, 38, 6, 1, 1, 7, 78, 160, 160, 78, 7, 1, 1, 8, 164, 469, 824, 469, 164, 8, 1, 1, 9, 332, 1337, 3501, 3501, 1337, 332, 9, 1, 1, 10, 680, 3750, 16262, 22144, 16262, 3750, 680, 10, 1

Offset: 1

Andrew Howroyd, Dec 20 2024

These paths are also called Greek-key tours. The path can end anywhere.

			Array begins:
======================================================
m\n | 1 2   3    4     5      6        7         8 ...
----+-------------------------------------------------
  1 | 1 1   1    1     1      1        1         1 ...
  2 | 1 2   3    4     5      6        7         8 ...
  3 | 1 3   8   17    38     78      164       332 ...
  4 | 1 4  17   52   160    469     1337      3750 ...
  5 | 1 5  38  160   824   3501    16262     68591 ...
  6 | 1 6  78  469  3501  22144   144476    899432 ...
  7 | 1 7 164 1337 16262 144476  1510446  13506023 ...
  8 | 1 8 332 3750 68591 899432 13506023 180160012 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)

Main diagonal is A145157.
Rows 1..8 are A000012, A000027, A046994, A046995, A145156, A160240, A160241, A374307.
Cf. A332307, A064298, A271465, A271592, A288518.

T(m,n) = T(n,m).

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

A181399 Summed lengths of nonintersecting rook paths on an n X k board (square array by antidiagonals).

Original entry on oeis.org

0, 1, 1, 2, 4, 2, 3, 14, 14, 3, 4, 40, 64, 40, 4, 5, 104, 284, 284, 104, 5, 6, 256, 1206, 1912, 1206, 256, 6, 7, 608, 4882, 13132, 13132, 4882, 608, 7, 8, 1408, 19060, 88608, 148432, 88608, 19060, 1408, 8, 9, 3200, 72588, 577727, 1692480, 1692480, 577727, 72588, 3200, 9

Offset: 1

David Scambler, Oct 17 2010

Paths are self-avoiding from one corner to the diagonally opposite corner.

			Array starts:
======================================================
n\k| 1   2     3      4        5        6        7
---|--------------------------------------------------
1  | 0   1     2      3        4        5        6 ...
2  | 1   4    14     40      104      256      608 ...
3  | 2  14    64    284     1206     4882    19060 ...
4  | 3  40   284   1912    13132    88608   577727 ...
5  | 4 104  1206  13132   148432  1692480 18893254 ...
6  | 5 256  4882  88608  1692480 32871240 ...
7  | 6 608 19060 577727 18893254 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..378 (terms 1..66 from David Scambler)

Related sequences: A181394 (3 X n), A181395 (4 X n), A181396 (5 X n), A181397 (6 X n), A181398 (n X n).

The number of these paths is given in A064298.

a(55) and a(60) in b-file corrected by Andrew Howroyd, Feb 23 2018

A064297 Triangle of self-avoiding rook paths joining opposite corners of n X k board.

Original entry on oeis.org

1, 1, 2, 1, 4, 12, 1, 8, 38, 184, 1, 16, 125, 976, 8512, 1, 32, 414, 5382, 79384, 1262816, 1, 64, 1369, 29739, 752061, 20562673, 575780564, 1, 128, 4522, 163496, 7110272, 336067810, 16230458696, 789360053252, 1, 256, 14934, 896476, 67005561

Offset: 1

Henry Bottomley, Sep 05 2001

			Triangle starts
1,
1, 2,
1, 4, 12,
1, 8, 38, 184,
1, 16, 125, 976, 8512,
1, 32, 414, 5382, 79384, 1262816,
1, 64, 1369, 29739, 752061, 20562673, 575780564,
1, 128, 4522, 163496, 7110272, 336067810, ...

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

Ruben Grønning Spaans, Triangle of rows 1 to 20, flattened
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]
Ruben Grønning Spaans, C program

Half of A064298.
Row/column combinations include A000012, A000079, A006192, A007786, A007787, A145403.
Right hand column is A007764.
Cf. A271465.

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

A332307 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A288518 Array read by antidiagonals: T(m,n) = number of (undirected) paths in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

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

Keywords

References

Links

Crossrefs

Programs

Python

Formula

Extensions

A378938 Array read by antidiagonals: T(m,n) is the number of Hamiltonian paths in an m X n grid which start in the top left corner.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A181399 Summed lengths of nonintersecting rook paths on an n X k board (square array by antidiagonals).