« Plus fort ! » — le score d'une liste de cartes

Soit $n \geq 3$ un entier. Un joueur dispose de $n$ cartes numérotées de $1$ à $n$. Il les mélange puis note, dans l'ordre, la suite des numéros obtenue : on appelle cela une liste de longueur $n$. Par exemple, avec $n=8$, une liste possible est $L=[2,5,7,6,1,8,4,3]$.

Avec une liste donnée, le joueur marque un point chaque fois que le numéro d'une carte est strictement supérieur à celui de la carte précédente (par exemple, avec $L=[2,5,7,6,1,8,4,3]$, le joueur marque 3 points : aux passages $2\to5$, $5\to7$, $1\to8$). Le nombre de points marqués est appelé le score de la liste.

On note $L_n(k)$ le nombre de listes de longueur $n$ ayant pour score $k$.

Calculer $L_3(k)$, $L_4(k)$ et $L_5(k)$ pour toutes les valeurs possibles de $k$.

Le score d'une liste de longueur $n$ vaut entre $0$ (liste strictement décroissante) et $n-1$ (liste strictement croissante), donc $L_n(0)=L_n(n-1)=1$.

Pour passer de $n$ à $n+1$, on insère la carte $n+1$ (la plus grande de toutes) à l'une des $n+1$ positions possibles d'une liste de longueur $n$ de score $k$. Comme $n+1$ est toujours strictement supérieure à ce qui la précède, on établit la récurrence suivante (nombres dits « eulériens ») :

En partant de $L_2(0)=L_2(1)=1$, on obtient :

On vérifie que la somme de chaque ligne vaut bien $n!$ : $1+4+1=6=3!$, $1+11+11+1=24=4!$, $1+26+66+26+1=120=5!$. ✓