Previously on this blog: “Polycube snakes and ouroboroi” (2022-11-18).
Preparing to add the sequences from that post into OEIS, I realized to my surprise that most of the 2D analogues weren’t yet in OEIS either! There are several near-miss variations, though, involving the following concepts:
Polyominoes with holes (snakes versus strips)
Any polyomino divides the plane into one or more rookwise-connected regions. Two chess rooks are in different regions if one cannot reach the other in any number of rookwise moves without at some point passing through a cell of the polyomino. A polyomino which divides the plane into \(k+1\) regions is said to have \(k\) holes.
The smallest polyomino with a hole is the O-heptomino… which also happens to be a polyomino snake.
The polyomino divides the two pictured rooks from each other; therefore it is not a strip.
Miroslav Vicher refers to polyomino snakes without holes as strip polyominoes. Strip polyominoes are interesting if your main recreational interests in polyominoes are tilings and dissections, because holes pose a problem for those tasks. The 30 free heptomino-strips can tile a pretty 14x15 rectangle:
but the 31 heptomino-snakes can’t tile any hole-free shape at all. Vicher notes that the 150 free nonomino-strips cannot tile any rectangle, either, because the nonomino depicted below has — not a hole, but what Vicher calls a cave.
Although the interior of the cave can be reached by a freely moving rook, it cannot be filled by any possible combination of snakes.
Vicher’s website often uses the shorthand “polystrip” to mean “strip polyomino”; but that’s unnecessarily confusing, given the established convention of using the suffix to identify the base form: polyomino, polyiamond, polyabolo, polyhex. We can speak also of strip polyiamonds, strip polyabolos, strip polyhexes; and snakes and ouroboroi of those forms as well.
OEIS sequences demonstrating the effect of holes include:
- OEIS A049429 counts free d-dimensional polycubes
- OEIS A000105 counts free polyominoes
- OEIS A002013 counts free snake polyominoes
- OEIS A333313 counts free snake polyominoes with no holes (i.e., strip polyominoes)
- OEIS A038119 counts free polycubes
- OEIS A357083 counts free polycubes with one or more holes
Holes in 3D
There are at least two ways to define the 3D equivalent of a “strip” (resp. “a snake without holes”).
The simplest kind of 3D “hole” is a fully enclosed empty region from which a 3D rook could not escape by 3D-rookwise moves; this is also known as a “cavity.” The smallest polycube with such a cavity is also a snake:
SRDRURDRURwraps around all six faces of an empty cell, in the same way as the O-heptomino wraps around all four sides of an empty 2D cell. Similarly, the shortest polyhypercube snake with a cavity would use 15 hypercubes to wrap around all eight hyperfaces of an empty 4D cell; and so on.
A different kind of 3D hole is the “donut hole”: a tunnel through which you can pass a string, then connect the ends of the string to form a loop, such that the loop of string cannot escape to infinity no matter how much it wiggles. Of the three free eight-cube ouroboroi, one (the simplest) has a donut hole, and the other two don’t. Of the two chiral ten-cube ouroboroi, one has a donut hole, and the other (being the polycube equivalent of a horn torus) doesn’t.
My lovely wife pointed out the donut-hole possibility; I then further observed that some polycube ouroboroi have what I might call “pseudo-tunnels,” where the ouroboros itself actually does not circumnavigate the tunnel, but simply doubles back on itself. We can characterize these pseudo-tunnels by whether our loop of string can escape them by wiggling through corners, or whether it must wiggle through edges as well. I believe the smallest polycube ouroboros with an “edge-type pseudo-tunnel” is this quite appropriately shaped 22-cube construction:
A minor tweak gives a 24-cube ouroboros with a “corner-type pseudo-tunnel”; this can be reduced to a 22-cube ouroboros (see my followup post).
One-sided versus free polyominoes
Whenever we talk about the distinctness of d-dimensional shapes, we must clarify what kinds of rotations we’re permitting.
- No rotations at all: “fixed” polyominoes
- Rotations in d-space but no higher: “one-sided” polyominoes
- Rotations through d+1-space: “two-sided” or “free” polyominoes
When counting “one-sided” 2D polyominoes, we don’t allow flipping them over through 3-space: mirror images are counted as distinct. Likewise, when counting “one-sided” 3D polycubes, we don’t allow flipping them through hyperspace: mirror images are counted as distinct. A polyform with distinct left- and right-handed variants is called “chiral”: its left- and right-handed variants are counted as two distinct one-sided polyforms, but identified as the same free polyform.
This notion of one-sidedness is different from my previous blog post’s notion of “directed snakes,” where I was distinguishing the snake’s head from its tail.
The mathematical term for that concept seems to be “rootedness,” although you might need some more verbiage to explain that a “rooted snake” must have its root actually at one of its ends, and not somewhere in the middle.
The following image shows just four free undirected polyomino snakes (the I, L, W, and Z pentominoes); but since the L and Z are chiral, we have a total of six one-sided undirected snakes in the left half of the image. Meanwhile, variants of the L and W produce six free directed/rooted snakes across the top half of the image; and the entire image shows nine examples of one-sided directed snakes. (Of course this is just a representative sampling of the total number of one-sided directed snake pentominoes.)
OEIS sequences demonstrating the effect of chirality include:
- OEIS A000988 counts one-sided polyominoes, which is the sum of:
- OEIS A000162 counts one-sided polycubes (A355966 counts those with cavities)
- OEIS A068870 counts one-sided polyhypercubes
- OEIS A255487 counts free polyhypercubes
- OEIS A151514 counts one-sided snake polyominoes
- OEIS A002013 counts free snake polyominoes
- OEIS A359068 counts one-sided strip polyominoes
- OEIS A333313 counts free strip polyominoes
Table of results (2D)
Here are my results for the 2D polyomino cases (source code). Columns corresponding to existing OEIS sequences are marked accordingly. OEIS sequences that did not exist prior to this blog post are italicized.
|n||Free strip polyominoes (A333313)||Free non-ouroboros snakes (A002013)||Free ouroboroi (A359706)||One-sided strips (A359068)||One-sided non-ouroboros snakes (A151514)||One-sided ouroboroi (A359707)|
Table of results (3D)
Here’s a partial table of 3D polycube cases (source code). Columns corresponding to existing OEIS sequences are marked, as above.
The table below indicates the existence of two chiral pairs among the 10-cube ouroboroi. Can you find them? How about the three different ways to enclose a cavity with a 12-cube ouroboros (one mirror-symmetric, the other two forming a chiral pair)?
|n||Free non-ouroboros snakes (A363202)||Free non-ouroboros snakes with cavities||Free ouroboroi||Free ouroboroi with cavities||One-sided non-ouroboros snakes (A363201)||One-sided non-ouroboros snakes with cavities||One-sided ouroboroi||One-sided ouroboroi with cavities|
- “Lego polycube snakes” (2022-12-11)