cp's OEIS Frontend

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

%I A007787 #26 Apr 06 2020 06:29:11
%S A007787 1,16,125,976,8512,79384,752061,7110272,67005561,630588698,5933085772,
%T A007787 55827318685,525343024814,4943673540576,46521924780255,
%U A007787 437788749723725,4119750109152730,38768318191017931,364823700357765771,3433121323699285343
%N A007787 Number of nonintersecting rook paths joining opposite corners of 5 X n board.
%D A007787 Netnews group rec.puzzles, Frequently Asked Questions (FAQ) file (Science Section).
%H A007787 Seiichi Manyama, <a href="/A007787/b007787.txt">Table of n, a(n) for n = 1..1000</a>
%H A007787 F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H A007787 F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H A007787 D. G. Radcliffe, N. J. A. Sloane, C. Cole, J. Gillogly, & D. Dodson, <a href="/A007765/a007765.pdf">Emails, 1994</a>
%F A007787 Faase gives a 27-term linear recurrence on his web page:
%F A007787 a(1) = 1,
%F A007787 a(2) = 16,
%F A007787 a(3) = 125,
%F A007787 a(4) = 976,
%F A007787 a(5) = 8512,
%F A007787 a(6) = 79384,
%F A007787 a(7) = 752061,
%F A007787 a(8) = 7110272,
%F A007787 a(9) = 67005561,
%F A007787 a(10) = 630588698,
%F A007787 a(11) = 5933085772,
%F A007787 a(12) = 55827318685,
%F A007787 a(13) = 525343024814,
%F A007787 a(14) = 4943673540576,
%F A007787 a(15) = 46521924780255,
%F A007787 a(16) = 437788749723725,
%F A007787 a(17) = 4119750109152730,
%F A007787 a(18) = 38768318191017931,
%F A007787 a(19) = 364823700357765771,
%F A007787 a(20) = 3433121323699285343,
%F A007787 a(21) = 32306898830469680384,
%F A007787 a(22) = 304019468350280601960,
%F A007787 a(23) = 2860931888452842047170,
%F A007787 a(24) = 26922391858409506569346,
%F A007787 a(25) = 253349332040459400463497,
%F A007787 a(26) = 2384107785665647075602841,
%F A007787 a(27) = 22435306570786253414376286 and
%F A007787 a(n) = 30a(n-1) - 383a(n-2) + 2772a(n-3) - 12378a(n-4) + 33254a(n-5)
%F A007787 - 40395a(n-6) - 44448a(n-7) + 239776a(n-8) - 274256a(n-9) - 180404a(n-10)
%F A007787 + 678758a(n-11) - 301650a(n-12) - 542266a(n-13) + 492472a(n-14) + 184306a(n-15)
%F A007787 - 225284a(n-16) - 102314a(n-17) + 25534a(n-18) + 97396a(n-19) + 10392a(n-20)
%F A007787 - 40292a(n-21) - 13218a(n-22) + 5328a(n-23) + 5376a(n-24) + 1822a(n-25)
%F A007787 + 319a(n-26) + 24a(n-27).
%F A007787 Asymptotics: a(n) ~ 0.115762181699251 * 9.4103574958247159212^n [From _Vaclav Kotesovec_, Aug 31 2012]
%o A007787 (Python)
%o A007787 # Using graphillion
%o A007787 from graphillion import GraphSet
%o A007787 import graphillion.tutorial as tl
%o A007787 def A064298(n, k):
%o A007787     if n == 1 or k == 1: return 1
%o A007787     universe = tl.grid(n - 1, k - 1)
%o A007787     GraphSet.set_universe(universe)
%o A007787     start, goal = 1, k * n
%o A007787     paths = GraphSet.paths(start, goal)
%o A007787     return paths.len()
%o A007787 def A007787(n):
%o A007787     return A064298(n, 5)
%o A007787 print([A007787(n) for n in range(1, 20)])  # _Seiichi Manyama_, Apr 06 2020
%Y A007787 Row 5 of A064298.
%Y A007787 Cf. A007764, A007786.
%K A007787 nonn,walk
%O A007787 1,2
%A A007787 Heiner Marxen
%E A007787 More terms from _Ralf Stephan_, Mar 29 2004
%E A007787 Added recurrence from Faase's web page. - _N. J. A. Sloane_, Feb 03 2009