Combinatorics of patience sorting piles

MaRDI QIDQ2654575zbMATH OpenFDO

Authors Alexander Burstein, Isaiah Lankham

Publication date 19 January 2010

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0506358, http://www.emis.de/journals/SLC/wpapers/s54Aburlank.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Bell numbersset partitionsgeneralized permutation patternspatience sortingbasic subsequencesleft-to-right minima subsequencesshadow diagrams

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Partitions of sets (05A18) Combinatorial aspects of representation theory (05E10)

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-�ar{1}-42) of permutations that avoid the generalized permutation pattern 2-31 unless it is part of the generalized pattern 3-1-42.

Recommendations

• Restricted patience sorting and barred pattern avoidance
• A geometric form for the extended patience sorting algorithm
• Combinatorics of patience sorting monoids
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• scientific article; zbMATH DE number 2107707

Cited in

(9)

• The monoids of the patience sorting algorithm
• Space-efficient algorithms for longest increasing subsequence
• Space-efficient algorithms for longest increasing subsequence
• A geometric form for the extended patience sorting algorithm
• Random matrix theory and its applications
• Asymptotically fastest sorting algorithm for almost sorted arrays
• Restricted patience sorting and barred pattern avoidance
• Descents and des-Wilf equivalence of permutations avoiding certain nonclassical patterns
• Combinatorics of patience sorting monoids

This page was built for publication: Combinatorics of patience sorting piles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2654575)