A271465 -id:A271465 - cp's OEIS frontend

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

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

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.

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

A006189 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with n rows and 3 columns.

Original entry on oeis.org

1, 1, 3, 11, 38, 126, 415, 1369, 4521, 14933, 49322, 162900, 538021, 1776961, 5868903, 19383671, 64019918, 211443426, 698350195, 2306494009, 7617832221, 25159990673, 83097804242, 274453403400, 906458014441, 2993827446721, 9887940354603, 32657648510531

Offset: 0

N. J. A. Sloane

a(n) = number of non-self-intersecting (or self-avoiding) paths from upper-left to lower-left of a grid of squares with 3 columns and n rows. E.g., for 3 columns and 2 rows, the paths are D, RDL, and RRDLL and the second a(n) = 3. The next a(n) = 11, which is the number of paths in a 3 X 3 grid: DD, DRDL, DRRDLL, DRURDDLL, RDDL, RDRDLL, RDLD, RRDDLL, RRDDLULD, RRDLDL, RRDLLD (where R=right, L=left, D=down, U=up). - Toby Gottfried, Mar 04 2013

H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..100
H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178. (Annotated scanned copy)
Index entries for linear recurrences with constant coefficients, signature (4,-3,2,1).

Column 3 of A271465.
Cf. A005409 (grids with 3 rows), A001333.
Cf. A214931 (grids with 4 rows).
Cf. A216211 (grids with 4 columns).

I:=[1,3,11,38]; [1] cat [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..41]]; // G. C. Greubel, May 24 2021

LinearRecurrence[{4,-3,2,1}, {1,1,3,11,38}, 100] (* Jean-François Alcover, Oct 08 2017 *)
With[{U = ChebyshevU}, Table[(1/2)*(U[n, 1/2] -U[n-1, 1/2] + I^n*(U[n, -3*I/2] + I*U[n-1, -3*I/2]) ), {n, 0, 40}]] (* G. C. Greubel, May 24 2021 *)

Vec((1-x)*(1-2*x)/((1-x+x^2)*(1-3*x-x^2)) + O(x^40)) \\ Colin Barker, Nov 17 2017

u=chebyshev_U;
[(1/2)*( u(n, 1/2) - u(n-1, 1/2) + i^n*(u(n, -3*i/2) + i*u(n-1, -3*i/2)) ) for n in (0..30)] # G. C. Greubel, May 24 2021

a(n) = 4*a(n-1) - 3*a(n-2) + 2*a(n-3) + a(n-4) for n > 3. - Giovanni Resta, Mar 13 2013
G.f.: (1-x)*(1-2*x)/((1 - x + x^2)*(1 - 3*x - x^2)). - Colin Barker, Nov 17 2017
2*a(n) = A010892(n) + A052924(n). - R. J. Mathar, Sep 27 2020
a(n) = (1/2)*( ChebyshevU(n, 1/2) - ChebyshevU(n-1, 1/2) + i^n*( ChebyshevU(n, -3*i/2) + i*ChebyshevU(n-1, -3*i/2) ) ). - G. C. Greubel, May 24 2021

Based on upper-left to lower-left path-counting program, more terms from Toby Gottfried, Mar 04 2013
Name clarified, offset changed, a(16)-a(25) from Andrew Howroyd, Apr 07 2016
a(0)=1 prepended by Colin Barker, Nov 17 2017

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

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.

A214931 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with 4 rows and n columns.

Original entry on oeis.org

1, 8, 38, 178, 844, 4012, 19072, 90658, 430938, 2048450, 9737260, 46285868, 220018976, 1045856010, 4971456754, 23631725866, 112332963420, 533972624844, 2538228811648, 12065422836242, 57352760145834, 272625264866098, 1295919060481740, 6160126839867820

Offset: 1

Toby Gottfried, Mar 09 2013

			For n=2, and moves U(p), D(own), R(ight), L(eft), the a(2)=8 walks are {DDD, DRDDL, DRDLD, DDRDL, RDDDL, RDDLD, RDLDD, RDLDRDL} with only the last touching all 8 squares of the grid.
Illustration of the 8 walks of a(2):
    .__      __      __        .       .        .       .     __
     __|    .  |    .  |    |__     |__      |  .    |  .     __|
    |  .     __|    .  |     __|     . |     |__     |  .    |__
    |  .    |  .     __|    |  .     __|      __|    |  .     __|

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

Row 4 of A271465.
Cf. A181688 (maximal walks with same conditions).
Cf. A005409 (grids with 3 rows), A006189 (grids with 3 columns).
Cf. A216211 (grids with 4 columns).

Empirical recurrence: a(1,...,5) = (1, 8, 38, 178, 844), a(n) = 7*a(n-1) - 12*a(n-2) + 7*a(n-3) - 3*a(n-4) - 2*a(n-5). - Giovanni Resta, Mar 13 2013

Empirical g.f.: x*(1+x-6*x^2+x^3+x^4)/(1-7*x+12*x^2-7*x^3+3*x^4+2*x^5). - Bruno Berselli, Mar 13 2013

Missing a(7) and a(13)-a(14) from Giovanni Resta, Mar 13 2013

a(15)-a(24) from Andrew Howroyd, Apr 08 2016

A216211 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with n rows and 4 columns.

Original entry on oeis.org

1, 4, 28, 178, 1008, 5493, 29879, 163357, 895519, 4911542, 26932856, 147666219, 809584243, 4438588016, 24334993398, 133419407518, 731487440774, 4010463570150, 21987820817522, 120550714106036, 660932932241338, 3623639639745022, 19867014703421770, 108923158026586497, 597183548915194615

Offset: 1

Toby Gottfried, Mar 13 2013

As n increases, the ratio of a(n)/a(n-1) appears to converge to around 5.483.

			For n=2, using the notation D(own), R(ight), L(eft), U(p), the 4 walks are {D, RDL, RRDLL, RRRDLLL}.

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

Column 4 of A271465. Cf. A005409 for grids with 3 rows, A006189 for grids with 3 columns, and A214931 for grids with 4 rows.

a[n_] := Block[{t=0,w,b=Array[1&, {n,4}]}, w[rr_,cc_] := Block[{r,c}, If[rr+cc == 2, t++, Do[{r,c} = {rr,cc} + e; If[0 0, b[[r,c]] = 0; w[r, c]; b[[r,c]] = 1], {e, {{-1,0}, {1,0}, {0,1}, {0,-1}}}]]]; b[[n,1]] = 0; w[n,1]; t]; a /@ Range[6] (* Giovanni Resta, Mar 13 2013 *)

Conjectures from Colin Barker, Nov 18 2017: (Start)
G.f.: x*(1 - 8*x + 34*x^2 - 66*x^3 + 21*x^4 + 85*x^5 - 64*x^6 - 45*x^7 + 26*x^8 + 11*x^9 - 3*x^10 - x^11) / ((1 - 8*x + 15*x^2 - 5*x^3 - 9*x^4 + 2*x^5 + x^6)*(1 - 4*x + 7*x^2 - 3*x^3 - 7*x^4 + 2*x^5 + x^6)).
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) for n>12.
(End)

a(13)-a(14) from Giovanni Resta, Mar 13 2013

Terms a(15) and beyond from Andrew Howroyd, Apr 08 2016

cp's OEIS Frontend

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

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

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

A006189 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with n rows and 3 columns.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

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

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

A214931 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with 4 rows and n columns.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A216211 Number of self-avoiding walks of any length from NW to SW corners of a grid or lattice with n rows and 4 columns.

Views

Author

Keywords