Le Roi des Catalans (2ème partie)

Dans la première partie de cet article, nous nous étions intéressés au problème suivant:

Si on place un Roi sur un échiquier de $(n +1) \times (n +1)$ cases, et s’il ne peut se déplacer que vers la droite ou vers le haut à chaque étape, de combien de façons $C_n$ peut-il aller de la case $(0,0)$ à la case $(n,n)$ sans jamais aller au-dessus de la diagonale principale ?

Nous avions déterminé une relation de récurrence suivie par la suite $(C_n)$ , à savoir:

$\displaystyle C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$

Grâce à celle-ci, nous avions trouvé que, pour un échiquier standard (8 cases sur 8 cases), il y avait $C_7 = 429$ chemins possibles pour le Roi.

Un des 429 chemins possibles pour le Roi sur un échiquier standard.

Dans cette seconde partie, nous allons essayer de déterminer une formule explicite de la suite $C_n$ . Rien de moins !

Rencontre du 3ème type

Plaçons-nous sur un échiquier à $(n+1) \times (n+1)$ cases. Afin de trouver le nombre $C_n$ de chemins du Roi qui ne dépassent jamais la diagonale principale, nous allons commencer par définir d’autres types de chemins qui, eux, seront plus simples à dénombrer. Plus précisément, voici les trois types de chemins que nous allons étudier:

■ Les chemins simples: ce sont les chemins allant de $(0,0)$ à $(n,n)$ sans contrainte particulière (si ce n’est qu’à chaque étape, le Roi ne se déplace que vers la droite ou vers le haut). Nous noterons $S_n$ le nombre total de chemins simples.

Exemple de chemin simple.

■ Les chemins légaux: ce sont les chemins allant de la case $(0,0)$ à la case $(n,n)$ qui ne dépassent jamais la diagonale principale. Comme nous l’avons dit, nous appelons $C_n$ la nombre total de chemins légaux.

roi_des_catalans2_exemple_de__chemin_legal

Exemple de chemin légal.

■ Les chemins illégaux: ce sont les chemins allant de $(0,0)$ à $(n,n)$ qui dépassent au moins une fois la diagonale principale. Nous noterons $I_n$ le nombre total de chemins illégaux.

Un exemple de chemin illégal. (Mais que fait la police ?)

Vous l’avez sans doute compris, notre problème de départ revient donc à déterminer le nombre de chemins légaux $C_n$ . Comme tout chemin simple est soit un chemin légal, soit un chemin illégal, on en déduit la relation suivante:

$S_n = C_n + I_n$

Ainsi, pour déterminer le nombre $C_n$ , il va nous falloir déterminer le nombre de chemins simples et le nombre de chemins illégaux.

Les chemins simples

Déterminer le nombre $S_n$ de chemins simples va être quelque chose de plutôt… simple (cette blague est tellement drôle que je songe sérieusement à renommer ce blog en blaguedemaths). Lorsque le Roi effectue un chemin simple, il effectue au total exactement $n$ déplacements vers la droite et $n$ déplacement vers le haut. En fait, si on note $D$ chaque fois que le Roi se déplace vers la droite et $H$ chaque fois que le Roi se déplace vers le haut, on peut alors représenter un chemin simple par une suite de $2n$ lettres contenant $n$ fois la lettre $D$ et $n$ fois la lettre $H$ . Par exemple, sur un échiquier standard (c’est-à-dire pour $n=7$ ), voici un exemple de suite représentant un chemin simple du Roi:

$D H D D D H H D H H D D H H$

et voici le chemin que cette suite représente:

Si on revient à un échiquier quelconque, on peut dire que déterminer le nombre de chemins simples revient à déterminer le nombre de suites de $2n$ lettres contenant $n$ fois la lettre $D$ et $n$ fois la lettre $H$ . Pour choisir une telle suite, on peut commencer par placer $n$ lettres $D$ parmi les $2n$ emplacements possibles de cette suite. Cela donne ${2n \choose n}$ possibilités. Une fois toutes les lettres $D$ placées, il n’y a guère plus le choix pour placer les $H$ . Ainsi, nous voyons que le nombre de chemins simples vaut

$\displaystyle S_n = {2n \choose n}$

Les chemins illégaux

