On the Catalan numbers

Historical remarks: The solution in terms of factorials was given by Euler [5] before Segner [11] gave the recurrence. The remark in Catalan's paper [1] is about parenthesizings of products. I don't know exactly when his name started being associated to these numbers; in 1962 they apparently still didn't have a name [15]. For matchings see [4, 9, 12]. Stanley has collected a long list [13, 14] of combinatorial interpretations; this is where I found the benzenoid example. Acknowledgements: This video was largely prompted by watching Sally Le Page's Sofa Science series, especially [2, 8]. It is heavily inspired by the work of Vi Hart, in particular [6], without which I would not know about hexaflexagons, and [7]. I thank GreeningGalaxy, Iskierka, and UmbralRaptor for providing helpful advice for this video; I thank Sally Le Page for answering a question about citations, and, of course, I thank the OEIS. Hints: 1. triangulation ↦ tree: the inner vertices of the tree are the triangles. tree ↦ parenthesizing: parse tree. parenthesizing ↦ parentheses: parenthesize only second factors and all second factors, e.g., a(b)(c) for (ab)c. See [15]. parentheses ↦ rook path: '(' ↦ right, ')' ↦ down. See [3]. 2. Count structures with n pairs and k hairpin loops (ignoring unpaired bases). Equivalently, that's n pairs of parentheses with k times "()". You'll get http://oeis.org/A001263. Adding unpaired nucleotides (one per hairpin loop, and the remaining ones wherever), get to http://oeis.org/A089741. Sum over the number of hairpin loops: http://oeis.org/A004148. 3. Count triangulations that have 3-fold symmetry, and those that have 2-fold symmetry: observe that the centre is either on an edge or inside a triangle. Use that to get http://oeis.org/A001683. Take care of mirror symmetry similarly. You'll get http://oeis.org/A000207. For flexagons, see http://flexagon.net/index.php/hexafle..., and think of the correspondance between triangulations and trees. Bonus question: both http://oeis.org/A001683 and http://oeis.org/A000207 are described as counting flexagons. What's going on here? Is there a sense in which the Catalan numbers themselves would count flexagons? (I have not looked into this; the answer may turn out to be obvious, or the question may turn out to be uninteresting). References: [1] Eugène Charles Catalan. Note sur une équation aux différences finies. Journal de Mathématiques Pures et Appliquées, 1(3):508–516, 1838. https://goo.gl/mskS1N [2] Alex Dainis and Sally Le Page. Sofa Science with Alex Dainis (BiteScized).    • Tell science through human stories - Alex ...  , 2016. [3] Henri Auguste Delannoy. Emploi de l'échiquier pour la résolution de divers problèmes de probabilité. In Compte rendu de la 18me session : congrès de Paris—1889, pages 43–52. Association française pour l'avancement des sciences, fusionnée avec l'association scientifique de France (fondée par Le Verrier en 1864), 1890. https://goo.gl/o0uWRr [4] Alfred Errera. Analysis situs : un problème d'énumération. Mémoires de la Classe des Sciences de l'Académie royale de Belgique, série 2, collection in-8°, 11(6), 1931. https://goo.gl/Mu5Hkh [5] Leonhard Euler. Letter to Christian Goldbach. http://eulerarchive.maa.org//correspo..., 1751. [6] Vi Hart. Hexaflexagon Series.    • Playlist  , 2012. [7] Vi Hart. Doodling in Math Class.    • Playlist  , 2013. [8] Vanessa Hill and Sally Le Page. Sofa Science with Vanessa Hill (BrainCraft).    • Science YouTube has a female discovery pro...  , 2016. [9] Andres J. Ruiz-Vargas and Emo Welzl. Crossing-free perfect matchings in wheel point sets. To appear. [10] Cédric Saule, Mireille Régnier, Jean-Marc Steyaert, and Alain Denise. Counting RNA Pseudoknotted Structures. Journal of Computational Biology. 18(10):1339–1351, 2011. https://goo.gl/x79iDT [11] János András Segner. Enumeratio modorum quibus figurae planae rectilineae per diagonales diuiduntur in triangula. In Novi Commentarii Academiae Scientiarum Imperialis Petropolitanae, volume 7 pro annis 1758 et 1759, pages 203–209, 1761. [12] Micha Sharir and Emo Welzl. On the number of crossing-free matchings, cycles, and partitions. SIAM Journal on Computing, 36(3):695–720, 2006. Preprint: https://goo.gl/Nha6PT [13] Richard P. Stanley. Exercises on Catalan and Related Numbers. http://www-math.mit.edu/~rstan/ec/cat..., 1998. [14] Richard P. Stanley. Catalan Addendum. http://www-math.mit.edu/~rstan/ec/cat..., 2013. [15] Dov Tamari. The algebra of bracketings and their enumeration. Nieuw Archief voor Wiskunde, 3(10):131–146, 1962. Zentralblatt: https://zbmath.org/scans/109/245.gif [16] Michael S. Waterman. Secondary Structure of Single-Stranded Nucleic Acids. Studies on foundations and combinatorics, Advances in mathematics supplementary studies, 1:167–212, 1978. https://goo.gl/KRLHBT