Scribd
Importer
126 vues2 pages

Nombre de Catalan

Le document traite des nombres de Catalan et des chemins de Dyck, en présentant des propriétés, des calculs et des relations de récurrence. Il inclut des exercices sur le calcul des nombres de Catalan pour différents indices et sur la détermination des chemins dans un plan respectant certaines conditions. Enfin, il établit une relation entre les chemins de Dyck et les nombres de Catalan, démontrant leur équivalence.

Transféré par

raniawalidi00
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
126 vues2 pages

Nombre de Catalan

Le document traite des nombres de Catalan et des chemins de Dyck, en présentant des propriétés, des calculs et des relations de récurrence. Il inclut des exercices sur le calcul des nombres de Catalan pour différents indices et sur la détermination des chemins dans un plan respectant certaines conditions. Enfin, il établit une relation entre les chemins de Dyck et les nombres de Catalan, démontrant leur équivalence.

Transféré par

raniawalidi00
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Centre Des Classes Préparatoires Mohammed 6

D’Excellence -BENGUERIR-
Nombre de catalan

Classe : MPSI4

Problème.
Partie 1 : quelques propriétés
 
1 2n
Considérons, pour tout entier naturel n, cn = n+1 · cn est appelé nombre de Catalan d’indice n.
n
1. Calculer c0 , c1 , c2 et c3 .
2(2n+1)
2. Montrer que, ∀n ∈ N, cn+1 = n+2 cn . En déduire la monotonie de (cn ).
       
2n 2n 2n 2n − 1
3. Prouver toutes les relations suivantes : ∀n ∈ N∗ , cn = n1 = − = 2
n+1 .
n+1 n n+1 n
4. Justifer que ∀n ∈ N, cn ∈ N.
5. Donner un équivalent de cn lorsque n tend vers +∞.

Partie 2 : Les chemis de Dyck


On considère dans cette partie des chemins menant dans le plan de l’origine du repère jusqu’au point de
coordonnées (n, m), en respectant les conditions suivantes : à chaque pas, on se déplace d’une unité vers la
droite, ou bien d’une unité vers le haut. On note ∆ l’ensemble des points du plan de coordonnées (x, y) situés
sous la droite d’équation y = x (c’est-à-dire tels que y ≤ x ), et on note δn,m le nombre de chemins menant de
(0, 0) à (n, m) et situés entièrement dans ∆ (autrement dit, ne traversant pas la diagonale). Un exemple avec
(n, m) = (4, 3)

1. (a) Que vaut δn,0 (pour tout entier n )? Que vaut δn,m si m > n ?
(b) Justifier que δn,n = δn,n−1 (si n ≥ 1 ) et δn,m = δn−1,m + δn,m−1 si m < n.
(c) En déduire la valeur de δn,1 (pour n ≥ 1 ) et de δn,2 (pour n ≥ 2 ).
(d) Donner la liste des δn,m pour toutes les valeurs de n et de m inférieures ou égales à 6 , en les présentant
sous forme d’un tableau de type «triangle de Pascal».

1
 
n−m+1 n+m
2. (a) Montrer par récurrence sur n que δn,m = n+1 .
n
(b) En déduire que δn,n = cn .
3. On va maintenant établir une relation de récurrence vérifiée par les nombres de Catalan. Soit P un chemin
de ∆, d’origine A(0, 0) et d’extrémité B(n, n), avec n ≥ 1. On sait qu’il y a exactement cn façons de
former P.
(a) On suppose que P ne rencontre la diagonale y = x qu’en A et B. Montrer que le nombre de façons
différentes de former le chemin P est cn−1 .
(b) On suppose que P rencontre y = x en au moins un point autre que A et B. Soit k l’abscisse minimum
(comprise entre 1 et n − 1 ) de ces points d’intersection. Pour chaque valeur de k, montrer qu’il y a
ck−1 cn−k façons de former P.
X n
(c) En déduire que pour tout n de N, on a cn+1 = ck cn−k
k=0

Vous aimerez peut-être aussi