Numero di Catalan

Da Wikipedia, l'enciclopedia libera.

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[1]. I primi 25 numeri di Catalan 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[modifica | modifica wikitesto]

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[2]. 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à[modifica | modifica wikitesto]

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:
Catalan-Hexagons-example.svg
  • 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:
Catalan number binary tree example.png
  • 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:
Catalan number 4x4 grid example.svg
  • C_n è il numero di possibili tassellazioni di una scala di n gradini con rettangoli. Ad esempio, per n=5 si ottiene
Catalan stairsteps 4.svg

Cenni storici[modifica | modifica wikitesto]

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 | modifica wikitesto]

  1. ^ (EN) Sequenza A000108 in On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
  2. ^ 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 | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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