Question transversaleMathsNSIRécursivité et récurrence

Combien y a-t-il de façons de placer correctement n paires de parenthèses ?

Q: Calculez C₅ avec la récurrence.

$C₀C₄+C₁C₃+C₂C₂+C₃C₁+C₄C₀=14+5+4+5+14=42$.

Q: Combien de mots de 2n parenthèses sans contrainte ?

$binom2nn$ si l'on impose $n$ ouvrantes et $n$ fermantes ; parmi eux, une fraction $1/(n+1)$ sont bien parenthésés.

Q: La suite des nombres de Catalan est-elle géométrique ?

Non : le rapport $Cₙ₊₁/Cₙ=(2(2n+1))/(n+2)$ n'est pas constant ; il tend vers 4, si bien que $Cₙ$ croît à peu près comme $4ⁿ$, divisé par une puissance de $n$.

Une expression bien parenthésée se décompose en ( A ) B, avec A et B bien parenthésées : C(n + 1) = Σ C(i) × C(n − i). On obtient 1, 1, 2, 5, 14, 42… et 16 796 pour 10 paires, qui est aussi C(20, 10) / 11.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En NSI, nous avons écrit un programme qui vérifie si une expression est bien parenthésée à l'aide d'une pile. Je me suis demandé combien d'expressions correctes on peut former avec 3, puis 10 paires de parenthèses. J'ai découvert les nombres de Catalan, qui comptent aussi les arbres binaires et bien d'autres objets.

L'enjeu et les notions du programme

Construire une relation de récurrence par décomposition récursive d'un objet, et la vérifier avec une formule fermée.

Mathématiques

Dénombrement, principes additif et multiplicatif (terminale)
Combinaisons, coefficient binomial (terminale)
Suites définies par récurrence (première)

Numérique et sciences informatiques

Structure de pile, vérification du parenthésage (terminale)
Récursivité, arbres binaires (terminale)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
Une expression est bien parenthésée si chaque parenthèse ouvrante est fermée plus loin, sans fermer avant d'ouvrir : « (()) » oui, « ())( » non. Problématique : combien d'expressions correctes avec $n$ n paires ?
2. Mathématiques : décomposition récursive
4 min
Petits cas : $C_{0} = 1$ C₀=1 (expression vide), $C_{1} = 1$ C₁=1 : (), $C_{2} = 2$ C₂=2 : ()(), (()), $C_{3} = 5$ C₃=5 : ()()(), ()(()), (())(), (()()), ((())).
Toute expression non vide s'écrit de façon unique $(A) B$ (A)B, où la première parenthèse ouvrante est fermée juste après $A$ A ; $A$ A et $B$ B sont bien parenthésées. Si $A$ A contient $i$ i paires, $B$ B en contient $n - i$ n-i. Par les principes multiplicatif puis additif :
$C_{n + 1} = \sum_{i = 0}^{n} C_{i} C_{n - i}$ Cₙ₊₁=Σ_i=0ⁿCᵢCₙ₋ᵢ.
On calcule : $C_{4} = C_{0} C_{3} + C_{1} C_{2} + C_{2} C_{1} + C_{3} C_{0} = 5 + 2 + 2 + 5 = 14$ C₄=C₀C₃+C₁C₂+C₂C₁+C₃C₀=5+2+2+5=14, puis 42, 132, 429, 1 430, 4 862, $C_{10} = 16796$ C₁₀=16 796.
Formule fermée (admise) : $C_{n} = \frac{1}{n + 1} (n 2 n)$ Cₙ=1/(n+1)binom2nn. Vérification : $\frac{1}{11} (10 20) = \frac{184 756}{11} = 16796$ 1/11 C(20, 10) =(184 756)/11=16 796.
3. NSI : piles et arbres
3 min
Pour vérifier une expression, on parcourt les caractères : on empile chaque « ( » et on dépile à chaque « ) ». L'expression est correcte si l'on ne dépile jamais une pile vide et si la pile est vide à la fin. Coût : un seul parcours.
Les mêmes nombres comptent les arbres binaires à $n$ n nœuds : un arbre est une racine, un sous-arbre gauche à $i$ i nœuds et un sous-arbre droit à $n - 1 - i$ n-1-i nœuds. On peut programmer la génération de toutes les expressions par une fonction récursive qui suit la décomposition $(A) B$ (A)B, et vérifier qu'elle en produit 14 pour 4 paires.
4. Conclusion
1,5 min
Les expressions bien parenthésées se comptent en les décomposant récursivement : les nombres de Catalan $1, 1, 2, 5, 14, 42, \dots$ 1,1,2,5,14,42,… en découlent. Une même suite compte des objets très différents, parce qu'ils ont la même structure récursive. J'ouvre sur les triangulations d'un polygone, comptées par les mêmes nombres.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

C_{n + 1} = i = 0 \sum n C_{i} C_{n - i}, C_{0} = 11, 1, 2, 5, 14, 42, 132 Cₙ₊₁=Σ_i=0ⁿCᵢ Cₙ₋ᵢ, C₀=1 1, 1, 2, 5, 14, 42, 132 C_{n} = \frac{1}{n + 1} (n 2 n) C_{10} = \frac{184 756}{11} = 16796 Cₙ=1/(n+1) C(2n, n) C₁₀=(184 756)/11=16 796

Conclusion : la réponse à la question

On compte les expressions bien parenthésées comme on écrit une fonction récursive : en décomposant l'objet en morceaux plus petits du même type. Les nombres de Catalan en sont la réponse.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Calculez C₅ avec la récurrence.

$C_{0} C_{4} + C_{1} C_{3} + C_{2} C_{2} + C_{3} C_{1} + C_{4} C_{0} = 14 + 5 + 4 + 5 + 14 = 42$ C₀C₄+C₁C₃+C₂C₂+C₃C₁+C₄C₀=14+5+4+5+14=42.

Pourquoi la décomposition (A)B est-elle unique ?

La parenthèse qui ferme la toute première ouvrante est déterminée : c'est la première position où le nombre de « ( » égale celui de « ) ».

Combien de mots de 2n parenthèses sans contrainte ?

$(n 2 n)$ binom2nn si l'on impose $n$ n ouvrantes et $n$ n fermantes ; parmi eux, une fraction $\frac{1}{n + 1}$ 1/(n+1) sont bien parenthésés.

Quel est le coût de la vérification par pile ?

Linéaire : un seul parcours de l'expression.

Combien d'arbres binaires à 3 nœuds ?

$C_{3} = 5$ C₃=5.

La suite des nombres de Catalan est-elle géométrique ?

Non : le rapport $\frac{C _{n + 1}}{C _{n}} = \frac{2 ( 2 n + 1 )}{n + 2}$ Cₙ₊₁/Cₙ=(2(2n+1))/(n+2) n'est pas constant ; il tend vers 4, si bien que $C_{n}$ Cₙ croît à peu près comme $4^{n}$ 4ⁿ, divisé par une puissance de $n$ n.

Les pièges qui coûtent des points

Oublier C₀ = 1 (l'expression vide), indispensable à la récurrence.
Additionner au lieu de multiplier C_i et C_(n−i).
Compter « )( » comme correcte.

Revoir les notions

Autres questions : récursivité et récurrence

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →