Onde ocorrem os números catalães?
-Número de psp com um determinado número de pares de colchetes
-Número de árvores binárias com determinado número de folhas
-Número de caminhos do canto inferior esquerdo ao canto superior direito no quadrado n * n que não tocam a diagonal
-Número de divisões do n-gon em triângulos
Como contar?1) Fórmula para o enésimo número catalão:
2)
•Vamos ter um PSS de comprimento 2n
•Obviamente começa com uma chave de abertura
•Então, digamos P = (A)B, onde A e B – também psp (além disso, A e B podem estar vazios)
•Se o comprimento de A = 2k, então a sequência A pode ser composta de formas Ck
•Então o comprimento de B = 2(n – k - 1) e B pode ser composto de maneiras Cn-k-1
•Vemos a fórmula para dp: Cn = soma(Ck * Cn-k-1) para todo k <
Materiais utilizados: