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
Additional Information
- Douglas Bowman
- Affiliation: Department of Mathematical Sciences, Northern Illinois University, DeKalb, Illinois 60115
- Email: bowman@math.niu.edu
- Alon Regev
- Affiliation: Department of Mathematical Sciences, Northern Illinois University, DeKalb, Illinois 60115
- Email: regev@math.niu.edu
- Received by editor(s): February 17, 2011
- Received by editor(s) in revised form: July 17, 2011
- Published electronically: July 12, 2012
- Communicated by: Jim Haglund
- © Copyright 2012
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 141 (2013), 779-789
- MSC (2010): Primary 05C30, 32B25, 52B11, 52B15, 52B05, 05E18
- DOI: https://doi.org/10.1090/S0002-9939-2012-11626-0
- MathSciNet review: 3003672