ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges
|
|
Problème : étant donné un produit de n nombres, de combien de façons peut-on "parenthéser" le produit en regroupant deux termes consécutifs (sans changer l'ordre) parmi les n nombres donnés (deux termes ou plus ne peuvent rester sans parenthèses) ?
Le nombre de possibilités est définie par la suite (Cn) avec C2 = 1 (C comme Catalan, bien sûr) et pour tout n au moins égal à 3 :
On peut faire entrer C2 dans la formule de récurrence en démarrant la suite à n = 1 en posant conventionnellement C1 = 1 et au moyen des combinaisons, on montrera facilement que l'on a :
➔
Pour éviter toute confusion entre les Cnp
(combinaisons) et les Cn (nombres de Catalan), on peut utiliser la
notation
très souvent employée pour les combinaisons. La formule ci-dessus s'écrit
alors :
ou encore, en exprimant Cn+1 :
On constate alors que les nombres de Catalan se trouvent dans le triangle de Pascal : termes médians des lignes de rang pair 2n, divisés par n + 1. On peut montrer (bon courage...) que la solution du problème est aussi donnée par la formule de récurrence :
Premiers nombres de Catalan :
n c(n) n
c(n) 1
1
11 16796 2 1 12 58786 3 2 13 208012 4 5 14 742900 5 14 15 2674440 6 42 16 9694845 7 132 17 35357670 8 429 18 129644790 9 1430 19 477638700 10 4862 20 1767263190
| Autres interventions de ces nombres : |
Considérons un polygone convexe d'au moins n = 4 côtés (quadrilatère, pentagone, hexagone,...) :
- De combien de façons peut-on le découper au moyen de diagonales ne s'intersectant pas ?
ou encore :
- De combien de façons peut-on le découper en n - 2 triangles ?
Ce problème combinatoire fut initialement posé par Euler :
Le nombre de possibilités est alors Cn - 1.
- Problème des votes : Lors d'une élection, il y a 2 candidats A et B , 2n bulletins exprimés et exactement n votes pour a et n votes pour B. Dans combien de cas le dépouillement fera apparaître que A est toujours en tête ou à égalité devant B ?
La réponse est ici Cn + 1, comme on peut le vérifier pour n = 2 et 3, ci-dessous :
n = 1 :
n = 2 :
,
n = 3 :
➔ Pour en savoir plus :
Nombres de Catalan
