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'${\displaystyle n}$-esimo numero di Catalan ${\displaystyle C_{n}}$ può essere definito facendo uso dei coefficienti binomiali nel modo seguente:

${\displaystyle 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

I numeri di Catalan possono essere definiti in modo ricorsivo imponendo ${\displaystyle C_{0}=1}$ e

${\displaystyle 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:

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

Proprietà

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

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

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

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

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

• ${\displaystyle C_{n}}$ è il numero di alberi binari pieni con ${\displaystyle n}$ nodi padre. Qui è mostrato il caso ${\displaystyle n=3}$:

• ${\displaystyle C_{n}}$ è il numero delle permutazioni degli interi ${\displaystyle 1,2,\ldots ,n}$ ordinabili mediante pila;
• ${\displaystyle C_{n}}$ è il numero dei cammini in una griglia ${\displaystyle n\times n}$ che collegano due vertici opposti restando sempre sotto la diagonale. I cammini per ${\displaystyle n=4}$ sono effettivamente ${\displaystyle 14}$:

• ${\displaystyle C_{n}}$ è il numero di possibili tassellazioni di una scala di ${\displaystyle n}$ gradini con ${\displaystyle n}$ rettangoli. Ad esempio, per ${\displaystyle n=4}$ 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

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

• Eugène Charles Catalan
• Parola di Dyck

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

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

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