|
%I #37 Apr 18 2018 08:34:47
%S 0,0,0,0,16,176,1536,15424,147728,1448416,14060048,136947616,
%T 1332257856,12965578752,126169362176,1227776129152,11947846468608,
%U 116266505653888,1131418872918784,11010065269439104,107141489725900544,1042616896632882688,10145938076107491328
%N Number of closed Knight's tours on a 3 X 2n board.
%C Leonhard Euler stated that no such tours are possible [Memoires Acad. Roy. Sci. (Berlin, 1759), 310-337], and many authors echoed this statement until Ernest Bergholt exhibited solutions for 2n=10 and 12 in British Chess Magazine 1918, page 74. The full set of 16 solutions for 2n=10 was published by Kraitchik in 1927. - _Don Knuth_, Apr 28 2010
%C Obtained independently by _Don Knuth_ and _Noam D. Elkies_ in April 1994, both using the transfer-matrix method (in slightly different ways). For this method, see for instance chapter 4.7 of R. P. Stanley's Enumerative Combinatorics, Vol. 1 (1986).
%C Ian Stewart, Mathematical Recreations column, Scientific American, February 1998, "Feedback", page 95, reports that Richard Ulmer of Denver has sent him a letter reporting work on this subject, about which he is writing a thesis, giving the terms though a(21). - _N. J. A. Sloane_, Mar 01 2018
%D D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.
%H Alois P. Heinz, <a href="/A070030/b070030.txt">Table of n, a(n) for n = 1..1000</a>
%H N. D. Elkies and R. P. Stanley, <a href="http://dx.doi.org/10.1007/BF02985635">The mathematical knight</a>, Math. Intelligencer, 25 (No. 1) (2003), 22-34.
%H George Jelliss, <a href="http://www.mayhematics.com/t/oa.htm">Open knight's tours of three-rank boards</a>, Knight's Tour Notes, note 3a (21 October 2000).
%H George Jelliss, <a href="http://www.mayhematics.com/t/ob.htm">Closed knight's tours of three-rank boards</a>, Knight's Tour Notes, note 3b (21 October 2000).
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KnightsTour.html">Knight's Tour</a>
%F Generating function: 16 * (z^5 + 5*z^6 - 34*z^7 - 116*z^8 + 505*z^9 + 616*z^10 - 3179*z^11 - 4*z^12 + 9536*z^13 - 8176*z^14 - 13392*z^15 + 15360*z^16 + 13888*z^17 + 2784*z^18 - 3328*z^19 - 22016*z^20 + 5120*z^21 + 2048*z^22) / (1 - 6*z - 64*z^2 + 200*z^3 + 1000*z^4 - 3016*z^5 - 3488*z^6 + 24256*z^7 - 23776*z^8 - 104168*z^9 + 203408*z^10 + 184704*z^11 - 443392*z^12 - 14336*z^13 + 151296*z^14 - 145920*z^15 + 263424*z^16 - 317440*z^17 - 36864*z^18 + 966656*z^19 - 573440*z^20 - 131072*z^21).
%F Asymptotic value .0001899*3.11949^(2n). - _Don Knuth_, Apr 28 2010. More decimal places: a(n) ~ 0.0001898644879979384968655648993009439045986223511152141689341... * 3.1194904567551021585814810124470909514449088706168023079811958...^(2*n). - _Vaclav Kotesovec_, Mar 03 2016
%F a(n) = A158074(n)/2. - _Eric W. Weisstein_, Mar 18 2009
%F Recurrence (D. E. Knuth and N. D. Elkies, 1994): a(n) = 6*a(n-1) + 64*a(n-2) - 200*a(n-3) - 1000*a(n-4) + 3016*a(n-5) + 3488*a(n-6) - 24256*a(n-7) + 23776*a(n-8) + 104168*a(n-9) - 203408*a(n-10) - 184704*a(n-11) + 443392*a(n-12) + 14336*a(n-13) - 151296*a(n-14) + 145920*a(n-15) - 263424*a(n-16) + 317440*a(n-17) + 36864*a(n-18) - 966656*a(n-19) + 573440*a(n-20) + 131072*a(n-21), for n>=23. - _Vaclav Kotesovec_, Mar 03 2016
%e The smallest 3 X 2n board admitting a closed Knight's tour is the 3 X 10, on which there are 16 such tours.
%t Rest[CoefficientList[Series[16 * (x^5 + 5*x^6 - 34*x^7 - 116*x^8 + 505*x^9 + 616*x^10 - 3179*x^11 - 4*x^12 + 9536*x^13 - 8176*x^14 - 13392*x^15 + 15360*x^16 + 13888*x^17 + 2784*x^18 - 3328*x^19 - 22016*x^20 + 5120*x^21 + 2048*x^22) / (1 - 6*x - 64*x^2 + 200*x^3 + 1000*x^4 - 3016*x^5 - 3488*x^6 + 24256*x^7 - 23776*x^8 - 104168*x^9 + 203408*x^10 + 184704*x^11 - 443392*x^12 - 14336*x^13 + 151296*x^14 - 145920*x^15 + 263424*x^16 - 317440*x^17 - 36864*x^18 + 966656*x^19 - 573440*x^20 - 131072*x^21), {x, 0, 30}], x]] (* _Vaclav Kotesovec_, Mar 03 2016 *)
%o (PARI) g = 16 * (z^5 + 5*z^6 - 34*z^7 - 116*z^8 + 505*z^9 + 616*z^10 - 3179*z^11 - 4*z^ 12 + 9536*z^13 - 8176*z^14 - 13392*z^15 + 15360*z^16 + 13888*z^17 + 2784*z^18 - 3328*z^19 - 22016*z^20 + 5120*z^21 + 2048*z^22) / (1 - 6*z - 64*z^2 + 200*z^3 + 1000*z^4 - 3016*z^5 - 3488*z^6 + 24256*z^7 - 23776*z^8 - 104168*z^9 + 203408*z^1 0 + 184704*z^11 - 443392*z^12 - 14336*z^13 + 151296*z^14 - 145920*z^15 + 263424* z^16 - 317440*z^17 - 36864*z^18 + 966656*z^19 - 573440*z^20 - 131072*z^21); g = g + O(z^31); vector(30,n,polcoeff(g,n))
%Y See also A169764, which gives the number of closed Knight's tours on a 3 X n board. Cf. A169696, A169765-A169777, A001230.
%Y Cf. A158074.
%K easy,nice,nonn
%O 1,5
%A _Noam D. Elkies_, Apr 13 2002
%E Comment corrected by _Johannes W. Meijer_, Nov 22 2010
| 