Linked partitions and permutation tableaux

zbMATH Open1295.05012arXiv1305.5357MaRDI QIDQ396898FDOQ396898

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)

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.

Full work available at URL: https://arxiv.org/abs/1305.5357

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

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

zbMATH Keywords

permutationdescentlinked partitionpermutation tableau

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• \(k\)-noncrossing and \(k\)-nonnesting graphs and fillings of Ferrers diagrams
• Tableaux combinatorics for the asymmetric exclusion process
• Bijections for permutation tableaux
• A Markov Chain on Permutations which Projects to the PASEP
• Permutation tableaux and permutation patterns
• A combinatorial derivation of the PASEP stationary state
• Linked partitions and linked cycles
• Multilinear function series and transforms in free probability theory

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.

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)