Où apparaissent les nombres catalans ?
-Nombre de psp avec un nombre donné de paires de parenthèses
-Nombre d'arbres binaires avec un nombre donné de feuilles
-Nombre de chemins du coin inférieur gauche au coin supérieur droit dans le carré n * n qui ne touchent pas la diagonale
-Nombre de divisions du n-gon en triangles
Comment compter ?1) Formule pour le nième nombre catalan :
2)
•Prenons un PSS de longueur 2n
•Il commence évidemment par une accolade ouvrante
•Donc, disons P = (A)B, où A et B – aussi psp (de plus, A et B peuvent être vides)
•Si la longueur de A = 2k, alors la séquence A peut être composée de Ck manières
•Alors la longueur de B = 2(n – k - 1) et B peut être composé de Cn-k-1 manières
•Nous voyons la formule pour dp : Cn = sum(Ck * Cn-k-1) pour tout k <
Les matériaux utilisés: