The Universe of Discourse

Fri, 30 Nov 2018

How many kinds of polygonal loops? (part 2)

I recently asked about these:

Four displays, each with five dark gray dots arranged at the vertices
of a regular pentagon.  In each display the dots are connected with
purple lines, but each in a different order.  If the dots were
numbered 0-1-2-3-4 in clockwise order, the four figures have purple
lines connecting them, respectively, in the orders
0-1-2-3-4-0, 0-1-3-2-4-0, 0-2-1-4-3-0, and 0-2-4-1-3-0.  The first of
these is a plain pentagon, and the last is a five-pointed star.  The
middle two are less symmetric.

And I said I thought there were nine analogous figures with six points.

Rahul Narain referred me to a recent discussion of almost this exact question on Math Stackexchange. (Note that the discussion there considers two figures different if they are reflections of one another; I consider them the same.) The answer turns out to be OEIS A000940. I had said:

… for !!N=6!!, I found it hard to enumerate. I think there are nine shapes but I might have missed one, because I know I kept making mistakes in the enumeration …

I missed three. The nine I got were:

This time
there are nine displays, each with six dots.  The connections are,
012345 (a hexagon), 015432, 032145 (two diamonds), 
015234 (highly irregular), 014523 (three triangles that share a vertex
in the center), 013254, 023154, 031254, and 035142.

And the three I missed are:

more hexagons, this time connected as follows:
014253, 013524, and 015342

I had tried to break them down by the arrangement of the outside ring of edges, which can be described by a composition. The first two of these have type !!1+1+1+1+2!! (which I missed completely; I thought there were none of this type) and the other has type !!1+2+1+2!!, the same as the !!015342!! one in the lower right of the previous diagram.

I had ended by saying:

I would certainly not trust myself to hand-enumerate the !!N=7!! shapes.

Good call, Mr. Dominus! I considered filing this under “oops” but I decided that although I had gotten the wrong answer, my confidence in it had been adequately low. On one level it was a mistake, but on a higher and more important level, I did better.

I am going to try the (Cauchy-Frobenius-)Burnside-(Redfield-)Pólya lemma on it next and see if I can get the right answer.

Thanks again to Rahul Narain for bringing this to my attention.

[Other articles in category /math] permanent link