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.Contrairement 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.En 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:(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.Nous 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:Et nous voyons facilement qu’il n’y a qu’un seul chemin possible:Nous 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:On 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:Tout 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)$ :Ainsi, 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:Ce 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):Pour 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:

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

Puisque 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.Cela 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).Il 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)$ .Ainsi, 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.

8 commentaires pour Le Roi des Catalans (1ère partie)

Anonyme dit :

14 mai 2016 à 23 h 00 min

Merci pour cet article très intéressant et très bien expliqué.
Je vous signale juste une petite coquille dans le cas n=2, vous avez tapé C2=3
Encore merci pour ce partage…

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  14 mai 2016 à 23 h 05 min
  
  Voilà qui est corrigé !
  Merci pour votre message, je suis content de voir que cet article vous a plu !
  
  J’aimeJ’aime
  
  Réponse
Ping : un chemin allant de (0, 0) à (k, k), un allant de (k, k) à (n + 1, n + 1) | Colours in Black and White
Anonyme dit :

18 juin 2016 à 19 h 06 min

Je crois qu’il y a un moyen plus simple de résoudre le problème : un chemin qui va de (0,0) à (n,n) en passant dans le rouge peut être envoyé sur un chemin qui va de (0,0) à (n-1,n+1) en appliquant une réflexion par rapport à la droite (m,m+1) uniquement sur la partie du chemin après le premier temps où le chemin entre dans le rouge. Réciproquement, un chemin qui va de (0,0) à (n-1,n+1) entre nécessairement dans le rouge, et par la même application peut être envoyé sur un chemin de (0,0) à (n,n) qui passe dans le rouge. Ainsi ces deux ensembles de chemins ont même cardinal, et en laissant au lecteur le soin de compléter les trous pour ne pas spoiler la suite, on arrive très rapidement au résultat que tu devrais donner dans ta deuxième partie…

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  18 juin 2016 à 20 h 51 min
  
  C’est effectivement ce que je comptais expliquer dans la 2eme partie de cet article… Bien vu !
  
  J’aimeJ’aime
  
  Réponse
Ping : Le Roi des Catalans (2ème partie) | Blogdemaths
projetmbc dit :

19 septembre 2016 à 9 h 56 min

Bonjour.

Comment ont été fait les graphiques avec les échiquiers car je les trouve sympas ?

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  19 septembre 2016 à 17 h 59 min
  
  Je les ai fait en LaTeX, à l’aide du très utile package Chessboard que vous pouvez trouver là:
  
  https://www.ctan.org/pkg/chessboard
  
  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.