Permutations triées et/ou triables

Le thème général de cet exposé est l'étude de plusieurs problèmes d'énumération liés à une procédure de tri de permutations initialement décrite par Knuth, et reprise plus récemment par West. Notre approche de ces problèmes, inspirée d'un article de Zeilberger, fait apparaître des équations fonctionnelles aux différences divisées, naturelles dans de nombreux problèmes d'énumération, mais qu'on ne sait la plupart du temps pas résoudre. Ainsi, les équations que nous obtenons - et pour certaines, résolvons - ont un intérêt propre qui déborde celui des questions énumératives initiales, dont voici pour finir une description. La procédure de tri de Knuth utilise une pile. Knuth avait caractérisé et compté les permutations triables par un passage dans la pile. Comme chacun le sait, il n'y a qu'une suite de nombres en combinatoire, et le nombre de telles permutations de longueur n est le n-ième nombre de Catalan. Plus généralement, on peut chercher à caractériser et compter les permutations de longueur n triables par k passages dans la pile (dites k-triables), ou celles qui apparaissent en sortie de pile, que nous appelons (abusivement) triées.