How many non-isomorphic ways a convex polygon with $n + 2$ sides can be cut into triangles?

Question

From Wikipedia:

The Catalan number $C_n$ is the number of different ways a convex polygon with $n + 2$ sides can be cut into triangles by connecting vertices with straight lines (a form of Polygon triangulation). The following hexagons illustrate the case $n = 4$:

$\hskip0.7in$

Combining triangulations that only differ by rotation or mirroring, how many non-isomorphic ways a convex polygon with $n + 2$ sides can be cut into triangles do we get then?

I currently got: $(1),1,1,3,4$ for $n=1$ to $5$, but I'm unsure how to count the triangle ($n=1$) and if I got all cases for the heptagon ($n=5$).

Answer 1

This type of problem (counting orbits of objects under some symmetry group$~G$, here the dihedral group associated to the $(n+2)$-gon) can be handled using Burnside's lemma, which says that the number of orbits is equal to the average over all group elements $g\in G$ of the number of objects fixed by$~g$. You already know the number of objects (triangulations) fixed by the identity element, namely all $C_n$ of them. The remaining group elements can be partitioned into conjugacy classes since the number of objects fixed by$~g$ is constant as $g$ varies over a conjugacy class. Only a few conjugacy classes will admit any fixed objects at all, which makes counting this way feasible.

To simplify put $m=n+2$, so the we are considering triangualtions of an $m$-gon, and $G=\operatorname{Dih}_m$, the dihedral group of order$~2m$. Among the rotations we need only consider those of order $2$ or $3$, if they exist, since the center of the $m$-gon must either be on an edge of the triangulation or in the interior of a triangle, and that edge/triangle alone limits the possible rotational symmetry of the triangulation to be at most twofold respectively threefold. The reflections in$~G$ form either one or two conjugacy classes (when $m$ is odd respectively even). When $m$ is even, the reflections$~g$ whose axis does not pass through any vertices (but rather through two midpoints of sides) do not admit any triangulations fixed by$~g$, since for either of the sides cut by the axis of the reflection, the third corner of the triangle on that side would have to be a $g$-fixed vertex, which doesn't exist. By the same reasoning, if $m$ is odd, any triangulation fixed by a reflection must contain the (isosceles) triangle defined by the side and the vertex on the axis of the reflection.

Consider the rotation$~z$ of order$~2$, which occurs in$~G$ when $m$ is even. Any triangulation fixed by it must contain exactly one of the $m/2$ diagonals that pass through the center of the $m$-gon. Once this diagonal is chosen, a $z$-symmetric triangulation is determined by a triangulation of one of the two $(m/2+1)$-gons into which the $m$-gon is cut, as the other one must be its image by$~z$; this can be done in $C_{m/2-1}$ different ways. So whenever $m$ is even, $z$ contributes $\frac m2C_{m/2-1}$ triangulations fixed by it. Similarly, whenever $m$ is divisible by$~3$ there are two rotations$~\rho$ of order$~3$; each one fixes the same set of triangulations, but we must not forget to count them twice. A $\rho$-fixed triangulation must contain exactly one of the $m/3$ equilateral triangles that share their center with the $m$-gon. Each such triangle leaves three $(m/3+1)$-gons to be triangulated, but after this has been done for one of them in one of the $C_{m/3-1}$ possible ways, the remaining ones are determined by the required $\rho$-symmetry. So the contribution of $3$-fold symmetry when it exist is $2\frac m3C_{m/3-1}$.

We are left with the reflections. If $m$ is odd there are $m$ conjugate reflections, for each of which as we have seen the axis determines a triangle that must occur in any triangulation fixed by it, and there remain two $(m+1)/2$-gons, of which as before it will suffice to triangulate one, in one of $C_{(m-3)/2}$ possible ways. This contributes $mC_{(m-3)/2}$ whenever $m$ is odd. The final case, with $m$ even and $\sigma$ is one of the $\frac m2$ reflections whose axis passes through two opposite vertices, is the most subtle one. On one hand the axis itself might occur in the triangulation, and this possibility accounts (for all such reflections combined) for $\frac m2C_{m/2-1}$ $\sigma$-fixed triangulations (the same number as contributed by $z$ alone). However the axis of reflection need not occur in the triangulation: it may run through the interior of triangles, and since every edge of the triangulation that meets the axis must be perpendicular to it one sees that there must be exactly two such (isosceles) triangles that cover the symmetry axis. To find the contribution of such symmetric configuration one might sum over all possibilities for this pair of triangles and discover that the result can be simplified by the quadratic recurrence satisfied by the Catalan numbers; one can however jump to the resulting expression by the following trick: the quadrilateral formed by the two triangles covering the axis can be re-triangulated in one other way, and the result is a $\sigma$-fixed triangulation in which the axis does occur. The correspondence is bijective, so we get one more contribution of $\frac m2C_{m/2-1}$.

