PC∗

Nombres de Catalan (Centrale PC 2021)

Durée : 4 heures

Ce sujet est divisé en trois parties.

– Dans la première partie, on étudie une marche aléatoire sur Z qui modélise la trajectoire d’une particule. On
s’intéresse en particulier au temps nécessaire pour que la particule revienne pour la première fois à son point de
départ, si cela arrive. Pour cela, on introduit une suite de nombres appelés nombres de Catalan et on étudie leurs
propriétés.
– Dans la deuxième partie, entièrement indépendante de la première, on s’intéresse au calcul d’un déterminant à
l’aide d’une suite de polynômes orthogonaux.
– Dans la troisième partie enfin, on utilise les résultats des deux premières parties pour calculer deux déterminants
associés aux nombres de Catalan.

I Étude d’une marche aléatoire sur Z

Soit (Ω, A, P) un espace probabilisé et soit (Xn )n∈N∗ une suite de variables aléatoires définies sur Ω et à valeurs dans
{−1, 1}, mutuellement indépendantes, et telles que, pour tout n ∈ N∗ ,

P(Xn = 1) = p et P(Xn = −1) = 1 − p, où p ∈]0, 1[.

n
X
On pose S0 = 0 et, pour tout n ∈ N∗ , Sn = Xk .
k=1
La suite (Sn )n∈N modélise la trajectoire aléatoire dans Z d’une particule située en S0 = 0 à l’instant initial n = 0, et faisant à
chaque instant n ∈ N un saut de +1 avec une probabilité p et de −1 avec une probabilité 1 − p, les sauts étant indépendants
et p appartenant à ]0, 1[.
Pour ω ∈ Ω, on représente la trajectoire de la particule par la ligne brisée joignant les points de coordonnées (n, Sn (ω))n∈N .

−1

−2

0 1 2 3 4 5 6 7 8 9

Figure 1 – Exemple de trajectoire possible

I. A – Espérance et variance de Sn
Dans cette sous-partie, n désigne un entier naturel non nul.
Soit Yn la variable aléatoire sur Ω égale au nombre de valeurs de k ∈ ⟦1, n⟧ telles que Xk = 1.
Q 1. Quelle est la loi de Yn ? En déduire l’espérance et la variance de Yn .
Q 2. Quelle relation a-t-on entre Sn et Yn ? En déduire l’espérance et la variance de Sn . Justifier que Sn et n ont même
parité.

I. B – Chemins de Dyck et loi du premier retour à l’origine

Pour m ∈ N∗ , on appelle chemin de longueur m tout m-uplet γ = (γ1 , . . . , γm ) tel que ∀i ∈ ⟦1, m⟧, γi ∈ {−1, 1}.
k
X
On pose alors sγ (0) = 0 et, pour tout k ∈ ⟦1, m⟧, sγ (k) = γi .
i=1
On représente le chemin γ par la ligne brisée joignant la suite des points de coordonnées (k, sγ (k))k∈⟦0,m⟧ .

Lycée Marcelin Berthelot page 1

Pour n ∈ N∗ :
– on appelle chemin de Dick de longueur 2n tout chemin γ = (γ1 , . . . , γ2n ) de longueur 2n tel que sγ (2n) = 0 et
∀k ∈ ⟦0, 2n⟧, sγ (k) ⩾ 0 ;
– on note Cn le nombre de chemins de Dyck de longueur 2n.
On convient de plus que C0 = 1.
La suite (Cn )n∈N est appelée suite des nombres de Catalan. On constate que C1 = 1 et C2 = 2.

2 2

1 1 1

0 0 0
0 1 2 0 1 2 3 4 0 1 2 3 4

Figure 2 – Représentation des chemins de Dyck de longueurs 2 et 4

Q 3. Donner sans démonstration la valeur de C3 et représenter tous les chemins de Dyck de longueur 6.
n o
Soit n ∈ N et γ = (γ1 , . . . , γ2n+2 ) un chemin de Dyck de longueur 2n + 2. Soit r = max i ∈ ⟦0, n⟧ sγ (2i) = 0 .
On suppose 0 < r < n et on considère les chemins α = (γ1 , . . . , γ2r ) et β = (γ2r+2 , . . . , γ2n+1 ).
Q 4. Justifier à l’aide d’une figure que γ2r+1 = 1, γ2n+2 = −1 et que α et β sont des chemins de Dyck.
Soit m ∈ N∗ et γ = (γ1 , . . . , γm ) un chemin de longueur m.
Pour t ∈ N, on note At,γ l’événement : « pour tout k ∈ ⟦1, m⟧, Xt+k = γk » ; en d’autres termes,
m 
\ 
At,γ = Xt+k = γk
k=1

Q 5. Soit n ∈ N∗ et soit γ = (γ1 , . . . , γ2n ) un chemin de Dyck de longueur 2n. Pour t ∈ N, exprimer P(At,γ ) en fonction de
n et p.
Soit T la variable aléatoire, définie sur Ω et à valeurs dans N, égale au premier instant où la particule revient à l’origine, si
cet instant existe, et égale à 0 si la particule ne revient jamais à l’origine :

∗
0 n o si ∀k ∈ N , Sk (ω) , 0


∀w ∈ Ω, T(ω) = 
min k ∈ N∗ Sk (ω) = 0
 sinon
 
Q 6. Montrer que T prend des valeurs paires et que, pour tout n ∈ N, P T = 2n + 2 = 2Cn pn+1 (1 − p)n+1 .

I. B. 1) Série génératrice des nombres de Catalan n

X
Q 7. En utilisant la question 4, montrer ∀n ∈ N, Cn+1 = Cr Cn−r .
r=0
XC
n
Q 8. À l’aide de la variable aléatoire T, montrer que la série converge.
4n
n⩾0
1 1
X  
Q 9. En déduire que la série entière Cn t n converge normalement sur l’intervalle I = − , .
4 4
n⩾0
+∞
X
On pose alors, pour tout t ∈ I, f (t) = Cn t n et g(t) = 2tf (t).
n=0
+∞
X
On rappelle que la série génératrice de T, donnée par GT (t) = P(T = n)t n , est définie si t ∈ [−1, 1].
n=0

Q 10. À l’aide des questions précédentes, exprimer GT à l’aide de g et de P(T = 0).

1
Q 11. En déduire que, si p , , alors T admet une espérance.
2
Q 12. Montrer que ∀t ∈ I, g(t)2 = 2g(t) − 4t.
√
Q 13. En déduire qu’il existe une fonction ε : I → {−1, 1} telle que ∀t ∈ I, g(t) = 1 + ε(t) 1 − 4t.

page 2 Lycée Marcelin Berthelot

 1
  √
Q 14. Montrer que ε est continue sur I \ . En déduire ∀t ∈ I, g(t) = 1 − 1 − 4t.
4
p 1
Q 15. En déduire que P(T , 0) = 1 − 1 − 4p(1 − p). Interpréter ce résultat lorsque p = .
2
1
Q 16. Montrer que si p = , alors T n’admet pas d’espérance.
2

I. C – Expression des nombres de Catalan et équivalent +∞

√ X
Q 17. Justifier l’existence d’une suite de réels (an )n∈N telle que ∀x ∈ ]−1, 1[, 1+x = 1+ an xn+1 et, pour tout n ∈ N,
exprimer an à l’aide d’un coefficient binomial. n=0
!
1 2n
Q 18. En déduire ∀n ∈ N, Cn = .
n+1 n
Q 19. Rappeler l’équivalent de Stirling. En déduire un équivalent de Cn lorsque n tend vers +∞.
Q 20. À partir de la question précédente, retrouver le résultat des question 11 et 16.

II Calcul d’un déterminant à l’aide d’un système orthogonal

Dans cette partie, on suppose que l’espace vectoriel R[X] est muni d’un produit scalaire (· | ·) et on note ∥ · ∥ la norme
associée.
Pour tout n ∈ N, on note Gn la matrice carrée de taille n + 1 suivante :

(1 | X) · · · (1 | Xn ) 
 
 (1 | 1)
n
 (X | 1) (X | X) · · · (X | X ) 
  

i−1 j−1
Gn = X X =  .
.. ..

 ..
 
1⩽i,j⩽n+1
 n . . 
(X | 1) (Xn | X) · · · (Xn | Xn )


On cherche à obtenir une expression du déterminant de Gn à l’aide d’une suite de polynômes orthogonaux.

II. A – Définition et propriétés d’un système orthogonal

Dans R[X] muni du produit scalaire (· | ·), on appelle système orthogonal toute suite de polynômes (Pn )n∈N vérifiant les
propriétés suivantes :
 
– (Pn )n∈N est une famille orthogonale, c’est-à-dire : ∀(i, j) ∈ N2 , i , j =⇒ Pi Pj = 0 ;
– pour tout n ∈ N, Pn est unitaire et de degré n.
Dans toute la partie II, on considère un système orthogonal (Vn )n∈N .
Q 21. Montrer que, pour tout n ∈ N, la famille (V0 , V1 , . . . , Vn ) est une base orthogonale de l’espace vectoriel Rn [X] des
polynômes à coefficients réels de degré inférieur ou égal à n.
 
Q 22. Soit n ∈ N et P ∈ R[X] tels que deg P < n. Montrer que Vn P = 0.
Q 23. Soit (Wn )n∈N un autre système orthogonal. Montrer que ∀n ∈ N, Wn = Vn .

II. B – Expression de det Gn à l’aide de la suite (Vn )n∈N

Soit n ∈ N et soit G′n la matrice carrée de taille n + 1 suivante :
 
(V0 | V0 ) (V0 | V1 ) ··· (V0 | Vn )
(V1 | V0 ) (V1 | V1 ) ··· (V1 | Vn )
  

′
Gn = Vi−1 Vj−1 =  .. .. ..


1⩽i,j⩽n+1 
 . . . 

(Vn | V0 ) (Vn | V1 ) · · · (Vn | Vn )

On note Qn = (qi,j )1⩽i,j⩽n+1 la matrice de la famille (V0 , V1 , . . . , Vn ) dans la base (1, X, . . . , Xn ) de Rn [X].
Q 24. Montrer que Qn est triangulaire supérieure et que det Qn = 1.
Q 25. Montrer que QnT Gn Qn = G′n , où QnT est la transposée de la matrice Qn .
n
Y
Q 26. En déduire que det Gn = ∥Vi ∥2 .
i=0

Lycée Marcelin Berthelot page 3

III Déterminant de Hankel des nombres de Catalan
Dans cette partie, on introduit un produit scalaire particulier sur R[X] et une suite de polynômes. On vérifie qu’il s’agit
d’un système orthogonal pour ce produit scalaire, ce qui permettra d’appliquer les résultats de la partie précédente.

III. A – Produit scalaire √

1−x
Q 27. Soit P ∈ R[X] et Q ∈ R[X]. Montrer que la fonction x 7→ P(4x)Q(4x) √ est intégrable sur ]0, 1].
x
Dans toute la partie III, on pose
√
  2Z1 1−x
