# 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …

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:

n\k_____0_______1_______2_______3_______4_______5_______6_______7
0_______1
1_______1_______1
2_______1_______2_______2
3_______1_______3_______5_______5
4_______1_______4_______9_______14______14
5_______1_______5_______14______28______42______42
6_______1_______6_______20______48______90______132_____132
7_______1_______7_______27______75______165_____297_____429_____429
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 🙂

Annunci

## One thought on “1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …”

1. Pribislav Hippe ha detto:

Please note that Bernoulli principle is at the base of airbrush painting. 🙂

Mi piace