ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Nombres de Catalan

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 :

© Serge Mehl - www.chronomath.com