Probl`emes de Math´ematiques Nombres de Catalan ´Enonc´e Nombres de Catalan On rappelle que si 0 ≤ p ≤ n, le symbole �n p � d´esigne le nombre de parties `a p ´el´ements dans un ensemble `a n ´el´ements. Par convention on pose �n p � = 0 si p < 0 ou p > n. Pour tout n de N, Cn = (2n)! n! (n + 1)! est appel´e nombre de Catalan d’indice n. I. G´en´eralit´es sur les nombres de Catalan 1. (a) Montrer que pour entier naturel n, on a l’´egalit´e Cn+1 = 2(2n + 1) n + 2 Cn. [ S ] (b) Donner les valeurs de Cn pour 0 ≤ n ≤ 7. [ S ] 2. Prouver les relations suivantes : (a) Cn = 1 n+1 �2n n � = 1 n � 2n n+1 � = �2n n � − � 2n n+1 � . [ S ] (b) Cn = 2 n+1 �2n−1 n � = 2 n−1 �2n−1 n+1 � = �2n−1 n � − �2n−1 n+1 � . [ S ] (c) Montrer que les Cn sont dans N, que la suite (Cn) est strictement croissante `a partir de n = 1, et en d´eduire lim n→+∞ Cn = +∞. [ S ] 3. Dans cette question, on trouve l’ordre de grandeur de Cn quand n tend vers +∞. (a) Montrer que pour tout k ≥ 1, on a : 4 �k−1 k �3/2 ≤ Ck Ck−1 ≤ 4 � k k+1 �3/2 . [ S ] (b) En d´eduire 4n−1 n√n ≤ Cn ≤ 34n−1 n√n pour n ≥ 1. [ S ] II. Un premier probl`eme de d´enombrement On va ´etudier un probl`eme de d´enombrement o`u interviennent les nombres de Catalan. On consid`ere des chemins joignant des points de N × N, et form´es de d´eplacements successifs. Les seuls d´eplacements autoris´es `a partir d’un point (n, m) sont : – Le passage de (n, m) `a (n + 1, m) (vers la droite.) – Le passage de (n, m) `a (n, m + 1) (vers le haut.) On note ∆ = {(n, m) ∈ N2, 0 ≤ m ≤ n} l’ensemble des points de N2 qui sont “sous” ou “sur” la diagonale y = x. Voici par exemple un chemin de ∆, qui va de (0, 0) `a (6, 5). Remarque : pour tous entiers naturels a et b, et moyennant une translation de vecteur (a, b), il est ´evident qu’il y a autant de chemins d’origine (0, 0) et d’extr´emit´e (n, m) qu’il y a de chemins d’origine (a, b) et d’extr´emit´e (a + n, b + m). Page 1 Jean-Michel Ferrard www.klubprepa.net c⃝EduKlub S.A. Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation individuelle et priv´ee sont interdites.