Paire de tableaux (P,Q)

Après ces deux cas extrêmes examinons maintenant les cas intermédiaires, dans l'ordre décroissant des valeurs x à insérer. Dans chaque cas on part de la figure en haut à droite de cette page, et on choisit x = 25 ou bien x = 16 ou bien x = 12 etc.

Chacune des cellules numérotées 25, 16, 12 a glissé vers la gauche en entraînant derrière elle 0, 1 ou 2 colonnes respectivement ; une fois sa place trouvée dans la ligne 1, la cellule ne bouge plus et forme un L à l'envers avec la colonne qui est à sa droite (par exemple sur la figure de droite qui correspond à x = 12 ce L inversé est colorié en rouge). Les colonnes suivantes (en allant vers la gauche) continuent à glisser vers le bas mais la nouvelle cellule immobilisée ligne 1 introduit une perturbation : les colonnes glissent en ligne brisée — l'illustration la plus claire est la colonne bleue de base 9 sur la figure de droite (x = 12) — jusqu'à ce que l'une d'entre elles glisse sans se briser, c'est-à-dire sans emprunter de cellule à sa voisine de droite ; les colonnes suivantes sont alors translatées vers le bas, la perturbation ne se fait plus sentir. Illustrations :

• sur la figure de gauche (x = 25) la cinquième colonne, de base 19, s'est brisée en glissant (elle a emprunté la cellule 33 à la sixième colonne et la cellule 36 est restée en place), après quoi les colonnes 4, 3, 2 et 1 ont glissé normalement ;
• sur la figure du milieu (x = 16) la quatrième colonne, de base 14, s'est brisée en glissant, de même que la troisième de base 9 (si, si, elle a récupéré la cellule 34 qui était en haut de la colonne 4), après quoi les colonnes 2 et 1 ont glissé normalement ;
• sur la figure de droite (x = 12) les colonnes 3, 2 et 1 se sont brisées.

Sur l'animation Flash les différences entre glissements en lignes brisées et glissements (totalement) verticaux sont toujours évidentes, alors que sur les clichés de cette page il faut être parfois plus attentif pour distinguer les deux. Voici les deux derniers cas (x = 8 et x = 5) sans commentaire (comme à la télé c'est peut-être mieux ainsi) :

L'explication de la structure des glissements lors des réductions successives est simple : la trace laissée par les cellules qui glissent lors d'une réduction — ces traces sont coloriées sur les clichés de cette page — impose de fortes contraintes au déroulement de la réduction suivante. Si deux cellules a et b sont voisines dans la même ligne on a par définition d'un tableau a ≤ b, et si b glisse verticalement lors d'une réduction, elle ne peut pas glisser horizontalement lors de la réduction suivante, car elle se retrouverait en-dessous de la cellule a et la colonne ne serait pas strictement croissante.

Le bilan dans tous les cas est que les cellules vertes (ici il y en a six) qui marquent les points de départ des réductions successives se retrouvent distribuées en haut des colonnes sauf une : il n'y a jamais deux cellules vertes empilées dans la même colonne après une réduction. La colonne exceptionnelle — celle qui n'est pas coiffée par une cellule verte — semble avoir grandi vers le haut si on la compare à la même colonne avant exécution du jeu de taquin. Ceci explique que la forme du tableau T' obtenu par insertion d'une valeur x dans le tableau de départ T contienne la forme de T.

Pour inverser les réductions qui transforment le tableau T en T' il suffit de dilater T' en cliquant (Shift+clic) sur les cellules vertes en haut des colonnes, de gauche à droite. Comme il y a une seule colonne non coiffée par une cellule verte il suffit de mémoriser son numéro.

Revenons à l'exemple de la permutation 3 7 4 1 2 6 5 (cf page précédente), la suite croissante de diagrammes obtenus lors des insertions successives :