Numero di Catalan

elemento di una successione di numeri naturali utile in molti calcoli combinatori

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 alternativeModifica

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àModifica

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  :
  •   è 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  :
  •   è 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  :
  •   è il numero di possibili tassellazioni di una scala di   gradini con   rettangoli. Ad esempio, per   si ottiene

StoriaModifica

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.

NoteModifica

  1. ^ (EN) Sequenza A000108, su 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

BibliografiaModifica

Voci correlateModifica

Altri progettiModifica

Collegamenti esterniModifica

Controllo di autoritàThesaurus BNCF 61477 · LCCN (ENsh2008005833 · GND (DE1072323532 · J9U (ENHE987007561759805171 (topic)
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica