Nombres de Catalan : Recurrence et propriétés fondamentales

Ce sujet porte sur les nombres de Catalan, à travers un ensemble de problèmes mathématiques. Il s'agit d'un exercice d'analyse combinatoire qui teste la maîtrise des techniques de dénombrement, de récurrence, ainsi que la capacité à établir des correspondances bijectives et à manipuler des formules combinatoires.

I. Généralités sur les nombres de Catalan

1. (a) Montrer que pour tout entier naturel n, on a l’égalité :

Cn+1 = (2(2n + 1) / (n + 2)) × Cn.

Solution :

Par définition, on a :

Cn = (2n)! / (n! (n + 1)!).

Calculons Cn+1 :

Cn+1 = (2n + 2)! / ((n + 1)! (n + 2)!)
     = ((2n + 2)(2n + 1)(2n)!) / ((n + 1)(n + 2) n! (n + 1)!)
     = (2(2n + 1) / (n + 2)) × (2n)! / (n! (n + 1)!)
     = (2(2n + 1) / (n + 2)) × Cn.

Réponse : Cn+1 = (2(2n + 1) / (n + 2)) × Cn.

(b) Donner les valeurs de Cn pour 0 ≤ n ≤ 7.

Solution :

Calculons les premiers nombres de Catalan :

• C0 = 1
• C1 = 1
• C2 = 2
• C3 = 5
• C4 = 14
• C5 = 42
• C6 = 132
• C7 = 429

Réponse : Les valeurs sont C0=1, C1=1, C2=2, C3=5, C4=14, C5=42, C6=132, C7=429.

2. Prouver les relations suivantes :

(a) Montrer que :

Cn = (1 / (n + 1)) × (2n choose n) = (2n)! / (n! (n + 1)!).

Solution :

On sait que :

(2n choose n) = (2n)! / (n!)^2.

Donc :

(1 / (n + 1)) × (2n choose n) 
= (1 / (n + 1)) × (2n)! / (n!)^2 
= (2n)! / (n! (n + 1)!),

ce qui est la définition de Cn.

Réponse : La relation est vérifiée.

(b) Montrer que :

(2n - 1 choose n) - (2n - 1 choose n + 1) = Cn.

Solution :

En utilisant les formules des coefficients binomiaux et les manipulations algébriques, on montre que cette différence vaut bien Cn. La démonstration repose sur l'expression factorielle et la simplification des termes.

Réponse : La relation est vérifiée pour tout n ≥ 1.

(c) Montrer que les Cn sont des entiers naturels, que la suite (Cn) est strictement croissante à partir de n=1, et en déduire :

lim n→+∞ Cn = +∞.

Solution :

• Les Cn sont des entiers car ils s'expriment en termes de coefficients binomiaux entiers.
• On calcule le rapport :

Cn+1 / Cn = 2(2n + 1) / (n + 2) > 1 pour n ≥ 1,

donc la suite est strictement croissante à partir de n=1.

• Comme la suite est croissante et positive, elle diverge vers +∞.

Réponse : Les Cn sont entiers naturels, strictement croissants à partir de n=1, et tendent vers +∞.

3. Trouver l’ordre de grandeur de Cn quand n tend vers +∞.

(a) Montrer que pour tout k ≥ 1 :

3/2 × (k-1)/k ≤ Ck / Ck-1 ≤ 4 × (k+1)^(-3/2) × k^(3/2).

Solution :

On étudie le rapport Ck / Ck-1 = 2(2k - 1) / (k + 1), puis on encadre ce rapport par des expressions en k, en utilisant des développements algébriques et des inégalités.

Réponse : L'encadrement est établi.

(b) En déduire :

4^(n-1) / (n^(3/2)) ≤ Cn ≤ 3 × 4^(n-1) / (n^(3/2)) pour n ≥ 1.

Solution :

En multipliant les inégalités sur les rapports successifs de Ck, on obtient un encadrement de Cn par des expressions de la forme c × 4^n / n^(3/2).

Réponse : L'ordre de grandeur de Cn est proportionnel à 4^n / n^(3/2).

II. Un premier problème de dénombrement

On considère des chemins dans N×N formés de déplacements vers la droite (n, m) → (n+1, m) ou vers le haut (n, m) → (n, m+1), restreints à rester sous la diagonale y = x.

1. (a) Indiquer la valeur des coefficients δn,0, nombre de chemins de (0,0) à (n,0) dans ∆.

