Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is a neat naming scheme for pentominoes based on letters they resemble. Is there a generalized naming scheme for polyominoes? If there isn't a canonical one, can you think of a good one?

Criteria

  1. I should be able to look at a given $n$-tomino and deduce a unique name in the system
  2. Names should be relatively concise
share|improve this question
    
fyi, N-tominoes are also called polyominos. –  Greg Martin Jan 19 '13 at 0:34
    
It seems unlikely. The number of polyominoes grows rapidly, about a factor 4 per square, see oeis.org/A000105 –  Ross Millikan Jan 19 '13 at 0:52
    
The number of isomers of a given alkane in chemistry grows pretty quickly too, but I can name all of these! Also on OEIS. –  orlandpm Jan 19 '13 at 1:02
    
@GregMartin thanks, reflected in edit –  orlandpm Jan 19 '13 at 6:11

2 Answers 2

No takers yet, so I'll give it a shot. Roughly, we can use some of the same strategies as naming carbon chains in organic chemistry: labeling long chains and then adding branches.

The simplest polyominoes are those with $n$ blocks in a straight line. We call the $n$th straight line polyomino $_nA$. For convenience later, we will construct $_nA$ from a preferred end by adding one block at a time. The polyominos $_1A$ through $_5A$ are below:

A series

For polyominoes which are straight but for a single bend, we start from the end closest to the bend, and mark the block where the first bend occurs as a superscript or subscript if it is a left or right bend respectively. If we don't allow reflections, then $_4A^2$ and $_4A_2$ are distinct. We would never write $_4A^3$, for example because that wouldn't have started counting from the end closest to the bend.

bends

If there are multiple bends, we include the locations of all bends and directions:

multiple bends

We can establish conventions like preferring smaller sets of indeces of bends, and preferring to start with a right turn. These are demonstrated above: we choose $_5A_{2,4}^3$ rather than $_5A_{3}^{2,4}$ because the right turn comes first in the former.

If the polyomino has branches, we can start with the longest branch and "sum" on the branches. The sum $+_n$ attaches the second term to the first at the $n$th side starting from the first. We can use parentheses to attach multiple branches.

enter image description here

Using this notation, we can describe every polyomino. However, we might want to add other elements like $m\times n$ blocks $_{mn}B_m$:

b series

The preferred side for numbering will be the far left of the bottom when the block is oriented vertically. We can add any number of strings to a block, and we will always start with the biggest block.

enter image description here

In principle, we can attach more blocks or chains on the end of any branch. If we wanted to make further simplifications, we could define rings by the polyominos they surround:

loop

Of course, with every simplification we make, we need to add more constraints so that we choose unique names for each polyomino. However, this description shows that in principle we can find a naming scheme for all polyominos.

Here are the named pentominoes. This scheme has the property that unbranched chiral pentominoes are obtained from their mirror images by switching subscripts and superscripts.

enter image description here

share|improve this answer

Oh, this looks like fun! Allow me to run with orlandpm's notation scheme by proposing a corresponding (natural language) naming scheme.

The simplest polyominoes $_1A,_2A,_3A,_4A,_5A,_6A,_7A,_8A,_9A,_{10}A,_{11}A,_{12}A,_{13}A,\dots$ we call henpo, dipo, tripo, tetrapo, pentapo, hexapo, heptapo, octapo, enneapo, decapo, hendecapo, dodecapo, triskaidecapo, and so on. Here we combine a Greek numeral prefix with "po", taken from the Greek "potami" meaning river (and nicely dovetailing with the word "polyomino").

A series

For polyominoes which are straight but for a single bend, such as $_4A^2$ and $_4A_2$, we append a numeral prefix and either "ar" (for a left turn) or "dex" for a right turn. The three tetrominoes below would be named tetrapo, tetrapodiar, and tetrapodidex. (Collapse two consecutive "a"s to one, so that $_8A_4$ would be octapotetrar rather than "octapotetraar".)

bends

If there are multiple bends, we keep appending. The first polyomino below can be called "pentapodidextriartetradex". I propose that if a turn occurs directly after a previous turn, then the numeral prefix can be omitted. Thus the first polyomino below would preferably be called pentapodidexardex. Similarly, the second polyomino is called octapodiardexardexheptadex.

multiple bends

If the polyomino has branches, we concatenate the names of the subpolyominos, with two additional changes. First indicate what base polyomino we are attaching subsidiary polyominoes to by changing the base's "po" to its long-form "pota". Second, we indicate the location of the attachment with a numeral prefix and "sy" (from "synapto", attach). The first polyomino below is dodecapopentarheptar, while the second one is dodecapotapentarheptartetrasydipo.

enter image description here

For blocks $_{mn}B_m$, we use the area's numeral prefix followed by "lim" (from "limni", lake), then the height's numeral prefix followed by "ups" ("upsos", height). (Some might have preferred "yps". We replace "au" by "u".) For example, a $4\times3$ block would be dodecalimtetrups, while a $6\times2$ block would be dodecalimhexups. For numbers with only one nontrivial factorization (that is, products of two primes or squares or cubes of primes), the height and "ups" should be omitted: the $_6B_3$ below is called hexalim rather than "hexalimtriups". (Its river-form name $_6A_{3,4}$ would have been "hexapotridexdex".) If a block is the base polyomino for attachments, we change "lim" to the long-form "limni".

b series

The first two polyominoes below are hexalimnitetrasytetrapo and hexalimnitetrasytetrapohexasytripodiar. I think the third one should be ${}_6B_3 ( {}\mathop{+}_4 {}_4A\ ( {}\mathop{+}_9 {}_1A \ ) )$ rather than ${}_6B_3 ( {}\mathop{+}_4 {}_4A\ ( {}\mathop{+}_2 {}_1A \ ) )$; hence its name would be "hexalimnitetrasytetrapotaenneasyhenpo". If a single block is the polyomino being attached, the "henpo" should be omitted, so that the third polyomino below is simply hexalimnitetrasytetrapotaenneasy.

enter image description here

Note a difference between the second and third names: in the second name, we had the long form "limni" but the short form "po", indicating that both subsidiary polyominoes are attached to the first one. In the third name, we had the long form "limni" and the long form "pota", indicating that the last polyomino is attached to the middle one rather than the initial one. In general, each new polyomino is attached to the most recent one with a long form; this rule indicates the default parenthesization.

It is sometimes necessary to parenthesize explicitly, even with the above rule. For example, we cannot yet distinguish the names of ${}_4B_2 ( {}\mathop{+}_1 {}_5A\ ( {}\mathop{+}_3 {}_1A\ {}\mathop{+}_5 {}_1A\ ))$ and ${}_4B_2 ( {}\mathop{+}_1 {}_5A\ ( {}\mathop{+}_3 {}_1A\ ) {}\mathop{+}_5 {}_1A\ )$. The former is called tetralimnihensypentapotatrisypentasy, since by default the final block (the omitted "henpo" in "pentasyhenpo") is attached to the most recent long-form "pentapota". To override this default parenthesization, we can surround an inner expression with "ex" and "ter". So the latter polyomino, ${}_4B_2 ( {}\mathop{+}_1 {}_5A\ ( {}\mathop{+}_3 {}_1A\ ) {}\mathop{+}_5 {}_1A\ )$, is called tetralimnihensyexpentapotatrisyterpentasy, to indicate that the "pentapotatrisy" and the omitted "henpo" are being hensy-attached and pentasy-attached to the base "tetralimni".

For rings defined by the polyominos they surround, we can use the suffix "ni" (from "nisi", island). The polyomino below is called tripodidexni. If other polyominos are attached to an island one, the long form "nisi" is used in place of "ni".

loop

Here are the names of all the pentominoes, listed by row in the order drawn below.

  1. pentapodidex, pentapodiar, pentapodidexar
  2. I think the notations of the first two pentominoes have been switched with each other. By the pictures, the names are tetrapotadiarpentasy and tetrapotadidexheptasy, followed by pentapodiardex.
  3. The first notation is wrong: it should be ${}_4A_2 ( {}\mathop{+}_8 {}_1A\ )$ and named tetrapotadidexoctasy. Following are pentapodidexardex and tripotatrisyheptasy.
  4. pentapotridex, pentapodidextetradex, tetralimnidisy
  5. pentapodidextetrar, pentapodiartetradex, tetralimnihensy
  6. The first one is tetrapotatrisy. The second one should be ${}_4A ( {}\mathop{+}_4 {}_1A\ )$, hence named tetrapotatetrasy. The last one is plain old pentapo.

enter image description here

Other shortcuts could be proposed, such as contracting "ardex" to "ax" and "dexar" to "der". I think I'll stop here though.

share|improve this answer
    
this is awesome. –  orlandpm Jan 19 '13 at 17:36
    
What happens if the ring is two-deep, or varies in depth (number of tiles surrounding an island)? Do we just fuse (sy-) on various river-form ominoes, or is there a shortercut (either that I am missing or which was not originally included)? Anyway, that is utterly wicked. –  konigr Feb 25 at 12:21
    
One could include shorter cuts; indeed, having islands in lakes is already a short cut - in principle one could do everything with just rivers. –  Greg Martin Feb 25 at 22:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.