Home   Catalan   Le Roi des Catalans (1ère partie)

Le Roi des Catalans (1ère partie)

Un Roi situé sur la case tout en bas à gauche d’un échiquier souhaite (pour des raisons personnelles que nous ne détaillerons pas ici) se rendre sur la case située tout en haut à droite.Roi_des_Catalans_figure_initialeContrairement au jeu d’Échecs où il peut se déplacer d’une case dans toutes les directions, notre Roi ne pourra ici se déplacer que d’une case vers la droite ou d’une case vers le haut à chaque fois.Roi_des_Catalans_deplacements_possibles_du_RoiEn plus de ça, notre Roi ne peut pas aller dans la partie haute de l’échiquier (trop fainéant), c’est-à-dire qu’il devra rester toujours en-dessous ou sur la diagonale principale:Roi_des_Catalans_figure_initiale_contrainte_de_la_diagonale(Remarquez au passage la belle illusion d’optique créée par cette figure…)

Voici donc la question qui va nous intéresser: de combien de façons un Roi sur un échiquier partant de la case la plus en bas à gauche peut-il rejoindre la case la plus en haut à droite en se déplaçant à chaque étape uniquement soit d’une case vers la droite, soit d’une case vers le haut, sans jamais aller au-delà de la diagonale principale ?

Nous verrons que ce problème d’apparence anecdotique renferme en fait une des suites de nombres les plus intéressantes en mathématiques.

Généralisation

En bons mathématiciens que nous sommes, nous voyons qu’il n’y a aucune raison de se restreindre à un échiquier de 8 cases par 8 cases. D’une part, parce qu’il est plus facile de comprendre et de résoudre ce problème si les échiquiers sont plus petits (on peut considérer des échiquiers de 1 par 1, ou de 2 par 2 pour commencer) et d’autre part, parce que vous n’êtes pas curieux de savoir ce qui se passe pour un échiquier de 9, 10 ou même 30 000 cases de côté ? Moi, si…

Si on reformule notre problème de façon plus générale, cela donne: si n est un entier naturel, et si on place le Roi sur un échiquier de (n +1) \times (n +1) cases, de combien de façons peut-il aller de la case (0,0) à la case (n,n) sans jamais aller au-dessus de la diagonale principale ?

Nous appellerons C_n ce nombre de chemins et notre but va être de déterminer le nombre C_7 (qui correspond au nombre de chemins sur un échiquier standard de 8 par 8).

Quelques cas particuliers

Comme on l’a dit, pour comprendre cette suite (C_n) le mieux est encore de regarder comment elle se comporte pour de petites valeurs de n. Je vous propose donc de commencer par voir ce qui se passe pour n=0. Car, non, il n’y a rien de honteux à commencer à n=0. On a tous un ami, ou un proche qui a commencé à n=0 un jour dans sa vie.Roi_des_Catalans_n_egale_0Nous voyons donc qu’il n’y a qu’un seul chemin, celui qui consiste à ne pas se déplacer puisqu’on est déjà sur la case d’arrivée dès le départ ! Ainsi, C_0=1. Passons au cas n=1, qui correspond à un échiquier de 2 par 2:Roi_des_Catalans_n_egale_1_videEt nous voyons facilement qu’il n’y a qu’un seul chemin possible:Roi_des_Catalans_n_egale_1_avec_parcoursNous venons de démontrer, non sans fierté, que C_1 = 1. Et pour n=2 alors ? Eh bien sortons un échiquier de 3 cases sur 3 cases et comptons:Roi_des_Catalans_n_egale_2On voit alors qu’il n’y a que deux chemins possibles donc C_2 = 2.

La marche de l’empereur

Vous pouvez vous amuser à compter tous les chemins pour n=3, 4, 5, mais à partir de n=6 cela commence à devenir fastidieux. Alors imaginez pour n=7… Donc, plutôt que de compter tous les chemins, nous allons plutôt essayer de trouver une relation de récurrence vérifiée par la suite (C_n) afin de laisser le soin à un ordinateur de faire le calcul à notre place (y a pas que le Roi qui est fainéant !)

Supposons que nous connaissions déjà C_0, C_1, C_2, …, C_n et essayons de voir comment en déduire C_{n+1}. Il nous faut pour cela nous placer sur un échiquier à (n+2) \times (n+2) cases:Roi_des_Catalans_echiquier_C_n_plus_1_videTout d’abord, si un chemin va de (0,0) à (n+1, n+1), il passera au moins une fois par la diagonale principale autrement qu’en (0,0) (au pire, en (n+1,n+1)). Considérons un chemin quelconque, et notons k>0 le plus petit entier strictement positif tel que ce chemin passe par la case caca… pardon, (k,k):Roi_des_Catalans_echiquier_C_n_plus_1_CACALOLAinsi, avant la case (k,k) aucune case de la diagonale n’est visitée (hormis (0,0) bien sûr). Après cette case, une ou plusieurs cases de la diagonale pourront être traversées. Notre but va être de dénombrer combien de tels chemins passant par (k,k) sont possibles. Mais avant cela, pour bien comprendre la situation, voici un exemple de tel chemin:Roi_des_Catalans_echiquier_C_n_plus_1_exemple_de_cheminCe chemin peut être décomposé en deux morceaux: un chemin allant de (0,0) à (k,k) (en bleu sur le schéma ci-dessous) et un chemin allant de (k,k) à (n+1,+1) (en vert sur le schéma):Roi_des_Catalans_echiquier_C_n_plus_1_exemple_avec_chemins_bleu_et_vertPour obtenir le nombre total de chemins passant pour la première fois sur la diagonale en (k,k), il suffira de faire le produit du nombre de chemins bleus possibles par le nombre de chemins verts possibles.

