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

1, 16, 125, 976, 8512, 79384, 752061, 7110272, 67005561, 630588698, 5933085772, 55827318685, 525343024814, 4943673540576, 46521924780255, 437788749723725, 4119750109152730, 38768318191017931, 364823700357765771, 3433121323699285343

Offset

1,2

References

Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file (Science Section).

Links

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

Formula

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]

Prog

(Python)
# 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

Crossrefs

Row 5 of A064298.

Cf. A007764, A007786.

Sequence in context: A000485 A264625 A213748 * A067470 A133111 A268998

Adjacent sequences: A007784 A007785 A007786 * A007788 A007789 A007790

Keyword

nonn,walk

Author

Heiner Marxen

Extensions

More terms from Ralf Stephan, Mar 29 2004

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009

Status

approved