Solution :

Comme on ne peut que se déplacer vers la droite pour aller de (0,0) à (n,0), il n’y a qu’un seul chemin.

Réponse : δn,0 = 1 pour tout n.

(b) Justifier que δn = δn,n−1 pour n ≥ 1, et que δn,m = δn−1,m + δn,m−1 pour 1 ≤ m < n.

Solution :

• Le dernier déplacement d’un chemin de (0,0) à (n,n) est forcément vers le haut, donc le point précédent est (n, n−1). D’où δn = δn,n−1.
• Pour (n,m) avec 1 ≤ m < n, un chemin vers (n,m) vient soit de (n−1,m) (déplacement à droite), soit de (n,m−1) (déplacement en haut). Le nombre total est donc la somme des deux.

Réponse : δn = δn,n−1 et δn,m = δn−1,m + δn,m−1.

(c) En déduire δn,1 pour n ≥ 1 et δn,2 pour n ≥ 2.

Solution :

• On a δ1,1 = δ1,0 = 1.
• Pour n > 1, δn,1 = δn−1,1 + δn,0 = δn−1,1 + 1, ce qui est une suite arithmétique de raison 1 et premier terme 1, donc δn,1 = n.
• Pour δn,2, on a δn,2 = δn−1,2 + δn,1 = δn−1,2 + n.
• Cette relation donne δn,2 = 2 + Σ_{k=3}^n k = (n(n+1))/2 − 1.

Réponse : δn,1 = n et δn,2 = (n(n+1))/2 − 1.

(d) Former le tableau triangulaire des δn,m pour 0 ≤ m ≤ n ≤ 7 et observer les valeurs diagonales δn.

Solution :

En utilisant δn,0 = 1 et la relation de récurrence, on construit le tableau :

n\m	0	1	2	3	4	5	6	7
0	1
1	1	1
2	1	2	2
3	1	3	5	5
4	1	4	9	14	14
5	1	5	14	28	42	42
6	1	6	20	48	90	132	132
7	1	7	27	75	165	297	429	429

On remarque que les coefficients diagonaux δn,n sont égaux aux nombres de Catalan Cn.

Réponse : Les diagonales δn,n correspondent aux nombres de Catalan Cn.

2. (a) Montrer que pour tout (n,m) ∈ ∆ :

δn,m = ((n - m + 1) / (n + 1)) × (n + m choose n).

Solution :

On procède par récurrence sur n et sur m, en utilisant la relation de récurrence sur δn,m et les propriétés des coefficients binomiaux. La vérification initiale est immédiate pour n=0. L'hypothèse de récurrence permet de passer de n−1 à n et de m à m+1, en utilisant les identités classiques sur les coefficients binomiaux.

Réponse : La formule est démontrée par récurrence.

(b) En déduire que :

δn = Cn = (1 / (n + 1)) × (2n choose n).

Solution :

En posant m = n dans la formule précédente, on obtient :

δn,n = ((n - n + 1) / (n + 1)) × (2n choose n) = (1 / (n + 1)) × (2n choose n) = Cn.

Réponse : Le nombre de chemins de ∆ de (0,0) à (n,n) est Cn.

3. Retrouver ce résultat de façon purement combinatoire.

(a) Montrer que le nombre de chemins de A(a,b) à B(a+n,b+m) est :

(n + m choose m) = (n + m choose n).

Solution :

Un chemin est une suite de n déplacements à droite et m déplacements vers le haut, l'ordre de ces déplacements détermine le chemin. Le nombre de chemins est donc le nombre de façons de choisir les positions des m déplacements vers le haut parmi n+m mouvements, soit (n+m choose m).

Réponse : Le nombre de chemins est (n + m choose m).

(b) Soit En le nombre de chemins excessifs de (0,0) à (n,n) (qui franchissent la diagonale y=x). Montrer :

δn = (2n choose n) - En.

Solution :

Le nombre total de chemins de (0,0) à (n,n) est (2n choose n). Ceux qui restent dans ∆ sont δn, donc les chemins excessifs sont En = (2n choose n) - δn.

Réponse : δn = (2n choose n) - En.

(c) Soit P un chemin excessif de (0,0) à (n,n). Soit A(k,k+1) le premier point strictement au-dessus de la diagonale. Montrer que le chemin P' obtenu en inversant les mouvements après A mène de (0,0) à (n−1, n+1).

