¿Dónde aparecen los números catalanes?
-Número de psp con un número determinado de pares de corchetes
-Número de árboles binarios con un número determinado de hojas
-Número de caminos desde la esquina inferior izquierda hasta la esquina superior derecha en el cuadrado n * n que no tocan la diagonal
-Número de divisiones del n-ágono en triángulos
¿Cómo contar?1) Fórmula del enésimo número catalán:
2)
•Vamos a tener un PSS de longitud 2n
•Obviamente comienza con una llave de apertura
•Entonces, digamos P = (A)B, donde A y B – también psp (además, A y B pueden estar vacíos)
•Si la longitud de A = 2k, entonces la secuencia A se puede componer de Ck formas
•Entonces la longitud de B = 2(n – k - 1) y B se puede componer de formas Cn-k-1
•Vemos la fórmula para dp: Cn = sum(Ck * Cn-k-1) para todo k <
Materiales usados: