Counting symmetry classes of dissections of a convex regular polygon. (English) Zbl 1301.52030
Summary: This paper proves explicit formulas for the number of dissections of a convex regular polygon modulo the action of the cyclic and dihedral groups. The formulas are obtained by making use of the Cauchy-Frobenius Lemma as well as bijections between rotationally symmetric dissections and simpler classes of dissections. A number of special cases of these formulas are studied. Consequently, some known enumerations are recovered and several new ones are provided.
MSC:
| 52B45 | Dissections and valuations (Hilbert’s third problem, etc.) |
| 05C30 | Enumeration in graph theory |
| 32B25 | Triangulation and topological properties of semi-analytic and subanalytic sets, and related questions |
| 52B11 | \(n\)-dimensional polytopes |
| 52B15 | Symmetry properties of polytopes |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 05E18 | Group actions on combinatorial structures |
Software:
OEISOnline Encyclopedia of Integer Sequences:
Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).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 (unlabeled) maximal outerplanar graphs on n+2 vertices.
Number of one-sided triangulations of the disk; or flexagons of order n; or unlabeled plane trivalent trees (n-2 internal vertices, all of degree 3 and hence n leaves).
Number of nonequivalent dissections of an n-gon into 3 polygons by nonintersecting diagonals up to rotation and reflection.
Number of (n - 6)-dissections of an n-gon (equivalently, the number of three-dimensional faces of the (n-3)-dimensional associahedron) modulo the cyclic action.
References:
| [1] | Aigner, M., A Course in Enumeration (2007), Springer · Zbl 1123.05001 |
| [2] | Bowman, D.; Regev, A., Counting equivalence classes of vertex pairs modulo the dihedral action on the associahedron, Proc. Amer. Math. Soc., 141, 779-789 (2013) · Zbl 1259.05080 |
| [3] | Brown, W. G., Enumeration of triangulations of the disk, Proc. Lond. Math. Soc. (3), 14, 746-768 (1964) · Zbl 0134.19503 |
| [4] | Burnside, W., Theory of Groups of Finite Order, 191 (1911), Cambridge University Press: Cambridge University Press Cambridge · JFM 26.0170.01 |
| [5] | Catalan, E., Sur les nombres de Segner, Rend. Circ. Mat. Palermo, 1, 190-201 (1887) · JFM 19.0170.03 |
| [6] | Cayley, A., On the partitions of a polygon, Proc. Lond. Math. Soc., 22, 237-262 (1890-1891) · JFM 23.0541.01 |
| [7] | Ceballos, C.; Santos, F.; Ziegler, G. M., Many non-equivalent realizations of the associahedron (2011) · Zbl 1389.52013 |
| [8] | Devadoss, S. L.; Read, R. C., Cellular structures determined by polygons and trees, Ann. Comb., 5, 71-98 (2001) · Zbl 0983.05008 |
| [9] | Larcombe, P. J.; French, D. R., The Catalan number \(k\)-fold self-convolution identity: the original formulation, J. Combin. Math. Combin. Comput., 46, 191-204 (2003) · Zbl 1035.05007 |
| [10] | Lee, C., The associahedron and triangulations of the \(n\)-gon, European J. Combin., 10, 6, 551-560 (1989) · Zbl 0682.52004 |
| [11] | Lisonek, P., Closed forms for the number of polygon dissections, J. Symbolic Comput., 20, 595-601 (1995) · Zbl 0848.05004 |
| [12] | Lisonek, P., Combinatorial families enumerated by quasi-polynomials, J. Combin. Theory Ser. A, 114, 619-630 (2007) · Zbl 1117.05005 |
| [13] | Moon, J. W.; Moser, L., Triangular dissections of \(n\)-gons, Canad. Math. Bull., 6, 175-178 (1963) · Zbl 0118.25701 |
| [14] | Przytycki, J. H.; Sikora, A., Polygon dissections and Euler, Fuss, Kirkman and Cayley numbers, J. Combin. Theory Ser. A, 92, 1, 68-76 (2000) · Zbl 0959.05004 |
| [15] | Read, R. C., On general dissections of a polygon, Aequationes Math., 18, 370-388 (1978) · Zbl 0396.05028 |
| [16] | Sloane, N. J.A., The on-line encyclopedia of integer sequences · Zbl 1044.11108 |
| [17] | Torkildsen, H., Counting cluster-tilted algebras of type \(A_n\), Int. Electron. J. Algebra, 4, 149-158 (2008) · Zbl 1163.16011 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
