Math Park - 09/11/13 - Valentin Feray, Sous suite croissante d'une permutation aléatoire
Channel: Institut Henri Poincaré
Date: 2013-11-09

Combien de cartes faut-il déplacer au minimum pour trier un jeu de cartes mélangé ? Reformulée en termes mathématiques, cette question amène à regarder la longueur de la plus longue sous-suite croissante d'une permutation aléatoire. Bien que simple à formuler, ce problème fait apparaître de nombreux outils mathématiques plus ou moins sophistiqués : double-compte, principe des tiroirs, tirage de points aléatoires...