Combinatorics of patience sorting piles

Details Combinatorics of patience sorting piles Combinatorics of patience sorting piles

2005-06-17

arxiv.org/abs/math/0506358v3

Mathematics

Combinatorics

19 pages, LaTeX; uses pstricks; view PS, not DVI; use dvips + ps2pdf, not dvi2pdf; part of FPSAC'05 proceedings; v3: final jou

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Combinatorics of patience sorting piles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Combinatorics of patience sorting piles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorics of patience sorting piles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-448281