Restricted Patience Sorting and Barred Pattern Avoidance

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Patience Sorting is a combinatorial algorithm that can be viewed as an iterated, non-recursive form of the Schensted Insertion Algorithm. In recent work the authors have shown that Patience Sorting provides an algorithmic description for permutations avoiding the barred (generalized) permutation pattern $3-\bar{1}-42$. Motivated by this and a recently formulated geometric form for Patience Sorting in terms of certain intersecting lattice paths, we study the related themes of restricted input and avoidance of similar barred permutation patterns. One such result is to characterize those permutations for which Patience Sorting is an invertible algorithm as the set of permutations simultaneously avoiding the barred patterns $3-\bar{1}-42$ and $3-\bar{1}-24$. We then enumerate this avoidance set, which involves convolved Fibonacci numbers.
12 pages, LaTeX, uses pstricks, needs fpsac.cls v2: final version of extended abstract for FPSAC'06

Keywords

Combinatorics, 05A05, 05A15, 05A18 (Primary); 05E10 (Secondary)

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/106106

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0512122
 http://arxiv.org/abs/math/0512122

Collections

arXiv