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 F_d(n) denote the set of minimal permutations of length n with d descents, and let f_d(n) = |F_d(n)|. They showed that f_n-2 (n) = 2ⁿ - (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 F_d(n) with a prescribed set of ascents, and we show that they 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).

  AMS Classification:  05A05, 05A19

  Keywords:  minimal permutation, 2-regular skew tableau, Knuth equivalence, RSK algorithm

  Download:   pdf