Établissement
Lycée du Pays d'Aunis (Surgères)
Année
2025-2026
Résumé
Les nombres de Catalan Cn sont définis par la formule :
Cn = 1/(n+1) * (n parmi 2n)
Ils apparaissent dans de nombreux problèmes de dénombrement.
1) Montrez que Cn compte le nombre de façons de parenthéser une expression à n+1 facteurs.
2) Montrez que Cn compte le nombre d’arbres binaires pleins à n+1 feuilles.
3) Trouvez une relation de récurrence vérifiée par Cn.
4) Défi : Montrez que les nombres de Catalan sont également liés au nombre de chemins de Dyck (chemins de longueur 2n ne passant pas au-dessus de la diagonale : on part de (0,0) et on arrive à (2n,0).
Cn = 1/(n+1) * (n parmi 2n)
Ils apparaissent dans de nombreux problèmes de dénombrement.
1) Montrez que Cn compte le nombre de façons de parenthéser une expression à n+1 facteurs.
2) Montrez que Cn compte le nombre d’arbres binaires pleins à n+1 feuilles.
3) Trouvez une relation de récurrence vérifiée par Cn.
4) Défi : Montrez que les nombres de Catalan sont également liés au nombre de chemins de Dyck (chemins de longueur 2n ne passant pas au-dessus de la diagonale : on part de (0,0) et on arrive à (2n,0).
Ateliers qui présentent ce sujet
Type de présentation au congrès
Exposé
À présenter
aux lycéens