Minimal Permutations and 2-Regular Skew Tableaux
William Y.C. Chen, Cindy C.Y. Gu and Kevin J. Ma
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} - (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, the RSK algorithm Download: PDF |