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'-esimo numero di Catalan può essere definito facendo uso dei coefficienti binomiali nel modo seguente:
La successione dei numeri di Catalan è registrata nella OEIS con la sigla A000108[1]. I primi 25 numeri di Catalan sono:
Definizioni alternative
I numeri di Catalan possono essere definiti in modo ricorsivo imponendo e
Questa relazione di ricorrenza è stata notata per la prima volta nel 1758 dal de Segner[2]. In particolare, la relazione mostra che i numeri di Catalan sono effettivamente dei numeri interi.
Un'espressione alternativa è la seguente:
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. Ad esempio, per
il poligono è un esagono e i modi sono effettivamente
:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Catalan-Hexagons-example.svg/400px-Catalan-Hexagons-example.svg.png)
è 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
:
è 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
:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/01/Catalan_number_binary_tree_example.png/400px-Catalan_number_binary_tree_example.png)
è 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
:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f4/Catalan_number_4x4_grid_example.svg/500px-Catalan_number_4x4_grid_example.svg.png)
è il numero di possibili tassellazioni di una scala di
gradini con
rettangoli. Ad esempio, per
si ottiene
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/63/Catalan_stairsteps_4.svg/500px-Catalan_stairsteps_4.svg.png)
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
- (EN) John Horton Conway, Richard Kenneth Guy, The Book of Numbers, Springer-Verlag, 1996, pp. 96-106.
- (EN) Richard Peter Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, 1999, pp. 219-229.
- Giuseppe Fera e Giorgio Tescaro, I numeri di Catalan, in Archimede, luglio/settembre 2007, pp. 124-132.
Voci correlate
Altri progetti
Wikimedia Commons contiene immagini o altri file sui numeri di Catalan
Collegamenti esterni
- (EN) Eric W. Weisstein, Numero di Catalan, su MathWorld, Wolfram Research.
- (EN) Catalan numbers su MacTutor
Controllo di autorità | Thesaurus BNCF 61477 · LCCN (EN) sh2008005833 · GND (DE) 1072323532 · J9U (EN, HE) 987007561759805171 |
---|