$C_{n+1}={\sum }_{i=0}^n{C}_i{C}_{n-i}$, with $C_0=1$

Given: a natural number $n$, and the set $Z_n$ of triples $(i,P,Q)$ with $i\le n$, $P\in {\mathcal{D}}_i$ and $Q\in {\mathcal{D}}_{n-i}$.

$C_m=\mid {\mathcal{D}}_m\mid$, and $C_0=1$ (The Catalan number $C_n:=\mid {\mathcal{D}}_n\mid$).

The map $\mathrm{\Theta }$ sending $(i,P,Q)\in Z_n$ to the diagonal path whose step word is $U$, the step word of $P$, $D$, the step word of $Q$, is a bijection $Z_n\to {\mathcal{D}}_{n+1}$ (Every Dyck path of semilength $n+1$ factors uniquely as $UPDQ$ with $P\in {\mathcal{D}}_i$ and $Q\in {\mathcal{D}}_{n-i}$).

${\mathcal{D}}_m$ is finite and nonempty for every $m\in \mathbb{N}$ (${\mathcal{D}}_n$ is a finite set).

If $I$ is finite and $(A_i{)}_{i\in I}$ are pairwise disjoint finite sets, then ${\bigcup }_{i\in I}{A}_i$ is finite with $\mid {\bigcup }_{i\in I}{A}_i\mid ={\sum }_{i\in I}\mid A_i\mid$ (The sum rule: a finite disjoint union is finite with $\mid A\cup B\mid =\mid A\mid +\mid B\mid$ and $\mid {\bigcup }_{i\in I}{A}_i\mid ={\sum }_{i\in I}\mid A_i\mid$, and a sum over a finite index set splits along a partition, clause 2).

If $A$ and $B$ are finite then $A\times B$ is finite and $\mid A\times B\mid =\mid A\mid \cdot \mid B\mid$ (The product rule: $\mid A\times B\mid =\mid A\mid \mid B\mid$, and $\mid {\prod }_{i<m}{A}_i\mid ={\prod }_{i<m}\mid A_i\mid$, clause 1).

For a finite index set $S$ and $a:S\to \mathbb{N}$, ${\sum }_{i\in S}{a}_i$ is defined and equals ${\sum }_{k<n^{\mathrm{\prime }}}{a}_{\phi (k)}$ for any bijection $\phi :n^{\mathrm{\prime }}\to S$ with $n^{\mathrm{\prime }}=\mid S\mid$; taking $S=n^{\mathrm{\prime }}$ and the identity gives ${\sum }_{i\in n^{\mathrm{\prime }}}{a}_i={\sum }_{k<n^{\mathrm{\prime }}}{a}_k$ (The sum ${\sum }_{i\in S}{a}_i$ over a finite index set, and its product form, clause (a)).

If $A$ is finite and $f:A\to B$ is a bijection then $B$ is finite and $\mid B\mid =\mid A\mid$ (The cardinality $\mid A\mid$ of a finite set).