Minimal Permutations and 2-Regular Skew Tableaux

Original · EN

Bouvel and Pergola introduced the notion of minimal permutations in the study of the whole genome duplication-random loss model for genome rearrangements. Let Fd(n) denote the set of minimal permutations of length n with d descents, and let fd(n)= |Fd(n)|. They derived that fₙ₋₂(n)=2ⁿ-(n-1)n-2 and fₙ(2n)=Cₙ, where Cₙ is the n-th Catalan number. Mansour and Yan proved that fₙ₊₁(2n+1)=2ⁿ⁻²nCₙ₊₁. In this paper, we consider the problem of counting minimal permutations in Fd(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). Furthermore, by using the Knuth equivalence, we give a combinatorial interpretation of a formula for a refinement of the number fₙ₊₁(2n+1).