We summarise, using the Iverson bracket $[d\mid n]$ to denote $1$ when $d$ divides $n$ and $0$ otherwise. The number of configurations for $m=n+2$ is given by $$ f(m)= \frac1{2m}\left(C_{m-2} +[2\mid m]\,\frac{3m}2C_{m/2-1} +[2\not\mid m]\,mC_{(m-3)/2} +[3\mid m]\,\frac{2m}3C_{m/3-1}\right) $$ If you like you can combine the middle two terms in parentheses by $\Bigl(1+\frac{[2\mid m]}2\Bigr)\,mC_{\lfloor m/2\rfloor-1}$ for a somewhat more compact formula. The first few values of this expression, as function of $n$, are $$\scriptstyle \begin{matrix} n & 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \\ \hline f(n+2)&1&1&1&3&4&12&27&82&228&733&2282&7528&24834&83898&285357&983244 \end{matrix} $$

Once we've got these numbers, it is of course easy to look this up in OEIS. Indeed it is sequence A000207 whose title is "Number of inequivalent ways of dissecting a regular $(n+2)$-gon into $n$ triangles by $n-1$ non-intersecting diagonals under rotations and reflections; also the number of planar $2$-trees".

Answer 2

The dividing lines make up a "cut graph" (a made up name) having $n-1$ edges. So if two cutups have nonisomorphic cut graphs, they cannot be isomorphic on rotation or reflection. For the case of the heptagon, $n=5$, these graphs have $4$ edges. There are at least $5$ of these graphs which arise for the heptagon. Number the heptagon vertices $1,\cdots,7$ cyclically for descriptions. CORRECTION there are at least 4.

A) One vertex with four edges going out from it (a tree): connect $1$ to each of $3,4,5,6.$

B) One vertex with three edges going out of it, and one of the other ends of one of those edges having another edge going out from it: connect $1$ to each of $3,4,5$ and connect $5$ to $7.$

(redundant case, so drop this) [this next case is another version of the one above, with an isomorphic cut graph] One vertex with two edges going out, with one of the other ends of one of those having two more edges going out: connect $1$ to each of $3,4$ and connect $4$ to each of $6,7.$

C) One vertex having three edges going out of it, and two other ends of these edges connected by an edge (This is the only non-tree graph I found for the heptagon): connect $1$ to each of $3,4,6$ and connect $4$ to $6$.

D) One vertex having two edges going out of it, with each other vertex of these edges having another edge going out of it (so this graph is like a W inside the heptagon): connect $1$ to $4,5$, connect $4$ to $2$, and connect $5$ to $7$.

This gives a total of (at least) $4$ distinct types of cutups for the heptagon. In general there may be a way to count the number of distinct cut graphs which may come up. However for large $n$ it doesn't seem clear (to me) that a single type of cut graph gives only one isomorphism class of cut ups (under reflection/rotation).

ADDED: a note about the (now corrected) count of 4 ways for the heptagon): I previously had miscounted and obtained five ways for the heptagon, but now agree with the OP that there are only four.

Note that the cut diagrams for cases (A) and (D) have a reflective symmetry, while those for (B) and (C) do not have any symmetries, rotational or reflective. So cases A,D contribute $14/2=7$ each to the total count (there being $14$ elements in the dihedral group for the heptagon), while cases B,C each contribute 14 to the count. This gives the required $7+14+14+7=42=C_5$ total ways to cut up the heptagon.

Answer 3

A good general approach to problems of this sort is Burnside's Lemma, which for triangulations of the regular $(n+2)$-gon amounts to: the number of non-isomorphic triangulations equals $S/(2n+4)$ where $S$ is the sum, over all the symmetries in the dihedral group, of the number of triangulations fixed by that symmetry.

It's simplest when $n+2$ is prime, then then there are only $3$ types of symmetries. For example, with $n = 5$, there are (1) the identity symmetry, which fixes all 42 triangulations, (2) Six non-trivial rotations, each of which is a single 7-cycle on the vertices and hence can't fix any triangulations, and (3) Seven reflections, each of which fixes $2$ triangulations (by sketching a heptagon, a reflection line, and drawing lines between vertices). So $S = 1(42) + 6(0) + 7(2) = 56$ and the number of orbits of the action (i.e. the number of non-isomorphic triangulations) is $56/14 = 4$.

I did it for $n = 7$, in which case the 9-gon has two different non-trival types of rotations [rotations by $3/9$ and $6/9$ have a different structure than those by $j/9$ for $(j,9)=1$ and I got

$S = 1(429) + 6(0) + 2(6) + 9(3) = 468$, and so the number of orbits is $468 / 18 = 26$.

I looked up the $7$th Catalan number and got the other triangulation counts (the 6 triangulations fixed by rotation by $3/9$ and the $3$ fixed by a reflection) by drawing so there might well be a mistake in there.

It gets more complicated when $n+2$ is even, for then there are two different types of reflections in the dihedral group, and when $n+2$ is highly composite, for then there are yet more types of rotations.