Déterminer le nombre de chemins illégaux va nous demander d’être beaucoup plus astucieux. L’idée va être la suivante: puisqu’on ne sait finalement bien dénombrer que des chemins simples, nous allons construire une bijection allant de l’ensemble des chemins illégaux vers l’ensemble des chemins simples d’un certain échiquier qui, lui, sera rectangulaire (et non pas carré !). Plus précisément, à tout chemin illégal, nous allons lui associer un chemin « symétrique » grâce à ce que j’appelle personnellement l’astuce du miroir.

Miroir, mon beau miroir…

Considérons un chemin illégal. Puisqu’il est illégal, il passera à un moment donné par au moins une case située dans la zone interdite et la première case illégale par laquelle il passera aura des coordonnées de la forme $(k-1, k)$ .

En fait, la première case de la zone interdite sur laquelle il passera est toujours située sur la petite diagonale allant de $(0,1)$ à $(n-1,n)$ :

Le « symétrique » de ce chemin illégal désignera le chemin obtenu de la façon suivante:

au départ, tant que le chemin illégal n’a pas encore été dans la zone interdite, le chemin illégal et son « symétrique » seront les mêmes;
à partir du moment où le chemin illégal entre dans la zone interdite (donc à partir de la case $(k-1,k)$ ), on effectue une symétrie axiale par rapport à la petite diagonale pour obtenir le deuxième morceau du chemin « symétrique » (d’où l’expression astuce du miroir).

Voici ci-dessous un exemple sans doute plus parlant que tout mon blabla; à gauche un chemin illégal et à droite son « symétrique »:

Comme vous le constatez, il faut tout de même agrandir l’échiquier d’une ligne sur le haut pour obtenir le chemin « symétrique ». Vous remarquez aussi que ce symétrique a toujours pour point de départ la case $(0,0)$ et pour point d’arrivée la case $(n-1, n+1)$ (qui est la case symétrique de la case d’arrivée $(n,n)$ du chemin illégal).

Enfin, dernière remarque importante: quand vous prenez le « symétrique » d’un « symétrique », vous retombez sur votre chemin de départ !

Il ne nous reste plus qu’à montrer que cette opération est une bijection. Plus précisément, nous allons démontrer la proposition suivante:

A tout chemin illégal allant de $(0,0)$ à $(n,n)$ correspond un et un seul chemin simple allant de $(0,0)$ à $(n-1,n+1)$ par l’astuce du miroir.

La démonstration

Tout d’abord, le « symétrique » d’un chemin illégal est bien un chemin simple car lorsqu’on prend le symétrique d’un chemin illégal, chaque déplacement vers la droite sera transformé en un déplacement vers le haut et chaque déplacement vers le haut sera transformé en un déplacement vers la droite. De plus, nous avons déjà expliqué pourquoi les points de départ et d’arrivée du symétrique sont $(0,0)$ et $(n-1,n+1)$ .

Ensuite, nous allons montrer que tout chemin simple allant de $(0,0)$ à $(n-1,n+1)$ est le symétrique d’au moins un chemin illégal (autrement dit, on montre la surjectivité de notre opération de « symétrie »). Si on prend un chemin simple allant de $(0,0)$ à $(n-1,n+1)$ , alors il traversera nécessairement la petite diagonale au moins une fois, disons en la case $(k-1, k)$ . Si, à partir de ce chemin simple, on prend le chemin obtenu de la même façon que par la méthode de l’astuce du miroir décrite plus haut, alors le chemin obtenu est bien un chemin illégal (et il va de la case $(0,0)$ à la case $(n,n)$ ) dont la première case interdite qu’il franchira est $(k-1,k)$ .

Enfin, montrons que chaque chemin simple allant de $(0,0)$ à $(n-1,n+1)$ ne peut pas être l’image de plus d’un chemin illégal (il s’agit donc de l’injectivité). Rappelez-vous que nous avions noté que quand on prend le « symétrique » du « symétrique », on retrouve le chemin de départ. Donc si deux chemins illégaux ont même « symétrique », en prenant le « symétrique » de ce « symétrique » on doit retrouver le chemin initial mais comme un chemin n’a qu’un seul « symétrique », c’est que les chemins de départ étaient identiques !

Nombres de chemins illégaux

