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

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

A181395 Summed lengths of nonintersecting rook paths on a 4 X n board.

Original entry on oeis.org

3, 40, 284, 1912, 13132, 88608, 577727, 3659416, 22719964, 139088248, 842307548, 5055782456, 30119691570, 178296516264, 1049685801023, 6150604755800, 35890214413836, 208663068856540, 1209212316951436, 6987073893141896, 40267076160162015, 231512818498197668

Offset: 1

David Scambler, Oct 17 2010

nonn

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

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

Row 4 of A181399.

Enumeration of these paths is A007786, related sequences A181394, A181396, A181397, A181398.

Conjectured g.f.: x*(1 - x)*(3 - 29*x + 51*x^2 + 595*x^3 - 3879*x^4 + 9553*x^5 - 8366*x^6 - 8026*x^7 + 22931*x^8 - 13117*x^9 - 5593*x^10 + 7955*x^11 - 6118*x^12 + 6842*x^13 + 1884*x^14 - 6824*x^15 + 519*x^16 + 1991*x^17 - 206*x^18 - 230*x^19 + 13*x^20 + 9*x^21)/((1 - 8*x + 15*x^2 - 5*x^3 - 9*x^4 + 2*x^5 + x^6)^2*(1 - 4*x + 7*x^2 - 3*x^3 - 7*x^4 + 2*x^5 + x^6)^2). - Andrew Howroyd, Jan 06 2020

a(10)-a(13) from Alois P. Heinz, Dec 10 2011

Terms a(14) and beyond from Andrew Howroyd, Jan 06 2020

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.

A244088 Decimal expansion of 1/2+2/sqrt(13), a constant related to the asymptotic evaluation of the number of self-avoiding rook paths joining opposite corners on a 3 X n chessboard.

Original entry on oeis.org

1, 0, 5, 4, 7, 0, 0, 1, 9, 6, 2, 2, 5, 2, 2, 9, 1, 2, 2, 0, 1, 8, 3, 4, 1, 7, 3, 3, 4, 5, 6, 9, 9, 9, 3, 7, 6, 3, 4, 6, 3, 5, 3, 3, 1, 9, 0, 5, 3, 1, 1, 4, 8, 0, 1, 9, 5, 5, 4, 5, 4, 3, 1, 6, 3, 4, 2, 6, 4, 1, 0, 6, 8, 9, 6, 8, 1, 5, 5, 4, 5, 3, 1, 0, 8, 4, 0, 2, 9, 3, 5, 6, 9, 5, 1, 5, 2, 4, 1, 8

Offset: 1

Jean-François Alcover, Jun 20 2014

			1.054700196225229122018341733456999376346353319...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.10.2 Rook paths on a chessboard, p. 334.

Cf. A006192, A007764, A007786, A007787, A244089.

RealDigits[1/2 + 2/Sqrt[13], 10, 100] // First

Asymptotic number of paths = p(k) ~ (1/2+2/sqrt(13)) * sqrt((3+sqrt(13))/2)^(2k), where k = n-1.

A244089 Decimal expansion of sqrt((3+sqrt(13))/2), a constant related to the asymptotic evaluation of the number of self-avoiding rook paths joining opposite corners on a 3 X n chessboard.

Original entry on oeis.org

1, 8, 1, 7, 3, 5, 4, 0, 2, 1, 0, 2, 3, 9, 7, 0, 6, 2, 0, 0, 7, 5, 1, 9, 4, 4, 8, 6, 0, 3, 5, 8, 2, 1, 9, 2, 6, 4, 6, 9, 4, 0, 3, 6, 4, 3, 1, 2, 7, 1, 3, 6, 1, 1, 2, 0, 6, 3, 3, 0, 7, 7, 0, 5, 8, 2, 7, 9, 8, 9, 9, 4, 3, 8, 6, 8, 3, 6, 5, 6, 9, 3, 6, 7, 8, 1, 9, 2, 0, 1, 7, 8, 1, 0, 0, 6, 2, 6, 7, 8

Offset: 1

Jean-François Alcover, Jun 20 2014

			1.8173540210239706200751944860358219264694...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.10.2 Rook paths on a chessboard, p. 334.

Cf. A006192, A007764, A007786, A007787, A244088.

RealDigits[Sqrt[(3 + Sqrt[13])/2], 10, 100] // First

Asymptotic number of paths = p(k) ~ (1/2+2/sqrt(13)) * sqrt((3+sqrt(13))/2)^(2k), where k = n-1.

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

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Python

Formula

Extensions

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

A181395 Summed lengths of nonintersecting rook paths on a 4 X n board.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

A244088 Decimal expansion of 1/2+2/sqrt(13), a constant related to the asymptotic evaluation of the number of self-avoiding rook paths joining opposite corners on a 3 X n chessboard.

Views

Author

Keywords

Examples

References

Crossrefs

Programs

Mathematica

Formula

A244089 Decimal expansion of sqrt((3+sqrt(13))/2), a constant related to the asymptotic evaluation of the number of self-avoiding rook paths joining opposite corners on a 3 X n chessboard.

Views

Author

Keywords

Examples

References

Crossrefs

Programs

Mathematica

Formula