Combinatorics of patience sorting monoids

Research output: Contribution to journalArticle

5 Downloads (Pure)

Abstract

This paper makes a combinatorial study of the two monoids and the two types of tableaux that arise from the two possible generalizations of the Patience Sorting algorithm from permutations (or standard words) to words. For both types of tableaux, we present Robinson–Schensted–Knuth-type correspondences (that is, bijective correspondences between word arrays and certain pairs of semistandard tableaux of the same shape), generalizing two known correspondences: a bijective correspondence between standard words and certain pairs of standard tableaux, and an injective correspondence between words and pairs of tableaux. We also exhibit formulas to count both the number of each type of tableaux with given evaluations (that is, containing a given number of each symbol). Observing that for any natural number n, the nth Bell number is given by the number of standard tableaux containing n symbols, we restrict the previous formulas to standard words and extract a formula for the Bell numbers. Finally, we present a ‘hook length formula’ that gives the number of standard tableaux of a given shape and deduce some consequences.

Original languageEnglish
Pages (from-to)2590-2611
Number of pages22
JournalDiscrete Mathematics
Volume342
Issue number9
DOIs
Publication statusPublished - 1 Sep 2019

Keywords

  • Bell number
  • Hook-length formula
  • Patience sorting algorithm
  • Robinson–Schensted–Knuth correspondence

Fingerprint Dive into the research topics of 'Combinatorics of patience sorting monoids'. Together they form a unique fingerprint.

Cite this