Journal of Integer Sequences, Vol. 13 (2010), Article 10.5.6

Analogues of Up-down Permutations for Colored Permutations


Andrew Niedermaier and Jeffrey Remmel
Department of Mathematics
University of California, San Diego
La Jolla, CA 92093-0112
USA

Abstract:

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.


Full version:  pdf,    dvi,    ps,    latex    


(Concerned with sequences A000111 A000182 A122045.)


Received December 19 2009; revised version received May 5 2010. Published in Journal of Integer Sequences, May 5 2010.


Return to Journal of Integer Sequences home page