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, …

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...