
arXiv: 1010.6261
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}nC_{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)$.
19 pages
Permutations, words, matrices, minimal permutation, Applied Mathematics, 05A05, 05A19, Knuth equivalence, Minimal permutation, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 2-Regular skew tableau, 2-regular skew tableau, RSK algorithm, Combinatorial identities, bijective combinatorics
Permutations, words, matrices, minimal permutation, Applied Mathematics, 05A05, 05A19, Knuth equivalence, Minimal permutation, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 2-Regular skew tableau, 2-regular skew tableau, RSK algorithm, Combinatorial identities, bijective combinatorics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
