Catalan numbers are an interesting sequence of integers, among many applications they have in counting problems they enumerate the celebrated Bernoulli excursions.
The n-th Catalan number can be obtained using the Catalan triangle:
Each element in the triangle is obtained taking what he has at his
left plus what he has on the top.
Each column of the triangle has a nice counting property, it enumerates the subset
of Bernoulli excursions touching the x-axis a fixed number of times.
The leftmost column counts for the single Bernoulli excursion touching the maximum number of times the x-axis whilst the rightmost column enumerates the excursions with minimum number of times. The inner columns enumerate all the intermediate cases …
next post for a picture to show this in practice 🙂