Linked partitions and permutation tableaux

MaRDI QIDQ396898zbMATH OpenFDO

Authors William Y. C. Chen, Lewis H. Liu, Carol J. Wang

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.5357, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p53

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

permutationdescentlinked partitionpermutation tableau

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19)

Abstract: Linked partitions are introduced by Dykema in the study of transforms in free probability theory, whereas permutation tableaux are introduced by Steingr'{i}msson and Williams in the study of totally positive Grassmannian cells. Let $[n]=1,2,ldots,n$. Let $L(n,k)$ denote the set of linked partitions of $[n]$ with $k$ blocks, let $P(n,k)$ denote the set of permutations of $[n]$ with $k$ descents, and let $T(n,k)$ denote the set of permutation tableaux of length $n$ with $k$ rows. Steingr'{i}msson and Williams found a bijection between the set of permutation tableaux of length $n$ with $k$ rows and the set of permutations of $[n]$ with $k$ weak excedances. Corteel and Nadeau gave a bijection from the set of permutation tableaux of length $n$ with $k$ columns to the set of permutations of $[n]$ with $k$ descents. In this paper, we establish a bijection between $L(n,k)$ and $P(n,k-1)$ and a bijection between $L(n,k)$ and $T(n,k)$. Restricting the latter bijection to noncrossing linked partitions, we find that the corresponding permutation tableaux can be characterized by pattern avoidance.

Recommendations

• The parity of the number of permutation tableaux in a fixed shape
• Permutation tableaux, restricted set partitions and labeled Dyck paths.
• Bijections for permutation tableaux
• Permutation tableaux and permutation patterns
• scientific article; zbMATH DE number 6928814

Cites work

• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• A Markov Chain on Permutations which Projects to the PASEP
• A combinatorial derivation of the PASEP stationary state
• Bijections for permutation tableaux
• Linked partitions and linked cycles
• Multilinear function series and transforms in free probability theory
• Permutation tableaux and permutation patterns
• Tableaux combinatorics for the asymmetric exclusion process
• \(k\)-noncrossing and \(k\)-nonnesting graphs and fillings of Ferrers diagrams

Cited in

(9)

• Separable \(d\)-permutations and guillotine partitions
• Linked partitions and linked cycles
• Singly covered minimal elements of linked partitions and cycles of permutations
• Permutation tableaux and the dashed permutation pattern 32-1
• Edge sequences, ribbon tableaux, and an action of affine permutations
• Vacillating Hecke tableaux and linked partitions
• The parity of the number of permutation tableaux in a fixed shape
• Wave linked partitions and 312-avoiding permutations with primacy being 1
• Permutation tableaux, restricted set partitions and labeled Dyck paths.

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Linked partitions and permutation tableaux

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