Dénombrement des chemins bleus

Pour dénombrer tous les chemins allant de (0,0) à (k,k) qui ne passent par aucune case de la diagonale principale, il faut d’abord remarquer deux choses:

  1. Puisque le Roi ne se déplace que vers la droite ou vers le haut, alors le tout premier déplacement qu’il effectue au départ est nécessairement vers la droite, donc vers la case (1,0).
  2. Pour la même raison, lorsque le Roi arrive à la case (k,k), c’est forcément en provenance de la case située juste en dessous, c’est-à-dire de la case (k,k-1).

Roi_des_Catalans_echiquier_C_n_plus_1_chemins_bleus_cases_forceesPuisque ces deux déplacements sont forcés, pour déterminer le nombre de chemins bleus il suffit de déterminer tous les chemins allant de (1,0) à (k,k-1) qui ne passent pas par la diagonale principale.Roi_des_Catalans_echiquier_C_n_plus_1_chemins_bleus_sous_echiquierCela revient donc à déterminer tous les chemins ne dépassant pas la diagonale principale d’un sous-échiquier à k \times k cases. Par définition, il y a donc C_{k-1} chemins bleus.

Dénombrement des chemins verts

Le dénombrement des chemins verts est beaucoup plus immédiat. En effet, un chemin vert est un chemin allant de (k,k) à (n+1,n+1) qui ne va pas au-delà de la diagonale (mais qui peut tout à fait passer sur celle-ci).Roi_des_Catalans_echiquier_C_n_plus_1_chemins_verts_sous_echiquierIl y a donc autant de chemins verts que de chemins ne dépassant pas la diagonale dans un échiquier de ((n+1)-k+1) \times ((n+1)-k+1) cases, c’est-à-dire C_{n-k+1} chemins, par définition.

Dénombrement final

D’après ce que nous venons de voir, il y a donc C_{k-1} \times C_{n-k+1} chemins allant de (0,0) vers (n+1,n+1) ne passant jamais au-dessus de la diagonale et passant pour la première fois sur celle-ci en (k,k).Roi_des_Catalans_echiquier_C_n_plus_1_denombrement_finalAinsi, si on prend un chemin quelconque, alors:

  • Soit la première case de la diagonale par laquelle il passe est (1,1) (c’est-à-dire k=1), ce qui donne C_{1-1} \times C_{n-1+1} = C_0 \times C_{n} possibilités;
  • Soit la première case de la diagonale par laquelle il passe est (2,2), ce qui donne C_1 \times C_{n-1} possibilités;
  • Soit la première case de la diagonale par laquelle il passe est (3,3), ce qui donne C_2 \times C_{n-2} possibilités;
  • etc.
  • Soit la première case de la diagonale par laquelle il passe est (n+1,n+1), ce qui donne C_n \times C_{0} possibilités.

Puisque tous ces cas sont disjoints, le nombre total de chemins est donc:

C_{n+1}  = C_0 \times C_n + C_1 \times C_{n-1} + C_2 \times C_{n-2} + \cdots + C_n \times C_0

ce qu’on peut réécrire sous la forme plus compacte et plus jolie suivante:

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

Le calcul pour un échiquier standard

Par exemple, si on souhaite calculer C_3, on écrira:

C_3 = C_0 \times C_2 + C_1 \times C_1 + C_2 \times C_0

Comme nous avions vu que C_0 = 1, C_1 = 1 et C_2 = 2, alors:

C_3 = 1 \times 2 + 1 \times 1 + 2 \times 1 = 5

De la même façon, on peut facilement calculer le nombre chemins sur un échiquier de 8 par 8, mais comme les ordinateurs font ça beaucoup mieux que nous, il est préférable d’écrire un petit programme (non optimal), qui nous dit que C_7 = 429. Et voilà, nous avons la réponse à notre question de départ !

Pour le plaisir, on peut s’amuser à calculer les valeurs suivantes de cette suite:

n C_n
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
13 742900
14 2674440

Enquête de satisfaction

Nous avons donc réussi à trouver une formule de récurrence pour la suite (C_n) mais, franchement, pensez-vous vraiment que nous allons nous satisfaire de cela ? Nous valons mieux que ça, voyons… visons plus haut ! Pourquoi ne pas essayer de trouver une formule explicite de cette suite ? C’est ce que nous tenterons de faire dans la deuxième partie de cet article… ce qui nous donnera l’occasion de faire encore plus de dénombrement !

Note:

Les nombres C_n que nous avons étudiés dans cet article s’appellent les nombres de Catalan, du mathématicien Eugènes Charles Catalan, qui, comme son nom ne l’indique pas, était un mathématicien franco-belge.


اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

Get Best Services from Our Business.