Nous pouvons enfin calculer le nombre $I_n$ de chemins illégaux. Puisqu’il y autant de chemins illégaux que deux chemins simples allant de $(0,0)$ à $(n-1,n+1)$ , il suffit de dénombrer ces derniers pour trouver le nombre de chemins illégaux. Or, un raisonnement similaire à ce qu’on a fait plus haut nous dit qu’un chemin simple allant de $(0,0)$ à $(n-1,n+1)$ est une suite de $2n$ lettres dont $n-1$ lettres D et $n+1$ lettres H. Ainsi,

$\displaystyle I_n = {2n \choose n-1}$

ou encore $\displaystyle I_n = {2n \choose n+1}$

Les chemins légaux

Le nombre de chemins légaux, c’est-à-dire la réponse à notre problème de départ, est alors facile à déterminer. Puisque

$C_n = S_n - I_n$

on en déduit que

$\displaystyle C_n = {2n \choose n} - {2n \choose n+1}$

Ainsi, on a

$C_n = \dfrac{(2n)!}{(2n-n)! n!} - \dfrac{(2n)!}{(2n - (n+1)) ! (n+1)!}$

donc

$C_n = \dfrac{(2n)!}{n! n!} - \dfrac{(2n)!}{(n-1) ! (n+1)!}$

En remarquant que $(n-1)! (n+1)! = n! n! \times \dfrac{n+1}{n}$ , on en déduit que:

$C_n = \dfrac{(2n)!}{n! n!} - \dfrac{n}{n+1} \times \dfrac{(2n)!}{n! n!}$

c’est-à-dire:

$\displaystyle C_n = {2n \choose n} - \frac{n}{n+1} {2n \choose n}$

En factorisant, on obtient:

$\displaystyle C_n = \left( 1 - \frac{n}{n+1} \right) {2n \choose n}$

ce qui nous donne enfin la formule tant attendue pour les nombres de Catalan (que nous avons bien mérité d’obtenir après tant d’efforts !):

$\boxed{ \displaystyle C_n = \frac{1}{n+1} {2n \choose n} }$

Par exemple, pour un échiquier standard ( $n=7$ ), on obtient

$\displaystyle C_7 = \frac{1}{7+1} {14 \choose 7 } = \frac{1}{8} \times 3432 = 429$

ce qui était bien ce qu’on avait déjà trouvé !

Utilisation des nombres de Catalan

On ne retrouve pas les nombres de Catalan seulement sur un échiquier mais aussi dans une multitude de situations ! En fait, si on analyse ce qu’on a fait dans cet article, les nombres de Catalan permettront (entre autres) de dénombrer toute liste d’éléments composée de deux types d’éléments « A » et « B » telle que:

il y a autant de $A$ que de $B$ ;
à chaque étape quand on parcourt la liste de la gauche vers la droite, il y a toujours plus (ou autant) de $A$ que de $B$

Dans notre exemple, un chemin du Roi qui ne traverse pas la diagonale n’est rien d’autre qu’une suite de $n$ déplacements vers la droite (D) et de $n$ déplacements vers le haut (H) telle qu’à chaque étape, il y a toujours plus (ou autant) de D que de H (si à un moment il y a plus de H que de D, c’est qu’on est entré dans la zone interdite !).

Autre exemple: on voit que les nombres de Catalan permettent de dénombrer facilement le nombre de façons de disposer $n$ paires de parenthèses car lorsqu’on place des parenthèses, il faut que:

il y ait autant de parenthèses ouvrantes « ( » que fermante « ) »
à chaque étape quand on lit une expression de la gauche vers la droite, il y a toujours plus ou autant de parenthèses ouvrantes « ( » que de parenthèses fermantes « ) ».

Ainsi, il y a $C_n$ façons de disposer $n$ paires de parenthèses.

roi_des_catalans2_les_14_facons_de_placer_4_paires_de_parentheses

Les C₄ = 14 façons de placer 4 paires de parenthèses.

Un dernier exemple, pour la route…

Un autre exemple un peu moins trivial avec des parenthèses est le suivant: imaginons une opération qui n’est pas associative (par exemple le produit vectoriel). De combien de façons différentes peut-on interpréter le calcul du produit suivant ?

$A \times B \times C \times D$

Par exemple, une façon d’interpréter ce calcul est:

