Status: #good
Tags: #theorem

Statement

The number of valid parenthesizations of $n+1$ letters is Catalan (ie. equal to $C_n$).

Proof

Not yet covered. Note there is a naive map from valid parenthesizations to Dyck path by parsing left to right, ignoring the letters, and whenever you see a $($, you go up, and whenever you see $)$, you go down. This is not a bijection as it is not injective:

• $((xy)z)$ and $(x(yz))$ both convert to the same Dyck path: up up down down.