Dove ricorrono i numeri catalani?
-Numero di psp con un determinato numero di coppie di parentesi
-Numero di alberi binari con un determinato numero di foglie
-Numero di percorsi dall'angolo in basso a sinistra all'angolo in alto a destra nel quadrato n * n che non toccano la diagonale
-Numero di divisioni di n-gon in triangoli
Come contare?1) Formula per l'ennesimo numero catalano:
2)
•Otteniamo un PSS di lunghezza 2n
•Ovviamente inizia con una parentesi graffa aperta
•Quindi, diciamo P = (A)B, dove A e B – anche psp (inoltre, A e B possono essere vuoti)
•Se la lunghezza di A = 2k, allora la sequenza A può essere composta nei modi Ck
•Allora la lunghezza di B = 2(n – k - 1) e B può essere composta nei modi Cn-k-1
•Vediamo la formula per dp: Cn = sum(Ck * Cn-k-1) per tutti i k <
Materiali usati: