How to show that the number of sequences of the form ($a_1$, $a_2$, …, $a_n$) when $\sum_{k=1}^i(a_k) \geq i$ for each $i$ and $\sum_{k=1}^n(a_k)$ = $n$ is equal to the corresponding Catalan number ($C_n$)?
In my proof that the number of terms of the decomposition of a polynomial of the form
$\prod_{i=1}^n(x_1 + … + x_i)$ is $C_n$,
I went so far as to be able to show that the number of these terms is equal to the number of sequences ($a_1$, $a_2$, …, $a_n$) mentioned above
And then I can't find a pattern
Ideas are also accepted to prove my original goal. I will be grateful to everyone
Best Answer
Write "$X$" $a_i$ times and one "$Y$" after it for all $i$ from $1$ to $n$. Here are Dyck words, the number of which corresponds to the $C_n$
For example, the set $(2, 0, 1)$ will correspond to two "$X$", one "$Y$", zero "$X$", one "$Y$", one "$X$", one "$Y$", that is "$XXYYXY$"