|
Search: id:A070030
|
|
|
| A070030 |
|
Number of closed Knight's tours on a 3 X 2n board. |
|
+0
2
|
|
| 0, 0, 0, 0, 16, 176, 1536, 15424, 147728, 1448416, 14060048, 136947616, 1332257856, 12965578752, 126169362176, 1227776129152, 11947846468608, 116266505653888, 1131418872918784, 11010065269439104, 107141489725900544
(list; graph; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
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.
|
|
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)
|
|
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.
|
|
PROGRAM
|
(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
|
Cf. A001230.
Sequence in context: A021374 A017931 A021129 this_sequence A017521 A007144 A002399
Adjacent sequences: A070027 A070028 A070029 this_sequence A070031 A070032 A070033
|
|
KEYWORD
|
easy,nice,nonn
|
|
AUTHOR
|
Noam D. Elkies (elkies(AT)math.harvard.edu), Apr 13 2002
|
|
|
Search completed in 0.002 seconds
|