$((A \times B) \times (C \times D))$

ou bien:

$(A \times (B \times (C \times D))$

On peut remarquer que pour se donner une expression, il suffit de savoir où sont placées les parenthèses ouvrantes ainsi que les produits; le reste (les parenthèses fermantes et les variables) est alors entièrement déterminé. Par exemple, si je vous donne l’expression

$(\times (( \times \times$

alors on place les variables $A$ , $B$ et $C$ à gauche des signes $\times$ et la variable $D$ à droite du dernier signe $\times$ :

$(A\times((B\times C \times D$

Ensuite, il n’y a plus guère le choix pour placer les parenthèses fermantes de façon à ce que l’expression ait du sens:

$(A\times((B\times C) \times D))$

(en fait, on commence par fermer la parenthèse ouvrante la plus « intérieure » et on continue comme cela jusqu’à la parenthèse ouvrante la plus « extérieure »).

Tout cela pour dire que, pour se donner une expression valide, il suffit de se donner une suite de $($ et de $\times$ telle que:

il y a au total autant de parenthèses ouvrantes $($ que de symboles $\times$
à chaque étape quand on lit l’expression de gauche à droite, il y a plus ou autant de parenthèses ouvrantes $($ que de signes $\times$

D’après ce qu’on a dit plus haut, le nombre d’expressions de ce type possédant 3 parenthèses ouvrantes et 3 symboles $\times$ est donné par le nombre de Catalan $C_3 = 5$ . Voici toutes les possibilités:

$( \times ( \times ( \times$
$( \times (( \times \times$
$((\times \times ( \times$
$(( \times ( \times \times$
$((( \times \times \times$

et voici les 5 expressions possibles qu’elles donnent:

$( A\times ( B \times ( C \times D)))$
$( A\times (( B\times C) \times D))$
$((A\times B) \times ( C \times D))$
$(( A \times ( B\times C)) \times D)$
$((( A \times B) \times C) \times D)$

Bien entendu, on peut généraliser cela de la façon suivante:

Le nombre de façons de parenthéser l’expression $x_1 \times x_2 \times \cdots \times x_n$ est $C_{n-1}$

Bref, on pourrait parler des nombres de Catalan encore pour longtemps car ils apparaissent souvent lorsqu’on fait du dénombrement ! J’espère juste que le Roi sur son échiquier ne m’en voudra pas trop de l’avoir mis entre parenthèses…

Notes:

A voir: la page Wikipédia catalane sur les nombres de Catalan.
Ce que j’ai appelé l’astuce de miroir s’appelle en Anglais le principe de réflexion d’André.
Les nombres de Catalan apparaissent vraiment dans beaucoup de domaines. Si vous voulez des dizaines d’interprétations différentes des nombres de Catalan (et pas seulement l’échiquier), vous pouvez consulter cette liste.

5 commentaires pour Le Roi des Catalans (2ème partie)

Ping : Le Roi des Catalans (1ère partie) | Blogdemaths
projetmbc dit :

19 septembre 2016 à 10 h 12 min

Belle preuve très accessible !

Pour info., on peut aussi utiliser les séries formelles pour obtenir une formule des nombres de Catalan : voir ce (pdf)[https://webusers.imj-prg.fr/~antoine.ducros/catalan.pdf] .

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  19 septembre 2016 à 18 h 00 min
  
  En voilà une preuve astucieuse ! Merci pour ce lien 🙂
  
  J’aimeJ’aime
  
  Réponse
projetmbc dit :

19 septembre 2016 à 16 h 06 min

J’allais oublié un exemple sympa et « montagnard » où les nombres de Catalan apparaissent : les chemins de Dyck.

J’aimeJ’aime

Réponse
Arles dit :

21 octobre 2022 à 9 h 59 min

Bravo pour votre effort de vulgarisation. J’ai appris de belles choses. Continuez ! Merci.

J’aimeJ’aime

Réponse

Votre commentaire Annuler la réponse.

Entrez votre commentaire...

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

E-mail (adresse strictement confidentielle)

Nom

Site web

Vous commentez à l’aide de votre compte WordPress.com. ( Déconnexion / Changer )

Vous commentez à l’aide de votre compte Facebook. ( Déconnexion / Changer )

Annuler

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.