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'-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:

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

Una espressione alternativa è la seguente:

Proprietà[modifica | modifica wikitesto]

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 :
Catalan-Hexagons-example.svg
  • è 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 :
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 senza mai attraversare la diagonale. I cammini per sono effettivamente :
Catalan number 4x4 grid example.svg
  • è il numero di possibili tassellazioni di una scala di gradini con rettangoli. Ad esempio, per 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