Numero di Catalan

In matematica, i numeri di Catalan formano una successione di numeri naturali utile in molti calcoli combinatori. Prendono il nome dal matematico belga Eugène Charles Catalan.

L'$n$-esimo numero di Catalan $C_n$ può essere definito facendo uso dei coefficienti binomiali nel modo seguente:

$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!n!}\qquad\mbox{ per }n \geqslant 1$

La successione dei numeri di Catalan è registrata nella OEIS con la sigla A000108. I primi 25 numeri di Catalan sono:

1,   1, 2, 5, 14,   42, 132, 429, 1430, 4862, 16796 (=C₁₀),

58786, 208012, 742900, 2674440,   9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420 (=C₂₀),

24466267020, 91482563640, 343059613650, 1289904147324 (=C₂₄)

Definizioni alternative

I numeri di Catalan possono essere definiti in modo ricorsivo imponendo $C_0 = 1$ e

$C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}\quad\mbox{ per }n\ge 1.$

Questa relazione di ricorrenza è stata notata per la prima volta nel 1758 dal de Segner. In particolare, la relazione mostra che i numeri di Catalan sono effettivamente dei numeri interi.

Una espressione alternativa è la seguente:

$C_n = {2n\choose n} - {2n\choose n-1} \qquad\mbox{ per }n\ge 1.$

Proprietà

Molti problemi combinatori hanno come soluzione i numeri di Catalan. Ad esempio:

• $C_n$ è il numero di modi in cui un poligono convesso con $n+2$ lati può essere suddiviso in triangoli. Ad esempio, per $n=4$ il poligono è un esagono e i modi sono effettivamente 14:

• $C_n$ è il numero delle parole di Dyck di lunghezza $2n$. Una parola di Dyck è composta di $n$ lettere $X$ e $n$ lettere $Y$, tale che ogni segmento iniziale non contenga più $Y$ che $X$. Ad esempio, le parole di Dyck con 6 lettere sono effettivamente $C_3 = 5$:

XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

• $C_n$ è il numero di modi in cui è possibile inserire $n$ coppie di parentesi in un prodotto di $n+1$ fattori. Ad esempio, per $n=3$ si ottiene

$(((ab)c)d) \quad ((a(bc))d) \quad((ab)(cd)) \quad (a((bc)d)) \quad (a(b(cd)))$

• $C_n$ è il numero di alberi binari pieni con $n$ nodi padre. Qui è mostrato il caso $n=3$:

• $C_n$ è il numero delle permutazioni degli interi 1, 2, ... , n ordinabili mediante pila;
• $C_n$ è il numero dei cammini in una griglia $n\times n$ che collegano due vertici opposti senza mai attraversare la diagonale. I cammini per $n=4$ sono effettivamente 14:

• $C_n$ è il numero di possibili tassellazioni di una scala di $n$ gradini con rettangoli. Ad esempio, per $n=5$ si ottiene

Cenni storici

Il nome di questi numeri è stato scelto in onore del matematico belga Eugène Charles Catalan (1814-1884) che li aveva studiati elegantemente intorno al 1838. La successione di questi numeri però già nel XVIII secolo era stata individuata dal matematico tedesco-ungherese Jan Andrej Segner (1704-1777) ed era stata studiata da Eulero. Inoltre, contemporaneamente a Catalan, era stata studiata dal matematico francese Jacques Binet (1786-1857). Il fatto che l'n-esimo numero di Catalan corrisponda al numero delle parole di Dyck aventi lunghezza 2n è stato trovato da Désiré André nel 1887.

Bibliografia

• John Horton Conway, Richard Kenneth Guy (1996): The Book of Numbers, Springer-Verlag. (pp. 96-106)
• Richard Peter Stanley (1999): Enumerative Combinatorics, Vol. 2. Cambridge University Press. (pp. 219-229)

Voci correlate

• Eugène Charles Catalan

Altri progetti

• Commons

• Commons contiene file multimediali su Numero di Catalan

Collegamenti esterni

• (EN) Voce in MathWorld
• (EN) Pagina di MacTutor

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica