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'-esimo numero di Catalan può essere definito facendo uso dei coefficienti binomiali nel modo seguente:

L'insieme dei numeri di Catalan forma la successione dei numeri di Catalan i cui primi 25 termini sono:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 (=C10), 58786, 208012, 742900, 2674440,   9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420 (=C20), 24466267020, 91482563640, 343059613650, 1289904147324 (=C24).

Definizioni alternative Con pochi semplici passaggi si può verificare che

quindi, assieme a , anche

può essere presa come definizione dell'-esimo numero di Catalan.

I numeri di Catalan possono anche essere definiti in modo ricorsivo imponendo e

Questa relazione di ricorrenza è stata notata per la prima volta nel 1758 da de Segner.A. de Segner, Enumeratio modorum, quibus figurae planae rectilineae per diagonales dividuntur in triangula. Novi commentarii academiae scientiarum Petropolitanae 7 (1758/59) 203–209

In particolare, queste due relazioni mostrano che i numeri di Catalan sono effettivamente dei numeri interi.

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

è il numero di modi in cui un poligono convesso con lati può essere suddiviso in triangoli per mezzo di diagonali che non si intersecano. Ad esempio, per il poligono è un esagono e i modi sono effettivamente :

è il numero delle parole di Dyck di lunghezza . Una parola di Dyck è composta di lettere e lettere , tale che ogni segmento iniziale non contenga più che . Ad esempio, le parole di Dyck con lettere sono effettivamente : XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY. è il numero di modi in cui è possibile inserire coppie di parentesi in un prodotto di fattori. Ad esempio, per si ottiene

è il numero di alberi binari pieni con nodi padre. Qui è mostrato il caso :

è il numero delle permutazioni degli interi ordinabili mediante pila; è il numero dei cammini in una griglia che collegano due vertici opposti restando sempre sotto la diagonale. I cammini per sono effettivamente :

è il numero di possibili tassellazioni di una scala di gradini con rettangoli. Ad esempio, per si ottiene

Storia

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.

Note

Bibliografia

Voci correlate Eugène Charles Catalan Parola di Dyck

Altri progetti

Collegamenti esterni

Catalan numbers su MacTutor

Categoria:Teoria dei numeri Categoria:Combinatoria Categoria:Successioni di interi