Nombre de Catalan

En mathématiques, et plus particulièrement en combinatoire, les nombres de Catalan forment une suite d'entiers naturels utilisée dans divers problèmes de dénombrement, impliquant souvent des objets définis de façon récursive. Ils sont nommés ainsi en l'honneur du mathématicien belge Eugène Charles Catalan (1814-1894) qui les a étudiés en 1838, mais étaient déjà connus d'Euler.

Le nombre de Catalan d'indice $n$ est défini par :

C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ pour }}n\geqslant 0.

Pour $n\geqslant 2$ , on peut écrire :

C_{n}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}={\frac {(n+2)(n+3)\cdots 2n}{2.3\cdots n}}

(voir Coefficient binomial central).

Les dix premiers nombres de Catalan (pour $n$ de 0 à 9) sont :

{\begin{matrix}n&0&1&2&3&4&5&6&7&8&9\\C_{n}&1&1&2&5&14&42&132&429&1\,430&4\,862\end{matrix}}

(pour les 1 001 premiers, voir les liens de la suite A000108 de l'OEIS).

Historique

La suite de Catalan est décrite pour la première fois en 1751 par le Suisse Leonhard Euler : dans une lettre à Goldbach, il pose le problème du dénombrement des triangulations d'un polygone, trouve les 8 premiers nombres, suggère une formule de produit explicite et trouve une forme explicite pour la fonction génératrice^[1]^,^[2]. Ce problème de triangulation est d'ailleurs aussi à l'origine indirecte du sudoku américano-japonais^[3].

En 1758, Johann Andreas Segner reprend le problème des triangulations (faisant explicitement référence à Euler), prouve une relation de récurrence quadratique et utilise la formule pour calculer les 18 premiers nombres, les 6 derniers de manière incorrecte^[4]^,^[2]. Les futurs nombres de Catalan prennent alors le nom de nombres de Segner.

Ce n'est qu'en 1838 qu'Eugène Charles Catalan pose et résout le problème du « nombre de manières d'effectuer le produit de n facteurs différents »^[5].

En 1839 Catalan fait le lien avec le nombre de triangulations^[6], et publie un article complet sur le sujet en 1887^[7]. Depuis, le nom de Catalan remplace celui de Segner.

L'astuce de comptage des mots de Dyck est trouvée par Désiré André en 1887.

En 1988, dans la revue chinoise Neimenggu Daxue Xuebao, a été publié le fait que la suite des nombres de Catalan avait été utilisée en Chine par le mathématicien Ming Antu (ou Minggatu) dès 1730, lors de l'écriture de son livre Ge Yuan Mi Lu Jie Fa (en), achevé par son élève Chen Jixin en 1774 et publié 60 ans plus tard.

P. J. Larcombe esquissa en 1999 certaines des caractéristiques du travail de Ming Antu, comme le fait qu'il utilisa la suite des nombres de Catalan pour exprimer des développements en séries de sin(2αあるふぁ) et sin(4αあるふぁ) en termes de sin(αあるふぁ)^[8].

Propriétés et comportement asymptotique

Une autre expression pour $C_{n}$ est

C_{n}={2n \choose n}-{2n \choose n+1}\quad {\text{pour }}n\geqslant 0,

ce qui est équivalent à l'expression précédente car ${\binom {2n}{n+1}}={\frac {n}{n+1}}{\binom {2n}{n}}$ . Cela montre que $C_{n}$ est un entier naturel, ce qui n'est pas évident de prime abord à partir de la première formule.

Les nombres de Catalan satisfont aussi à la relation de récurrence

C_{0}=1\quad {\mbox{et}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{pour }}n\geqslant 0.

De plus,

C_{n}={\frac {1}{n+1}}\sum _{i=0}^{n}{n \choose i}^{2}.

Cela est dû au fait que ${2n \choose n}=\sum _{i=0}^{n}{n \choose i}^{2}$ . Ils vérifient aussi $C_{0}=1$ et $C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n}$ , ce qui peut être un moyen plus efficace pour les calculer.

La formule de Stirling permet de calculer un équivalent asymptotique de la suite des nombres de Catalan^[9] :

C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}

Un résultat dû à Ernst Kummer, et qui se déduit trivialement de la relation de récurrence indiquée plus haut, aboutit à ce que les seuls nombres de Catalan $C_{n}$ impairs sont ceux pour lesquels $n=2^{k}-1$ . Tous les autres sont pairs.

Applications en combinatoire

Il existe de nombreux problèmes combinatoires dont la solution est donnée par les nombres de Catalan. Les nombres de Catalan peuvent être interprétés de différentes façons dont voici quelques exemples :

$C_{n}$ est égal au nombre de mots de Dyck de longueur $2n$ .
$C_{n}$ est également le nombre de façons différentes de placer des parenthèses autour de $n$ + 1 facteurs, pour préciser une expression faisant intervenir $n$ fois une loi de composition interne non associative.
$C_{n}$ est également le nombre d'arbres binaires stricts à $n$ + 1 feuilles.
$C_{n}$ est aussi égal au nombre de façons de découper en triangles un polygone convexe à $n$ + 2 côtés en reliant certains de ses sommets par des segments de droite.
$C_{n}$ est le nombre de chemins monotones le long des arêtes d'une grille à $n$ × $n$ carrés, qui restent sous (ou au niveau de) la diagonale.
$C_{n}$ est le nombre de trajectoires de longueur 2 $n$ + 1 d'une marche aléatoire simple qui ont la propriété d'aller de la hauteur 0 à la hauteur 1 en restant négatif ou nul lors des 2 $n$ premières étapes.
$C_{n}$ est le nombre d'arbres planaires enracinés à $n$ arêtes.

Mots de Dyck

Article détaillé : Langage de Dyck.

Un mot de Dyck est une chaîne de caractères formée de $n$ lettres $X$ et de $n$ lettres $Y$ , telle qu'aucun préfixe (mot obtenu en supprimant les dernières lettres à partir d'un rang quelconque) ne contienne strictement plus de $Y$ que de $X$ . Autrement dit, lorsque nous parcourons un mot de Dyck de gauche à droite, le nombre de $X$ rencontrés est toujours supérieur ou égal au nombre de $Y$ . Par exemple, les mots de Dyck de la longueur 6 sont:

XXXYYY,\quad XYXXYY,\quad XYXYXY,\quad XXYYXY,\quad XXYXYY.

En l'occurrence, C₃= 5.

Assimilant $X$ à une parenthèse ouvrante et $Y$ à une parenthèse fermante, un mot de Dyck de longueur 2n peut être vu comme une expression formée de $n$ paires de parenthèses correctement assemblées : ((())), ()(()), ()()(), (())(), (()()) ; voir aussi Langage de Dyck. Les mots de Dyck peuvent être naturellement représentés comme des chemins dans un quadrillage de $n$ + 1 points par $n$ + 1 points, reliant certains points par les traits verticaux et horizontaux. Ces chemins commencent dans le coin inférieur gauche, et se terminent dans le coin supérieur droit, en allant toujours vers le haut ou vers la droite, mais ne passant jamais au-dessus de la diagonale principale. $X$ représente alors un « déplacement vers la droite » et $Y$ représente un « déplacement vers le haut ».
Nous pouvons compter les mots de Dyck avec l'astuce suivante appelée principe de symétrie : intéressons-nous aux mots contenant n $X$ et n $Y$ qui ne sont pas des mots de Dyck. Dans de tels mots, déterminons le premier Y qui brise la condition de Dyck, puis modifions toutes les lettres qui suivent ce $Y$ , en échangeant $X$ avec $Y$ et vice versa. Nous obtenons un mot avec $n$ + 1 $Y$ et $n$ - 1 $X$ , et en fait tous les mots comportant $n$ + 1 $Y$ et $n$ - 1 $X$ peuvent être obtenus par ce moyen et de manière unique. Le nombre de ces mots est le nombre de façons de placer les $n$ - 1 $X$ dans 2 $n$ emplacements et est égal à

