Minimal permutations and 2-regular skew tableaux

DOI10.1016/J.AAM.2011.04.003zbMATH Open1230.05006arXiv1010.6261OpenAlexW2010683903MaRDI QIDQ720593FDOQ720593

Authors: William Y. C. Chen, Cindy C. Y. Gu, Kevin J. Ma 

Publication date: 11 October 2011

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: Bouvel and Pergola introduced the notion of minimal permutations in the study of the whole genome duplication-random loss model for genome rearrangements. Let $mathcal{F}_d(n)$ denote the set of minimal permutations of length $n$ with $d$ descents, and let $f_d(n)=|mathcal{F}_d(n)|$. They derived that $f_{n-2}(n)=2^n-(n-1)n-2$ and $f_n(2n)=C_n$, where $C_n$ is the $n$-th Catalan number. Mansour and Yan proved that $f_{n+1}(2n+1)=2^{n-2}n{C}_{n+1}$. In this paper, we consider the problem of counting minimal permutations in $mathcal{F}_d(n)$ with a prescribed set of ascents. We show that such structures are in one-to-one correspondence with a class of skew Young tableaux, which we call $2$-regular skew tableaux. Using the determinantal formula for the number of skew Young tableaux of a given shape, we find an explicit formula for $f_{n-3}(n)$. Furthermore, by using the Knuth equivalence, we give a combinatorial interpretation of a formula for a refinement of the number $f_{n+1}(2n+1)$.

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

Recommendations

• Minimal permutations with \(d\) descents
• On the enumeration of \(d\)-minimal permutations
• Some properties of non minimal permutations
• scientific article
• Posets and permutations in the duplication-loss model: minimal permutations with \(d\) descents

zbMATH Keywords

RSK algorithmKnuth equivalence2-regular skew tableauminimal permutation

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Permutations, matrices, and generalized Young tableaux
• Polygon dissections and standard Young tableaux
• On the enumeration of d-minimal permutations
• Posets and permutations in the duplication-loss model: minimal permutations with \(d\) descents
• On the tandem duplication-random loss model of genome rearrangement
• On the enumeration of skew Young tableaux
• Minimal permutations with \(d\) descents

Cited In (3)

• Permutation patterns in genome rearrangement problems: the reversal model
• Minimal permutations with \(d\) descents
• Title not available (Why is that?)

This page was built for publication: Minimal permutations and 2-regular skew tableaux

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