Séminaire Lotharingien de Combinatoire, B54Ab (2006), 19 pp.

Alexander Burstein and Isaiah Lankham

Combinatorics of Patience Sorting Piles

Abstract. Despite having been introduced in 1962 by C.L. Mallows, the combinatorial algorithm Patience Sorting is only now beginning to receive significant attention due to such recent deep results as the Baik-Deift-Johansson Theorem that connect it to fields including Probabilistic Combinatorics and Random Matrix Theory. The aim of this work is to develop some of the more basic combinatorics of the Patience Sorting Algorithm. In particular, we exploit the similarities between Patience Sorting and the Schensted Insertion Algorithm in order to do things that include defining an analog of the Knuth relations and extending Patience Sorting to a bijection between permutations and certain pairs of set partitions. As an application of these constructions we characterize and enumerate the set S_n(3-1^--42) of permutations that avoid the generalized permutation pattern 2-31 unless it is part of the generalized pattern 3-1-42.

Résumé. En dépit de l'introduction en 1962 par C.L. Mallows, l'algorithme combinatoire Patience Sorting commence seulement maintenant à susciter l'attention significative dû à des résultats profonds récents, tels que le théorème de Baik-Deift-Johansson, qui le relient à la combinatoire probabiliste et à la théorie des matrices aléatoires. On développe une partie plus fondamentale de la combinatoire de l'algorithme de Patience Sorting. En particulier, on utilise les similarités entre Patience Sorting et la correspondance de Schensted pour définir un analogue des relations de Knuth et pour généraliser Patience Sorting à une bijection entre les permutations et certaines paires de partitions d'ensemble. Comme application de ces constructions on caractérise et énumère l'ensemble S_n(3-1^--42) des permutations qui évitent le motif de permutation généralisé 2-31 à moins qu'il soit partie du motif généralisé 3-1-42.

Received: June 17, 2005. Accepted: December 23, 2005. Final Version: March 29, 2006.

The following versions are available: