✦ LIBER ✦

Ears of triangulations and Catalan numbers

✍ Scribed by F. Hurtado; M. Noy

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 232 KB
Volume: 149
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00331-c

No coin nor oath required. For personal study only.

✦ Synopsis

It is known that a convex polygon of n sides admits C.-2 triangulations, where C, is a Catalan number. We classify these triangulations (considered as outerplanar graphs) according to their dual trees, and prove the following formula for the number of triangulations of a convex n-gon whose dual tree has exactly k leaves:

The proof is bijective and provides a recursive formula for the Catalan numbers similar to, but different from, a classical identity of Touchard. An averaging argument allows one to deduce Touchard's formula from ours.

📜 SIMILAR VOLUMES

Catalan-like Numbers and Determinants

✍ Martin Aigner 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 190 KB

A class of numbers, called Catalan-like numbers, are introduced which unify many well-known counting coefficients, such as the Catalan numbers, the Motzkin numbers, the middle binomial coefficients, the hexagonal numbers, and many more. Generating functions, recursions and determinants of Hankel mat

Some more properties of Catalan numbers

✍ Elena Barcucci; M.Cecilia Verri 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 492 KB

Prime and prime power divisibility of Ca

Prime and prime power divisibility of Catalan numbers

✍ Ronald Alter; K.K Kubota 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 549 KB

Generating trees and the Catalan and Sch

Generating trees and the Catalan and Schröder numbers

✍ Julian West 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 1015 KB

Catalan numbers in process synthesis

✍ Mahnoosh Shoaei; J. T. Sommerfeld 📂 Article 📅 1986 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 194 KB

Congruences for Catalan and Motzkin numb

Congruences for Catalan and Motzkin numbers and related sequences

✍ Emeric Deutsch; Bruce E. Sagan 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 238 KB

We prove various congruences for Catalan and Motzkin numbers as well as related sequences. The common thread is that all these sequences can be expressed in terms of binomial coefficients. Our techniques are combinatorial and algebraic: group actions, induction, and Lucas' congruence for binomial co