Analogues of up-down permutations for colored permutations

Niedermaier, Andrew ; Remmel, Jeffrey

Journal of integer sequences, Tome 13 (2010) no. 5.

Résumé

Summary: André proved that $ \sec x$ is the generating function of all up-down permutations of even length and $ \tan x$ is the generating function of all up-down permutation of odd length. There are three equivalent ways to define up-down permutations in the symmetric group $ S_n$. That is, a permutation $ \sigma $ in the symmetric group $ S_n$ is an up-down permutation if either (i) the rise set of $ \sigma $ consists of all the odd numbers less than $ n$, (ii) the descent set of $ \sigma $ consists of all even number less than $ n$, or (iii) both (i) and (ii). We consider analogues of André's results for colored permutations of the form $ (\sigma ,w)$ where $ \sigma \in S_n$ and $ w \in \{0,\ldots, k-1\}^n$ under the product order. That is, we define $ (\sigma _i,w_i) (\sigma _{i+1},w_{i+1})$ if and only if $ \sigma _i \sigma _{i+1}$ and $ w_i \leq w_{i+1}$. We then say a colored permutation $ (\sigma ,w)$ is (I) an up-not up permutation if the rise set of $ (\sigma ,w)$ consists of all the odd numbers less than $ n$, (II) a not down-down permutation if the descent set of $ (\sigma ,w)$ consists of all the even numbers less than $ n$, (III) an up-down permutation if both (I) and (II) hold. For $ k \geq 2$, conditions (I), (II), and (III) are pairwise distinct. We find $ p,q$-analogues of the generating functions for up-not up, not down-down, and up-down colored permutations.

Détail

Classification : 05A05, 05A15
Keywords: (Concerned with sequences and )