Enumerations of Permutations by Circular Descent Sets

Abstract

The circular descent of a permutation $\sigma$ is a set $\{\sigma (i)\mid \sigma (i)>\sigma (i+1)\}$. In this paper, we focus on the enumerations of permutations by the circular descent set. Let $cde{s}_n(S)$ be the number of permutations of length $n$ which have the circular descent set $S$. We derive the explicit formula for $cde{s}_n(S)$. We describe a class of generating binary trees $T_k$ with weights. We find that the number of permutations in the set $CDE{S}_n(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.