Counting equivalence classes of vertex pairs modulo the dihedral action on the associahedron

Bowman, Douglas; Regev, Alon

doi:10.1090/S0002-9939-2012-11626-0

Counting equivalence classes of vertex pairs modulo the dihedral action on the associahedron
HTML articles powered by AMS MathViewer

by Douglas Bowman and Alon Regev PDF

Proc. Amer. Math. Soc. 141 (2013), 779-789 Request permission

Abstract:

This paper proves explicit formulae for the number of edges, $2$-sets and diagonals in the associahedron of dimension $n$ modulo the action of the dihedral group. A generating function for the number of $k$-sets modulo this action, as well as a formula for the cycle index, is given. A table of values is also provided.

References

Lewis Bowen, Jesús A. De Loera, Mike Develin, and Francisco Santos, The Gromov norm of the product of two surfaces, Topology 44 (2005), no. 2, 321–339. MR 2114710, DOI 10.1016/j.top.2004.10.007
William G. Brown, Enumeration of triangulations of the disk, Proc. London Math. Soc. (3) 14 (1964), 746–768. MR 168485, DOI 10.1112/plms/s3-14.4.746
William G. Brown, Historical Note on a Recurrent Combinatorial Problem, Amer. Math. Monthly 72 (1965), no. 9, 973–977. MR 1533479, DOI 10.2307/2313332
W. Burnside, Theory of Groups of Finite Order, 2nd ed., Cambridge University Press, Cambridge, 1911, p. 191.
Jesús A. De Loera, Jörg Rambau, and Francisco Santos, Triangulations, Algorithms and Computation in Mathematics, vol. 25, Springer-Verlag, Berlin, 2010. Structures for algorithms and applications. MR 2743368, DOI 10.1007/978-3-642-12971-1
Frank Harary and Edgar M. Palmer, Graphical enumeration, Academic Press, New York-London, 1973. MR 0357214
Danièle Huguet and Dov Tamari, La structure polyédrale des complexes de parenthésages, J. Combin. Inform. System Sci. 3 (1978), no. 2, 69–81 (French). MR 538214
Carl W. Lee, The associahedron and triangulations of the $n$-gon, European J. Combin. 10 (1989), no. 6, 551–560. MR 1022776, DOI 10.1016/S0195-6698(89)80072-1
Petr Lisoněk, Closed forms for the number of polygon dissections, J. Symbolic Comput. 20 (1995), no. 5-6, 595–601. Symbolic computation in combinatorics $\Delta _1$ (Ithaca, NY, 1993). MR 1395415, DOI 10.1006/jsco.1995.1066
J. W. Moon and L. Moser, Triangular dissections of $n$-gons, Canad. Math. Bull. 6 (1963), 175–178. MR 154821, DOI 10.4153/CMB-1963-017-0
G. Pòlya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145–254.
Ronald C. Read, On general dissections of a polygon, Aequationes Math. 18 (1978), no. 3, 370–388. MR 522523, DOI 10.1007/BF01818581
Daniel D. Sleator, Robert E. Tarjan, and William P. Thurston, Rotation distance, triangulations, and hyperbolic geometry, J. Amer. Math. Soc. 1 (1988), no. 3, 647–681. MR 928904, DOI 10.1090/S0894-0347-1988-0928904-4
Herbert S. Wilf, generatingfunctionology, 2nd ed., Academic Press, Inc., Boston, MA, 1994. MR 1277813