L'atelier de la patience

Ce que mesure le nombre de tas

Deux cartes d'une même suite croissante ne peuvent jamais finir sur le même tas, puisque la seconde, plus haute, n'a pas le droit de se poser sur la première. Il faut donc au moins autant de tas que la plus longue suite croissante. Et la stratégie de la patience n'en ouvre jamais davantage : en suivant, depuis le dernier tas, le dessus du tas voisin de gauche au moment de chaque pose, on remonte une suite croissante qui traverse tous les tas. C'est le fil doré de la table.

Avec 52 cartes distinctes bien battues, on obtient 11 ou 12 tas en moyenne, autour de 2√52 ≈ 14,4 moins une correction : la loi exacte des fluctuations est celle de Tracy et Widom, la même que pour la plus grande valeur propre d'une grande matrice aléatoire (Baik, Deift et Johansson, 1999).

La règle des cartes de même valeur

Un vrai jeu répète ses valeurs : quatre as, quatre deux… Un jeu se décrit alors par ses séries, de longueurs L₁, L₂, …, chacune contenant les valeurs 1 à L. Le jeu réel, c'est quatre séries de 13. Il faut décider si une carte peut se poser sur une carte de même valeur. Si oui, les tas comptent la plus longue suite strictement croissante, et ne dépassent jamais le nombre de valeurs distinctes. Si non, ils comptent la plus longue suite croissante au sens large, et valent au moins le plus grand nombre d'exemplaires d'une même valeur.

La correspondance de Robinson–Schensted–Knuth donne la répartition exacte : elle associe chaque mélange à un tableau de Young de forme λ, et le nombre de mélanges de forme λ vaut

f_λ · K_λ,μ

où f_λ se calcule par la formule des équerres et K_λ,μ est un nombre de Kostka, qui compte les tableaux remplis avec les multiplicités μ du jeu. La règle d'égalité choisit simplement le sens de lecture : égal permis, on compte les lignes de λ ; égal interdit, la longueur de sa première ligne.

Les mélanges à l'américaine

Un paquet neuf est rangé : chaque série en ordre croissant. Un mélange à l'américaine coupe le paquet en deux et entrelace les moitiés ; après k mélanges, le paquet n'est fait que d'au plus 2^k séries montantes entrelacées. La patience voit cet ordre résiduel : sur 52 cartes distinctes, on passe d'environ 31 tas après un mélange à 14 après quatre, et il faut 6 ou 7 mélanges pour retrouver la valeur d'un paquet parfaitement battu. C'est l'écho, en tas, du résultat de Bayer et Diaconis : environ sept mélanges suffisent à battre un jeu.

Les vérifications de ces formules, et leurs liens avec les marcheurs vicieux et les tours de Hanoï, sont dans le Carnet Mathématique, aux fiches L·108 à L·111.

Références

• D. Aldous et P. Diaconis, « Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem », Bulletin of the American Mathematical Society, vol. 36, 1999, p. 413-432.
• J. Baik, P. Deift et K. Johansson, « On the distribution of the length of the longest increasing subsequence of random permutations », Journal of the American Mathematical Society, vol. 12, 1999, p. 1119-1178.
• D. E. Knuth, « Permutations, matrices, and generalized Young tableaux », Pacific Journal of Mathematics, vol. 34, 1970, p. 709-727.
• D. Bayer et P. Diaconis, « Trailing the dovetail shuffle to its lair », The Annals of Applied Probability, vol. 2, 1992, p. 294-313.
• OEIS A047874 : permutations de n selon la longueur de leur plus longue sous-suite croissante.