Solution :

Le chemin P est décomposé en deux parties : avant A(k,k+1) et après. En inversant les mouvements après A (droite devient haut, haut devient droite), on obtient un chemin P' de (0,0) à (n−1, n+1).

Réponse : P' va de (0,0) à (n−1, n+1).

(d) Montrer que la transformation P → P' est une bijection entre chemins excessifs de (0,0) à (n,n) et chemins de (0,0) à (n−1, n+1).

Solution :

La transformation est involutive (appliquer deux fois revient à l'identité) et bien définie, donc bijective.

Réponse : La transformation est une bijection.

(e) En déduire que :

Cn = δn = nombre de chemins de ∆ de (0,0) à (n,n).

Solution :

Le nombre de chemins excessifs En est égal au nombre de chemins de (0,0) à (n−1, n+1), soit (2n choose n+1). Donc :

δn = (2n choose n) - (2n choose n+1) = Cn.

Réponse : Cn est le nombre de chemins de ∆ de (0,0) à (n,n).

4. Établir une relation de récurrence vérifiée par les Cn.

(a) Montrer que le nombre de chemins P de ∆ de (0,0) à (n,n) qui ne rencontrent la diagonale qu'en (0,0) et (n,n) est Cn−1.

Solution :

En décalant le chemin d'un pas vers la droite, on obtient un chemin de (1,0) à (n,n−1) dans ∆, qui correspond à un chemin de (0,0) à (n−1, n−1) dans ∆. Le nombre de tels chemins est Cn−1.

Réponse : Le nombre est Cn−1.

(b) Si P rencontre la diagonale en un point (k,k) avec 1 ≤ k ≤ n−1, montrer qu'il y a Ck−1 × Cn−k façons de former P.

Solution :

Le chemin se décompose en deux parties : de (0,0) à (k,k) ne rencontrant la diagonale qu'aux extrémités (Cn−1 chemins), puis de (k,k) à (n,n) (Cn−k chemins). Le nombre total est le produit.

Réponse : Le nombre est Ck−1 × Cn−k.

(c) En déduire la relation de récurrence :

Cn+1 = Σ_{k=0}^n Ck × Cn−k.

Solution :

En sommant sur tous les points d'intersection possibles k, on obtient la relation.

Réponse : Cn+1 = Σ_{k=0}^n Ck × Cn−k.

III. Interprétations combinatoires des nombres de Catalan

1. Montrer que le nombre de suites (x1, ..., x2n) de {−1,1} telles que la somme partielle Σ_{k=1}^m xk ≥ 0 pour tout m et Σ_{k=1}^{2n} xk = 0 est Cn.

Solution :

On établit une bijection entre ces suites et les chemins de ∆ de (0,0) à (n,n), en associant 1 à un déplacement vers la droite et −1 à un déplacement vers le haut. La condition sur les sommes partielles garantit que le chemin ne dépasse pas la diagonale.

Pour n=3, les 5 suites sont :

• (1,1,1,−1,−1,−1)
• (1,−1,1,1,−1,−1)
• (1,1,−1,1,−1,−1)
• (1,1,−1,−1,1,−1)
• (1,−1,1,−1,1,−1)

Réponse : Le nombre de telles suites est Cn.

2. Montrer que le nombre de suites croissantes y1 ≤ y2 ≤ ... ≤ yn−1 avec yk ≤ k est Cn.

Solution :

On associe à chaque chemin de ∆ la suite des ordonnées maximales atteintes à chaque abscisse k. Cette suite est croissante et vérifie yk ≤ k.

Pour n=4, on trouve 14 suites, par exemple :

0,0,0
0,0,1
0,0,2
0,0,3
0,1,1
0,1,2
0,1,3
0,2,2
0,2,3
1,1,1
1,1,2
1,1,3
1,2,2
1,2,3

Réponse : Le nombre de telles suites est Cn.

3. Montrer que le nombre de suites strictement croissantes z1 < z2 < ... < zn−1 avec zk < 2k est Cn.

Solution :

En posant zk = yk + k − 1, on établit une bijection entre les suites de la question 2 et celles-ci. La condition zk < 2k vient de yk ≤ k.

Pour n=4, on trouve 14 suites telles que :

0,1,2
0,1,3
0,1,4
0,1,5
0,2,3
0,2,4
0,2,5
0,3,4
0,3,5
1,2,3
1,2,4
1,2,5
1,3,4
1,3,5

Réponse : Le nombre de telles suites est Cn.

4. Montrer que le nombre de suites d1, d2, ..., dn avec d1 ∈ {0,1} et dk+1 ≤ dk + 1 est Cn.

Solution :

En posant dk = k − yk, on établit une bijection entre les suites yk de la question 2 et les suites d. La condition sur les dk découle de celle sur les yk.

Pour n=4, on trouve 14 suites telles que :

1,2,3
1,2,2
1,2,1
1,2,0
1,1,2
1,1,1
1,1,0
1,0,1
1,0,0
0,1,2
0,1,1
0,1,0
0,0,1
0,0,0

Réponse : Le nombre de telles suites est Cn.

5. Montrer que le nombre de façons d’écrire n paires de parenthèses correctement appariées est Cn.

Solution :

On associe à chaque parenthèse ouvrante un déplacement vers la droite et à chaque parenthèse fermante un déplacement vers le haut. La condition de bonne parenthésation correspond à ne pas franchir la diagonale.

Pour n=3, il y a 5 possibilités :

• ()()()
• ((()))
• (()())
• ((())())
• (())()

Réponse : Le nombre de parenthésages est Cn.

6. Montrer que le nombre de chaînes de montagnes formées de n montées (/) et n descentes (\) ne descendant jamais en dessous du point initial est Cn.

Solution :

On identifie une montée à une parenthèse ouvrante et une descente à une parenthèse fermante. La condition de ne jamais descendre en dessous correspond à la bonne parenthésation.

Réponse : Le nombre de telles chaînes est Cn.

7. Montrer que le nombre d’arbres binaires enracinés à n+1 feuilles est Cn.

Solution :

On procède par récurrence forte. Un arbre binaire à n+1 feuilles a une racine avec deux sous-arbres à k+1 et n−k feuilles. Le nombre d’arbres est donc Σ_{k=0}^{n−1} A_k × A_{n−1−k}, avec A_0=1. Par hypothèse de récurrence, A_k = C_k, donc :

A_n = Σ_{k=0}^{n−1} C_k × C_{n−1−k} = C_n,

par la relation de récurrence des nombres de Catalan.

Réponse : Le nombre d’arbres binaires enracinés à n+1 feuilles est Cn.

8. Montrer que le nombre de parenthésages possibles d’un produit non associatif de n+1 termes est Cn.

Solution :

Chaque parenthésage correspond à un arbre binaire enraciné à n+1 feuilles, donc leur nombre est Cn.

Réponse : Le nombre de parenthésages est Cn.

9. Douze convives sont assis autour d’une table. Combien de manières peuvent-ils échanger six poignées de main simultanées sans croisement ?

Solution :

Notons γ_n le nombre de solutions pour 2n convives. On a γ_0=1, γ_1=1, γ_2=2. En supposant γ_k = C_k pour k ≤ n, on montre par récurrence que :

γ_{n+1} = Σ_{k=0}^n C_k × C_{n−k} = C_{n+1}.

Pour 12 convives (n=6), il y a donc C_6 = 132 solutions.

Réponse : Il y a 132 façons de faire ces poignées de main sans croisement.

Méthode

Ce sujet récompense la maîtrise des techniques suivantes :

• Manipulation rigoureuse des coefficients binomiaux et des formules factorielles.
• Utilisation de la récurrence simple et forte pour démontrer des propriétés et formules.
• Construction et exploitation de relations de récurrence, notamment la relation caractéristique des nombres de Catalan.
• Établissement de bijections combinatoires entre différents ensembles pour interpréter les nombres de Catalan.
• Capacité à décomposer des problèmes complexes en sous-problèmes plus simples, notamment dans les dénombrements de chemins.
• Utilisation des propriétés des chemins dans le plan discret et des contraintes géométriques (ne pas franchir la diagonale).

Les erreurs pénalisées sont :

• Confusion dans les indices des sommes ou des coefficients binomiaux.
• Omissions des étapes intermédiaires dans les démonstrations, notamment dans les récurrences.
• Manque de justification claire des bijections ou des correspondances entre ensembles.
• Calculs approximatifs ou erreurs dans la manipulation des expressions factorielles.
• Ignorer les conditions aux bords dans les problèmes de chemins (par exemple, les cas m=0 ou m=n).