|
| |
|
|
A070030
|
|
Number of closed Knight's tours on a 3 X 2n board.
|
|
18
| |
|
|
0, 0, 0, 0, 16, 176, 1536, 15424, 147728, 1448416, 14060048, 136947616, 1332257856, 12965578752, 126169362176, 1227776129152, 11947846468608, 116266505653888, 1131418872918784, 11010065269439104, 107141489725900544
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,5
|
|
|
COMMENTS
| 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. - D. E. Knuth, Apr 28 2010
Obtained independently by D. E. 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).
|
|
|
REFERENCES
| N. D. Elkies and R. P. Stanley, The mathematical knight, Math. Intelligencer, 25 (No. 1, 2003), 22-34.
D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.
|
|
|
LINKS
| George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).
Eric Weisstein's World of Mathematics, Knight's Tour [From Eric W. Weisstein (eric(AT)weisstein.com), Mar 18 2009]
|
|
|
FORMULA
| 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)
Asymptotic value .0001899*3.11949^(2n). - D. E. Knuth, Apr 28 2010
|
|
|
EXAMPLE
| The smallest 3 X 2n board admitting a closed Knight's tour is the 3 X 10, on which there are 16 such tours.
|
|
|
PROG
| (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))
|
|
|
CROSSREFS
| See also A169764, which gives the number of closed Knight's tours on a 3 X n board. Cf. A169696, A169765-A169777, A001230.
Equals A158074(n)/2. Cf. A158074 [From Eric W. Weisstein (eric(AT)weisstein.com), Mar 18 2009]
Sequence in context: A187720 A017931 A021129 * A017521 A007144 A002399
Adjacent sequences: A070027 A070028 A070029 * A070031 A070032 A070033
|
|
|
KEYWORD
| easy,nice,nonn
|
|
|
AUTHOR
| Noam D. Elkies (elkies(AT)math.harvard.edu), Apr 13 2002
|
|
|
EXTENSIONS
| Comment corrected by Johannes W. Meijer (meijgia(AT)hotmail.com), Nov 22 2010
|
| |
|
|
