Module: Numéros catalans


Problem

1 /2


Nombre de numéros catalans

Theory Click to read/hide

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

Problem

Sortie N-ème nombre de catalan

Entrée
La première ligne de l'entrée contient un seul nombre N (\(1 <= N <= 20\)) .
 
Sortie
Imprimer un nombre - Nème nombre de catalan
 

 

Exemples
# Entrée Sortie
1 1 1