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 ?

roi_des_catalans2_rappel_du_problemeNous 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.

roi_des_catalans2_un_des_429_chemins

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.

Un exemple de chemin simple.

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 ?)

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:roi_des_catalans2_exemple_de_chemin_simple_correspondant_a_une_suite_de_lettres

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).roi_des_catalans2__chemin_illegal_avec_1ere_case_interdite

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):roi_des_catalans2_petite_diagonale

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 »:roi_des_catalans2_chemin_illegal_et_son_symetrique

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 C4 = 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:

Advertisements
Cet article, publié dans Dénombrement, est tagué , , , , , . Ajoutez ce permalien à vos favoris.

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

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

  2. projetmbc dit :

    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] .

  3. projetmbc dit :

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

Laisser un commentaire

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

Logo WordPress.com

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

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

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

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s