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!}},\quad {\text{ per }}n\geqslant 0.

La successione dei numeri di Catalan è registrata nella OEIS con la sigla A000108^[1]. 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 modifica

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 {\text{ per }}n\geq 1.

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:

C_{n}={2n \choose n}-{2n \choose n-1},\quad {\text{ per }}n\geq 1.

Proprietà modifica

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 $C_{4}=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,\ldots ,n$ ordinabili mediante pila;
$C_{n}$ è il numero dei cammini in una griglia $n\times n$ che collegano due vertici opposti restando sempre sotto la diagonale. I cammini per $n=4$ sono effettivamente $14$ :

$C_{n}$ è il numero di possibili tassellazioni di una scala di $n$ gradini con $n$ rettangoli. Ad esempio, per $n=4$ si ottiene

Storia modifica

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 modifica

^ (EN) Sequenza A000108, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
^ A. de Segner, Enumeratio modorum, quibus figurae planae rectilineae per diagonales dividuntur in triangula. Novi commentarii academiae scientiarum Petropolitanae 7 (1758/59) 203–209

Bibliografia modifica

(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.