A polyknight is a plane geometric figure formed by selecting cells in a square lattice that could represent the path of a chess knight in which doubling back is allowed. It is a polyform with square cells which are not necessarily connected, comparable to the polyking. Alternatively, it can be interpreted as a connected subset of the vertices of a knight's graph, a graph formed by connecting pairs of lattice squares that are a knight's move apart.[1]
Enumeration of polyknights
editFree, one-sided, and fixed polyknights
editThree common ways of distinguishing polyominoes for enumeration[2] can also be extended to polyknights:
- free polyknights are distinct when none is a rigid transformation (translation, rotation, reflection or glide reflection) of another (pieces that can be picked up and flipped over).
- one-sided polyknights are distinct when none is a translation or rotation of another (pieces that cannot be flipped over).
- fixed polyknights are distinct when none is a translation of another (pieces that can be neither flipped nor rotated).
The following table shows the numbers of polyknights of various types with n cells.
| n | free | one-sided | fixed |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 1 | 2 | 4 |
| 3 | 6 | 8 | 28 |
| 4 | 35 | 68 | 234 |
| 5 | 290 | 550 | 2,162 |
| 6 | 2,680 | 5,328 | 20,972 |
| 7 | 26,379 | 52,484 | 209,608 |
| 8 | 267,598 | 534,793 | 2,135,572 |
| 9 | 2,758,016 | 5,513,338 | 22,049,959 |
| 10 | 28,749,456 | 57,494,308 | 229,939,414 |
| OEIS | A030446 | A030445 | A030444 |
Free polyknights
-
The 290 free pentaknights. -
The 2,680 free hexaknights.
Notes
edit- ^ Aleksandrowicz, Gadi; Barequet, Gill (2011), "Parallel enumeration of lattice animals", in Atallah, Mikhail J.; Li, Xiang-Yang; Zhu, Binhai (eds.), Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2011, Jinhua, China, May 28-31, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6681, Springer, pp. 90–99, doi:10.1007/978-3-642-21204-8_13, ISBN 978-3-642-21203-1.
- ^ Redelmeier, D. Hugh (1981), "Counting polyominoes: yet another attack", Discrete Mathematics, 36 (2): 191–203, doi:10.1016/0012-365X(81)90237-5
