Enumerations of Permutations by Circular Descent Sets

摘要

The circular descent of a permutation a is a set {sigma(i) vertical bar sigma(i) > sigma(i + 1)}. In this paper, we focus on the enumerations of permutations by the circular descent set. Let cdes(n) (S) be the number of permutations of length n which have the circular descent set S. We derive the explicit formula for cdes(n )(S). We describe a class of generating binary trees T-k with weights. We find that the number of permutations in the set CDESn (S) corresponds to the weights of T-k. As a application of the main results in this paper, we also give the enumeration of permutation tableaux according to their shape.