∀(P, Q) ∈ R[X] × R[X], P Q = P(4x)Q(4x) √ dx
π 0 x
Q 28. Montrer que (· | ·) est un produit scalaire sur R[X].

III. B – Système orthogonal

Soit (Un )n∈N la suite de polynômes définie par U0 = 1, U1 = X − 1 et ∀n ∈ N, Un+2 = (X − 2)Un+1 − Un .
Q 29. Pour tout n ∈ N, montrer que Un est unitaire de degré n, et déterminer la valeur de Un (0).
Q 30. Soit θ ∈ R. Montrer que ∀n ∈ N, Un (4 cos2 θ) sin(θ) = sin((2n + 1)θ).
Z π/2
Q 31. Soit (m, n) ∈ N2 . Calculer sin((2m + 1)θ) sin((2n + 1)θ) dθ.
0
Q 32. En déduire que (Un )n∈N est un système orthogonal et que, pour tout n ∈ N, ∥Un ∥ = 1.
Pour calculer la valeur de (Um | Un ), on pourra effectuer le changement de variable x = cos2 θ.

III. C – Application
Pour tout n ∈ N, on pose µn = (Xn | 1).
Q 33. À l’aide d’une intégration par parties, montrer
1
2 × 4n
Z
3
∀n ∈ N∗ , 4µn−1 − µn = xn−3/2 (1 − x)3/2 dx = µ
π 0 2n − 1 n

Q 34. En déduire ∀n ∈ N, µn = Cn .
Q 35. Soit n ∈ N. Déduire des parties précédentes la valeur du déterminant

C0 C1 C2 ··· Cn−1 Cn
. . .
C1 .. .. .. Cn+1
.. . . ..
  C2 . .. .. .
Hn = det Ci+j−2 = ..
1⩽i,j⩽n+1
. . .. ..
.
..
.
C2n−2
. . .
Cn−1 .. .. .. C2n−1
Cn Cn+1 ··· C2n−2 C2n−1 C2n

III. D – Un autre déterminant de Hankel

Dans cette sous-partie, on pose, pour tout n ∈ N,

C0 C1 C2 ··· Cn−1 Cn C1 C2 C3 ··· Cn−1 Cn

. . .
C1 ..
.
..
.
..
.
Cn+1 C2 .. .. .. Cn+1
.. .. . . ..
..
.
..
.
..
. C3 . .. .. .
Dn (X) = C2 . et H′n = ..
.. . . . . .. ..
.
..
.
. .. .. .. C2n−2 . C2n−3
. . .
Cn−1 Cn Cn+1 ··· C2n−2 C2n−1 Cn−1 .. .. .. C2n−2
1 X ··· Xn−2 Xn−1 Xn Cn Cn+1 ··· C2n−3 C2n−2 C2n−1
 
Q 36. Soit (n, k) ∈ N2 tel que k < n. Montrer Dn Xk = 0.
Q 37. En déduire que ∀n ∈ N, Dn = Un , puis déterminer, pour tout n ∈ N∗ , la valeur du déterminant H′n .

page 4 Lycée Marcelin Berthelot