Calcolatore di Numeri di Catalan
Calcola i numeri di Catalan con applicazioni in combinatoria e alberi binari
Inserisci un numero intero non negativo (da 0 a 30)
Risultati
Inserisci i valori e clicca su Calcola per vedere il risultato.
Teoria e Formula
Numeri di Catalan
I numeri di Catalan formano una sequenza di numeri naturali che si presentano in vari problemi di conteggio, spesso coinvolgendo oggetti definiti ricorsivamente. L'n-esimo numero di Catalan conta il numero di espressioni contenenti n coppie di parentesi correttamente abbinate.
Formule
\(C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}\)
\(C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}\)
La prima formula utilizza i coefficienti binomiali, mentre la seconda è una definizione ricorsiva
Applicazioni
- Numero di modi per abbinare correttamente n coppie di parentesi
- Numero di diversi alberi binari con n+1 foglie
- Numero di cammini da (0,0) a (n,n) che non attraversano la diagonale
- Numero di modi per triangolare un poligono convesso con n+2 lati
- Numero di modi per collegare 2n punti su un cerchio con n corde non incrociate
Primi numeri di Catalan
I primi numeri di Catalan sono: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796...
Esempio
Calcola C₃ (numero di modi per abbinare 3 coppie di parentesi):
\(C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \cdot 20 = 5\)