Numero di Catalan

Da Wikipedia, l'enciclopedia libera.

Stub Questa voce di matematica è solo un abbozzo: contribuisci a migliorarla secondo le convenzioni di Wikipedia.

Il termine generale della successione dei numeri di Catalan è definito dall'espressione

C_n := \frac{1}{n+1}{2n\choose n} \qquad\mbox{ per }n = 0, 1, 2, ... ,

oppure chiedendo che \,C_n\, fornisca il numero di modi per suddividere un poligono convesso con n+2 vertici distinguibili in triangoli aventi i vertici coincidenti con quelli del poligono.

La successione dei numeri di Catalan è registrata nella OEIS con la sigla A000108. 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)

I successivi numeri di Catalan si possono ottenere, a partire da \,C_0:= 1\,, mediante la seguente relazione di ricorrenza di Segner (1758)

\qquad C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}\quad\mbox{ per }n\ge 1 .

Questa uguaglianza garantisce che tutti i numeri della forma usata nella prima definizione sono numeri interi.

Si trovano inoltre le espressioni

C_n = {2n\choose n} - {2n\choose n-1} \qquad\mbox{ per }n\ge 1 .

Accade che i numeri di Catalan forniscono i numeri di molte decine di configurazioni discrete. Alcuni esempi di interpretazioni enumerative di Cn sono: numero delle parole di Dyck di lunghezza 2n; numero delle arborescenze binarie piene con n nodi padre; numero delle permutazioni degli interi 1, 2, ... , n ordinabili mediante pila; numero dei cammini nel primo quadrante del piano combinatorio \mathbb{N} \times \mathbb{N} costituiti da passi NE e SW che terminano nel punto \langle 2n, 0 \rangle.
Non stupisce quindi che essi si incontrano in una grande varietà di questioni di combinatoria.

[modifica] Cenni storici

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 diciottesimo 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. André nel 1887.

[modifica] Bibliografia

  • John Horton Conway, R. K. Guy (1996): The Book of Numbers, Springer-Verlag. (pp. 96-106)
  • Richard P. Stanley (1999): Enumerative Combinatorics, Vol. 2. Cambridge University Press. (pp. 219-229)

[modifica] Collegamenti esterni


Estratto da "http://it.wikipedia.org/wiki/Numero_di_Catalan"
Strumenti personali