{2n \choose n-1}

ce qui donne le nombre de mots qui ne sont pas de Dyck ; le nombre de mots de Dyck est égal à

{2n \choose n}-{2n \choose n-1}

qui est le $n$ -ième nombre de Catalan $C_{n}$ .

Notons que ce dénombrement est celui posé dans le problème du scrutin au sens large.

Une généralisation au cas où les lettres $X$ et $Y$ ne sont pas en même quantité se trouve dans l'article sur le triangle de Catalan.

Nombre de parenthésages dans un produit

$C_{n}$ est le nombre de façons différentes de placer des parenthèses autour de $n$ + 1 termes, pour préciser une expression faisant intervenir $n$ fois une loi de composition interne. Pour $n$ = 3 par exemple, la loi étant notée multiplicativement, nous obtenons 5 façons différentes de placer des parenthèses autour de 4 facteurs : $a(b(cd)),a((bc)d),(ab)(cd),(a(bc))d,((ab)c)d$ .

Lorsque la loi est associative, chaque parenthésage donne le même résultat, mais peut conduire à des temps de calcul différents. En particulier pour un produit matriciel le nombre de multiplications scalaires à effectuer change suivant les parenthésages, et dans la pratique, cela peut rendre nécessaire l'utilisation d'algorithmes de multiplication de matrices enchaînées.

Triangulations d'un polygone

$C_{n}$ est aussi égal au nombre de façons de découper en triangles un polygone convexe à $n+2$ côtés en reliant certains de ses sommets par des segments de droite.

Pour n = 3, un polygone à n + 2 sommets est un pentagone : le nombre de ses triangulations est C₃ = 5.

Arbres binaires

$C_{n}$ est également le nombre d'arbres binaires à $n$ nœuds (internes et externes).

$C_{n}$ est aussi le nombre d'arbres binaires stricts à $n$ + 1 feuilles^{[n 1]}. La correspondance entre les produits non associatifs, les triangulations d'un polygone et les arbres binaires stricts est illustré sur l'image ci-dessous.

Partitions non croisées

Article détaillé : Partition non croisée.

$C_{n}$ est également le nombre de partitions non croisées de l'ensemble {1, … , $n$ }. A fortiori, $C_{n}$ n'excède jamais le $n$ -ième nombre de Bell, ce qui était asymptotiquement attendu, puisque les nombres de Bell croissent bien plus vite que $2^{2n}$ , une autre borne des nombres de Catalan, découlant par exemple de leur définition comme nombre de mots de Dyck de longueur 2 $n$ .

Chemins sous-diagonaux dans le carré

$C_{n}$ est le nombre de chemins monotones le long des arêtes d'une grille à $n$ × $n$ carrés, qui restent sous (ou au niveau de) la diagonale. Un chemin monotone part du coin Sud-Ouest, arrive dans le coin Nord-Est, et est constitué d'arêtes dirigées à droite ou vers le haut. Un mot de Dyck encode un tel chemin de la manière suivante : $X$ signifie « va à droite » et $Y$ signifie « monte ». Les diagrammes ci-dessous représentent le cas $n$ = 4 :

Pour $n=1,2,3,4,5,6,7,\dots$ , l'aire totale sous les chemins vaut : $0,1,8,47,244,1186,5536,\dots$ (suite A029760 de l'OEIS).

Trajectoires de la marche aléatoire simple

$C_{n}$ est le nombre de trajectoires de longueur 2 $n$ + 1 d'une marche aléatoire simple qui ont la propriété d'aller de la hauteur 0 à la hauteur 1 en restant négatif ou nul lors des 2 $n$ premières étapes. On peut voir cela en faisant pivoter de 45 degrés le chemin entre les deux coins d'un carré décrit lors du premier exemple. C'est aussi le nombre de trajectoires de longueur 2 $n$ + 2 allant de la hauteur 0 à la hauteur 0 en restant strictement positives lors des 2 $n$ + 1 étapes intermédiaires, ou encore le nombre de trajectoires de longueur 2n allant de la hauteur 0 à la hauteur 0 en restant positives ou nulles lors des 2 $n$ – 1 étapes intermédiaires. Dans ce dernier cas on peut coder la trajectoire par une suite de 2 $n$ signes + et – (pour montée et descente), la condition de positivité se traduisant par le fait que cette suite est un mot de Dyck (car chaque préfixe a plus de montées que de descentes). Ainsi, pour la marche aléatoire simple, la probabilité que le premier temps de retour en 0, partant de 0, ait lieu à l'instant 2 $n$ + 2, est $2C_{n}p^{n+1}(1-p)^{n+1}$ , le facteur 2 prenant en compte les trajectoires strictement négatives en plus des trajectoires strictement positives. De même, la probabilité que le premier temps d'atteinte de 1, partant de 0, ait lieu à l'instant 2 $n$ + 1, est $C_{n}p^{n+1}(1-p)^{n}$ .

Arbres planaires

$C_{n}$ est le nombre d'arbres planaires enracinés à $n$ arêtes. La bijection avec les mots de Dyck, ou encore avec les trajectoires de marches aléatoires, est donnée très visuellement par un parcours extérieur de l'arbre. La trajectoire obtenue est le graphe de la fonction qui à chaque coin (secteur angulaire délimité par un sommet et deux arêtes contigües issues de ce sommet) associe la hauteur du sommet (la distance du sommet à la racine). Les coins sont parcourus dans l'ordre correspondant au parcours autour de l'arbre (voir figure ci-contre). Chaque sommet est visité autant de fois qu'il y a de coins issus de ce sommet, c.-à-d. le nombre de visites à un sommet est le degré de ce sommet ; à titre d'exception, le nombre de visites à la racine est son degré plus un (plus le retour final à la racine, qui revient à visiter deux fois le coin origine). Ainsi le nombre de pas de la marche est la somme des degrés du graphe, c.-à-d. deux fois le nombre d'arêtes du graphe.

Bijection entre les 5 arbres à 3 arêtes (ligne supérieure), les 5 trajectoires positives de longueur 6 (ligne intermédiaire) et les mots de Dyck correspondants (ligne inférieure).

Bijections entre les exemples

Les ensembles décrits plus haut qui sont à $C_{n}$ éléments sont clairement en bijection les uns avec les autres.

Les bijections entre deux ensembles symétriques (produits non associatifs, triangulations d'un polygone, arbres binaires stricts) sont décrits plus haut. De même les bijections entre deux ensembles latéralisés (mots de Dyck, chemins monotones sous la diagonale, marches aléatoires positives, arbres planaires) sont décrits dans les sections précédentes. La bijection entre les arbres binaires stricts à 2n arêtes et les arbres planaires à n arêtes se fait en contractant soit les arêtes gauches, soit les arêtes droites de l'arbre binaire. D'où les appellations « symétriques » et « latéralisés ».

L'image suivant illustre les différentes bijections avec un exemple concret :

Relations de récurrence

Comme vu précédemment, les nombres de Catalan satisfont la relation de récurrence

$C_{0}=1\qquad {\mbox{et pour}}\quad n\geqslant 1\qquad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}.$ Ceci vient du fait que tout mot de Dyck w de longueur supérieure à 2 peut s'écrire de manière unique sous la forme $w=Xw_{1}Yw_{2},$ où w₁ et w₂ désignent des mots de Dyck (éventuellement vides). La série génératrice des nombres de Catalan est définie par $c(x)=\sum _{n=0}^{\infty }C_{n}x^{n}$ et en utilisant la relation de récurrence ci-dessus, on voit que $c(x)=1+xc(x)^{2}$ et par conséquent $c(x)={\frac {1-(1-4x)^{1/2}}{2x}}$ ^{[n 2]};réciproquement, partant de la série génératrice, on obtient aisément la formule explicite des $C_{n}$ en utilisant le développement de Newton de $(1-4x)^{1/2}$ ; ce passage d'une relation de récurrence à une formule explicite est une des utilisations les plus importantes des séries génératrices.

D'autre part, ils satisfont la relation de récurrence

$C_{0}=1,\forall n\geqslant 1\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1},$ qui permet aussi de retrouver la série génératrice, en effet, cette relation montre que $c(x)$ est la solution de l'équation différentielle $(x-4x^{2})c'(x)+(1-2x)c(x)-1=0$ qui vaut 1 en 0.

Ils satisfont enfin à la relation de récurrence de Jacques Touchard :

$C_{0}=1,\forall n\geqslant 0\quad C_{n+1}=\sum _{0\leqslant k\leqslant \,n/2}2^{n-2k}{n \choose 2k}C_{k}$ .

Matrice de Hankel

La matrice de Hankel d'ordre $n$ dont le terme $(i,j)$ est le nombre de Catalan $C_{i+j-2}$ a pour déterminant 1, indépendamment de la valeur de $n$ .

Ainsi, pour $n$ = 4, nous avons

\det {\begin{pmatrix}1&1&2&5\\1&2&5&14\\2&5&14&42\\5&14&42&132\end{pmatrix}}=1.

De plus, si les termes sont « décalés », en prenant les nombres de Catalan $C_{i+j-1}$ , le déterminant est toujours 1, indépendamment de la valeur de $n$ ^{[n 3]}.

Ainsi, pour $n$ = 4, nous avons

\det {\begin{pmatrix}1&2&5&14\\2&5&14&42\\5&14&42&132\\14&42&132&429\end{pmatrix}}=1.

La suite des nombres de Catalan est la seule suite de nombres^{[n 4]} ayant cette double propriété.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Catalan number » (voir la liste des auteurs).

Notes

↑ Un arbre binaire est dit strict (ou localement complet) si chaque nœud a soit 0 soit 2 fils. Un tel arbre à n + 1 feuilles a aussi n nœuds internes, et 2n arêtes.
↑ Cette écriture est parfaitement rigoureuse dans le cadre des séries formelles ; si on interprète $c(x)$ comme une série entière, l'expression asymptotique de $C_{n}$ montre que le rayon de convergence de la série est 1/4, et que sur l'intervalle réel $[-1/4,1/4]$ , on a $c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}$ , en prolongeant le membre de droite en 0 par la valeur 1.
↑ En revanche, ce n'est plus le cas pour un décalage de 2 lignes : $\det {\begin{pmatrix}2&5\\5&14\end{pmatrix}}=3$ .
↑ L'existence et l'unicité d'une telle suite se démontre aisément par récurrence, mais il est nettement moins aisé de vérifier qu'on obtient ainsi la suite des nombres de Catalan.

Références

↑ (de) Leonhard Euler, « Lettre CXL », sur eulerarchive.maa.org
↑ ^{a et b} (en) Igor pak, « Catalan numbers page »
↑ "Ouest-France" du 18 août 2021 in fine.
↑ (la) Johann Andreas Segner, « Enumeratio modorum quibus figurae planae rectilinae per diagonales dividuntur in triangula », Novi Commentarii Academiae Scientiarum Imperialis Petropolitanae, vol. 7,‎ 1758/59, publié en 1761 (lire en ligne)
↑ E. Catalan, « Note sur une équation aux différences finies », Journal de Mathématiques pures et appliquées, n^o 3,‎ 1838, p. 515-516 (lire en ligne)
↑ E. Catalan, « Solution nouvelle de cette question: un polygone étant donné, de combien de manières peut-on le partager en triangles au moyen de diagonales ? », Journal de mathématiques pures et appliquées x, 1^re série, n^o 4,‎ 1839, p. 91-94. (lire en ligne)
↑ E. Catalan, « Sur les nombres de Segner », Rend. Circ. Mat. Palermo 1 (1887), 190–201., n^o 1,‎ 1887, p. 190-201 (lire en ligne)
↑ (en) Luo Jianjin, « Ming'antu and His Power Series Expansions », Institute for the History of Science, Inner Mongolia Normal University; Institute of Science, Technology and Culture, Zhejiang University.
↑ On trouvera une analyse plus précise de ce développement asymptotique dans Analytic Combinatorics, p. 383.

Voir aussi

Bibliographie

(en) Richard P. Stanley, Enumerative Combinatorics, vol. 1 et 2 [détail des éditions] (présentation en ligne)
(en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2008 (ISBN 0-521-89806-4, lire en ligne)
Aubrey Blecher, Charlotte Brennan et Arnold Knopfmacher, « Water capacity of Dyck paths », Advances in Applied Mathematics, vol. 112,‎ 2020, article n^o 101945 (ISSN 0196-8858, DOI 10.1016/j.aam.2019.101945)

Articles connexes

Triangle de Catalan
Coefficient binomial central ${\binom {2n}{n}}$
Algorithme de Rémy
Nombre de Delannoy
Nombre de Fuss-Catalan (en)

Liens externes

(en) Eric W. Weisstein, « Catalan Number », sur MathWorld
[vidéo] El ji, « Deux (deux ?) minutes pour... les nombres de Catalan », sur YouTube, 2017 (consulté le 28 mars 2023)
Texte de la vidéo précédente.

Portail des mathématiques

[10] Un arbre binaire est dit strict (ou localement complet) si chaque nœud a soit 0 soit 2 fils. Un tel arbre à n + 1 feuilles a aussi n nœuds internes, et 2n arêtes.

[11] Cette écriture est parfaitement rigoureuse dans le cadre des séries formelles ; si on interprète $c(x)$ comme une série entière, l'expression asymptotique de $C_{n}$ montre que le rayon de convergence de la série est 1/4, et que sur l'intervalle réel $[-1/4,1/4]$ , on a $c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}$ , en prolongeant le membre de droite en 0 par la valeur 1.

[12] En revanche, ce n'est plus le cas pour un décalage de 2 lignes : $\det {\begin{pmatrix}2&5\\5&14\end{pmatrix}}=3$ .

[13] L'existence et l'unicité d'une telle suite se démontre aisément par récurrence, mais il est nettement moins aisé de vérifier qu'on obtient ainsi la suite des nombres de Catalan.

[1] (de) Leonhard Euler, « Lettre CXL », sur eulerarchive.maa.org

[:0-2] {a et b} (en) Igor pak, « Catalan numbers page »

[3] "Ouest-France" du 18 août 2021 in fine.

[4] (la) Johann Andreas Segner, « Enumeratio modorum quibus figurae planae rectilinae per diagonales dividuntur in triangula », Novi Commentarii Academiae Scientiarum Imperialis Petropolitanae, vol. 7,‎ 1758/59, publié en 1761 (lire en ligne)

[5] E. Catalan, « Note sur une équation aux différences finies », Journal de Mathématiques pures et appliquées, n^o 3,‎ 1838, p. 515-516 (lire en ligne)

[6] E. Catalan, « Solution nouvelle de cette question: un polygone étant donné, de combien de manières peut-on le partager en triangles au moyen de diagonales ? », Journal de mathématiques pures et appliquées x, 1^re série, n^o 4,‎ 1839, p. 91-94. (lire en ligne)

[7] E. Catalan, « Sur les nombres de Segner », Rend. Circ. Mat. Palermo 1 (1887), 190–201., n^o 1,‎ 1887, p. 190-201 (lire en ligne)

[Jianjin-8] (en) Luo Jianjin, « Ming'antu and His Power Series Expansions », Institute for the History of Science, Inner Mongolia Normal University; Institute of Science, Technology and Culture, Zhejiang University.

[9] On trouvera une analyse plus précise de ce développement asymptotique dans Analytic Combinatorics, p. 383.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[n 1]

[n 2]

[n 3]

[n 4]