Analogues of Up-down Permutations for Colored Permutations

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

                   jremmel@ucsd.edu

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 σ in the symmetric group S_{n} is an updown permutation if either (i) the rise set of σ consists of all the odd numbers less than n, (ii) the descent set of σ 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 (σ, w) where σ ∈ S_{n} and w ∈ {0, …, k − 1}^{n} under the product order. That is, we define (σ_{i}, w_{i}) < (σ_{i+1}, w_{i+1}) if and only if σ_{i} < σ_{i+1} and w_{i} ≤ w_{i+1}. We then say a colored permutation (σ, w) is (I) an up-not up permutation if the rise set of (σ, w) consists of all the odd numbers less than n, (II) a not down-down permutation if the descent set of (σ, w) consists of all the even numbers less than n, (III) an up-down permutation if both (I) and (II) hold. For k ≥ 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.

1 Introduction

Let P = {1, 2, 3, …} denote the set of positive integers, E = {2, 4, 6, …} denote the set of even integers in P, and O = {1, 3, 5, …} denote the set of odd integers in P. Let P_{n} = {1, …, n}, E_{n} = E∩P_{n}, and O_{n} = O∩P_{n}. Let S_{n} denote the symmetric group, i.e., the set of all permutations of P_{n}. Then if σ = σ_{1}σ_{2} … σ_{n} ∈ S_{n}, we define Des(σ) = {i : σ_{i} > σ_{i+1}} and Ris(σ) = {i : σ_{i} < σ_{i+1}}. We say that σ is an up-down permutation if

1Partially supported by NSF grant DMS 0654060.

σ_{1} < σ_{2} > σ_{3} < σ_{4} > σ_{5} ⋯,

or, equivalently, if Des(σ) = E_{n−1} or Ris(σ) = O_{n−1}. Similarly, we say that σ is an down-up permutation if

σ_{1} > σ_{2} < σ_{3} > σ_{4} < σ_{5} ⋯,

or, equivalently, if Ris(σ) = E_{n−1} or Des(σ) = O_{n−1}. Clearly if σ = σ_{1}σ_{2} ⋯ σ_{n} ∈ S_{n} is an up-down permutation, then the complement of σ,

σ^{c} = (n + 1 − σ_{1})(n + 1 − σ_{2}) ⋯ (n + 1 − σ_{n})

is a down-up permutation. Thus the number of up-down permutations in S_{n} is equal to the number of down-up permutations in S_{n}. Let UD_{n} denote the number of up-down permutations in S_{n}. Then André [2, 3] proved the following.

sec t = 1 + ∑_{n∈E} UD_{n} \frac{t^{n}}{n!} and  (1)
tan t = ∑_{n∈O} UD_{n} \frac{t^{n}}{n!}.  (2)

The goal of this paper is to find analogues of André’s results for colored permutations. That is, we shall consider pairs of the form (σ, w) where σ ∈ S_{n} and w ∈ {0, 1, …, k − 1}^{n}. Thus if w = w_{1} ⋯ w_{n} and σ = σ_{1} ⋯ σ_{n} ∈ S_{n}, then we will say that σ_{i} is colored with w_{i} in (σ, w). Alternatively, we can think of (σ, w) as an element of the wreath product C_{k}≀S_{n} of the cyclic group C_{k} and the symmetric group S_{n}. C_{k} ≀S_{n} is the group of k^{n}n! signed permutations where there are k signs, 1 = ϵ^{0}, ϵ, ϵ^{2}, …, ϵ^{k−1} where ϵ is a primitive k-th root of unity. Hence we can think of Γ ∈ C_{k} ≀ S_{n} as a pair (σ, w) where σ = σ_{1} … σ_{n} ∈ S_{n} and the sign of σ_{i} is ϵ^{w_{i}} for i = 1, …, n. Throughout the paper, we shall abbreviate S_{n} × {0, …, k − 1}^{n} by C_{k} ≀ S_{n} even though our results do not use the group structure of C_{k} ≀ S_{n}. .

To define the analogues of up-down permutations in C_{k} ≀ S_{n}, we need to define the analogues of the descent set and the rise set of a colored permutation. That is, suppose ≺ is a partial order on the set of pairs (i, j) ∈ {1, …, n}×{0, …, k−1}. Then if σ = σ_{1} … σ_{n} ∈ S_{n} and w = w_{1} … w_{n} ∈ {0, …, k − 1}^{n}, we define

Des_{≺}((σ, w)) = {i : (σ_{i}, w_{i}) ≻ (σ_{i+1}, w_{i+1})} and
Ris_{≺}((σ, w)) = {i : (σ_{i}, w_{i}) ≺ (σ_{i+1}, w_{i+1})}.

We then say that (σ, w) is an up-down permutation if

(σ_{1}, w_{1}) ≺ (σ_{2}, w_{2}) ≻ (σ_{3}, w_{3}) ≺ (σ_{4}, w_{4}) ≻ (σ_{5}, w_{5}) · · · .  (3)

Now if ≺ is a total order, then counting the number of up-down permutations is uninteresting. For example, Adin and Roichman [1] used the following total order to define their notion of flag major index on C_{k} ≀ S_{n}:

(1, k − 1) ≺ ⋯ ≺ (n, k − 1) ≺ (1, k − 2) ≺ ⋯ ≺ (n, k − 2) ≺ ⋯ ≺ (1, 0) ≺ ⋯ ≺ (n, 0).

If we use such a total order ≺ and we pick an assignment of colors, (1, w_{1}), … (n, w_{n}), to 1, 2, …, n, then ≺ induces a total order on the pairs (1, w_{1}), …, (n, w_{n}). Hence for this assignment of colors, there are clearly just UD_{n} pairs (σ, w) which satisfy (3). Hence relative to a total order ≺, there are k^{n}UD_{n} colored permutations (σ, w) ∈ C_{k} ≀ S_{n} that satisfy (3).

However if we use the product order on {1, …, n} × {0, …, k − 1}, then we have a completely different situation. That is, we define the product order ≤ on {1, …, n} × {0, , …, k − 1} by declaring that (i_{1}, j_{1}) ≤ (i_{2}, j_{2}) if and only if i_{1} ≤ i_{2} and j_{1} ≤ j_{2}. Again we can define the analogue of the descent set and rise set of a colored permutation in C_{k} ≀ S_{n} as

Des((σ, w)) = {i : (σ_{i}, w_{i}) > (σ_{i+1}, w_{i+1})} and  (4)
Ris((σ, w)) = {i : (σ_{i}, w_{i}) < (σ_{i+1}, w_{i+1})}.  (5)

We can then define three different natural analogues of up-down permutations. That is, we define the following three sets of permutations in C_{k} ≀ S_{n}:

1. U-D_{n,k} = {(σ, w) ∈ C_{k} ≀ S_{n} : Ris((σ, w)) = O_{n−1} and Des((σ, w)) = E_{n−1}},

2. U-NU_{n,k} = {(σ, w) ∈ C_{k} ≀ S_{n} : Ris((σ, w)) = O_{n−1}}, and

3. ND-D_{n,k} = {(σ, w) ∈ C_{k} ≀ S_{n} : Des((σ, w)) = E_{n−1}}.

Here U-NU stands for “up-not up” and ND-D stands for “not down-down.” Clearly U-D_{n,k} is contained in both U-NU_{n,k} and ND-D_{n,k}. However, both of these containments are strict and U-NU_{n,k} ≠ ND-D_{n,k}. For example, if k = 2 and n = 3, then

(1 2 3, 1 1 0) ∈ U-NU_{3,2} − (U-D_{3,2} ∪ ND-D_{3,2}) and
(1 3 2, 1 0 0) ∈ ND-D_{3,2} − (U-D_{3,2} ∪ U-NU_{3,2}).

Let u-d_{n,k} = |U-D_{n,k}|, nd-d_{n,k} = |ND-D_{n,k}|, and u-nu_{n,k} = |U-NU_{n,k}|. Then the main goal of this paper is to find expressions for the following generating functions:

A(t) = ∑_{n≥0} \frac{u-d_{2n,k}t^{2n}}{(2n)!} ,  B(t) = ∑_{n≥0} \frac{u-d_{2n+1,k}t^{2n+1}}{(2n + 1)!} ,

C(t) = ∑_{n≥0} \frac{u-nu_{2n,k}t^{2n}}{(2n)!} ,  D(t) = ∑_{n≥0} \frac{u-nu_{2n+1,k}t^{2n+1}}{(2n + 1)!} ,

E(t) = ∑_{n≥0} \frac{nd-d_{2n,k}t^{2n}}{(2n)!} , and F (t) = ∑_{n≥0} \frac{nd-d_{2n+1,k}t^{2n+1}}{(2n + 1)!} .

The generating functions A(t) and B(t) are simply Hadamard products of the generating functions for up-down permutations of S_{n} and the generating functions for sequences of words w = w_{1} … w_{n} ∈ {0, …, k − 1}^{∗} such that

w_{1} ≤ w_{2} ≥ w_{3} ≤ w_{4} ≥ w_{5} ≤ w_{6} · · · .

The generating function for such words was found by Rawlings [16]. The generating functions for C(t), D(t), E(t) and F (t) are more interesting. For example, we shall show that

C(t) = \frac{(k − 1)!}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} cos t} and  (6)

D(t) = \frac{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} sin t}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} cos t}  (7)

For k ≤ 4, the generating functions and their initial terms are listed below:

k  egf for u-nu_{2n,k}  egf for u-nu_{2n+1,k}  {u-nu_{n,k}}_{n≥1}
1  sec t  tan t  1, 1, 2, 5, 16, 61, …
2  \frac{1}{cos t−t sin t}  \frac{sin t+t cos t}{cos t−t sin t}  2, 3, 14, 49, 376, 1987, …
3  \frac{2}{(2−t^{2}) cos t−4t sin t}  \frac{4t cos t+(2−t^{2}) sin t}{(2−t^{2}) cos t−4t sin t}  3, 6, 44, 201, 2436, 16768, …
4  \frac{6}{(6−9t^{2}) cos t−(18t−t^{3}) sin t}  \frac{(18t−t^{3}) cos t+(6−9t^{2}) sin t}{(6−9t^{2}) cos t−(18t−t^{3}) sin t}  4, 10, 100, 565, 9356, 79584, …

It is easy to see that if (σ, w) = (σ_{1} … σ_{2n+1}, w_{1} … w_{2n+1}) is in U-NU_{2n+1,k}, then the reverse of (σ, w),

(σ, w)^{r} = (σ_{2n+1} … σ_{1}, w_{2n+1} … w_{1}),

will be in ND-D_{2n+1,k} so that

∑_{n≥0} \frac{nd-d_{2n+1,k} · t^{2n+1}}{(2n + 1)!} = \frac{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} sin t}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} cos t}.  (8)

Thus D(t) = F (t). However the generating function for E(t) is not the same as for C(t). We shall prove that

E(t) = ∑_{n≥0} \frac{nd-d_{2n,k} · t^{2n}}{(2n)!} = (\frac{(k − 1)!}{2\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{it}} + \frac{(k − 1)!}{2\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{−it}} )^{−1}

= \frac{(\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{it}) (\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{−it})}{(k − 1)!\frac{d^{k−1}}{dt^{k−1}} t^{k−1} cos t}

= \frac{P_{k−1}(it)P_{k−1}(−it)}{(k − 1)!\frac{d^{k−1}}{dt^{k−1}} t^{k−1} cos t},

where P_{d}(z) = ∑_{m=0}^{d} z^{d}\binom{d}{m}^{2}((d − m)!). In fact, we shall prove that

P_{d}(it)P_{d}(−it) = ∑_{s=0}^{d} t^{2s} ∑_{r=0}^{2s}(−1)^{s−r}\binom{d}{r}^{2}(d − r)!\binom{d}{2s − r}^{2}(d − (2s − r))!

= ∑_{s=0}^{d} \frac{(d!)^{2}}{(2s)!}\binom{d}{s}\binom{d + s}{s}t^{2s}.  (9)

Thus P_{d}(it)P_{d}(−it) is a polynomial with integer coefficients of degree 2d where only evendegree terms are non-zero. For k ≤ 4, we get the following results:

k  egf for nd-d_{2n,k}  P_{k−1}(z)  {nd-d_{n,k}}_{n≥1}
1  sec t  1  1, 1, 2, 5, 16, 61, …
2  \frac{1+t^{2}}{cos t−t sin t}  1 + z  2, 10, 14, 85, 376, 3457, …
3  \frac{4+12t^{2}+t^{4}}{(2−t^{2}) cos t−4t sin t}  2 + 4z + z^{2}  3, 12, 44, 423, 2436, 35398, …
4  \frac{36+216t^{2}+45t^{4}+t^{6}}{(6−9t^{2}) cos t−(18t−t^{3}) sin t}  6 + 18z + 9z^{2} + z^{3} 4, 22, 100, 1315, 9356, 185804, …

In fact, we shall show that the generating functions C(t), D(t), E(t) and F (t) are special cases of more general generating functions which keep track of more statistics over more general sets of elements in C_{k} ≀ S_{n}. That is, for any k ≥ 2, let

(C_{k} ≀ S_{n})^{(2)} = {(σ, w) ∈ C_{k} ≀ S_{n} : O_{n−1} ⊆ Rise((σ, w))} and  (10)
(C_{k} ≀ S_{n})_{(2)} = {(σ, w) ∈ C_{k} ≀ S_{n} : O_{n−1} ∩ Des((σ, w)) = ∅}.  (11)

Thus (C_{k} ≀S_{n})^{(2)} is the set of (σ, w) ∈ C_{k} ≀S_{n} which are forced of have rises at all odd positions and (C_{k} ≀ S_{n})_{(2)} is the set of (σ, w) ∈ C_{k} ≀ S_{n} which do not have a descent at an odd position. Then we shall find generating functions for certain statistics on (C_{k}≀S_{n})^{(2)} which specialize to C(t) and D(t) and generating functions for certain statistics on (C_{k} ≀ S_{n})_{(2)} which specialize to E(t) and F (t). The techniques that we shall use to derive our generating functions over (C_{k} ≀ S_{n})^{(2)} or (C_{k} ≀ S_{n})_{(2)} are based on ideas from a paper by Mendes, Remmel, and Riehl [13] who, for any k ≥ 2 and 0 ≤ j ≤ k − 1, found generating functions for permutations σ ∈ S_{n} such that Des(σ) = {j + sk : k ≥ 0 & j + sk < n}. Mendes, Remmel, and Riehl derived their generating functions by applying certain ring homomorphisms defined on the ring of symmetric functions Γ over infinitely many variables x_{1}, x_{2}, … to simple symmetric function identities. We will also find our generating functions over (C_{k} ≀ S_{n})^{(2)} or (C_{k} ≀ S_{n})_{(2)} by applying ring homomorphisms defined on Λ to simple symmetric function identities. To derive our generating functions over (C_{k} ≀ S_{n})_{(2)}, we shall also need to find the generating function for (σ, w) ∈ C_{k} ≀ S_{n} such that Des((σ, w)) = ∅.

The outline of this paper is as follows. In Section 2, we shall derive the generating functions A(t) and B(t). In Section 3, we shall provide the necessary background on symmetric functions that we shall need to derive the generating functions C(t), D(t), E(t) and F (t). In Section 4, we shall give the derivations of the generating functions that specialize to C(t) and D(t). Finally in Section 5, we shall give the derivations of the generating functions that specialize to E(t) and F (t).

2 The generating functions for up-down permutations

In this section, we shall give expressions for the generating functions for A(t) and B(t). To state our results, we first need some notation. Suppose that f(t) = ∑_{n≥0} f_{n}t^{n} and g(t) = ∑_{n≥0} g_{n}t^{n}. Then the Hadamard product f(t) ⊗ g(t) of f and g is defined by

f(t) ⊗ g(t) = ∑_{n≥0} f_{n}g_{n}t^{n}.  (12)

Let P^{∗} denote the set of all words over the alphabet P and P^{+} denote the set of all nonempty words in P^{∗}. We let ϵ denote the empty word. For any w = w_{1}w_{2} … w_{n} ∈ P^{+}, we let ℓ(w) = n denote the length of w, |w| = ∑_{i=1}^{n} w_{i}, and x(w) = ∏_{i=1}^{n} x_{w_{i}}. For example, if w = 1 2 1 3 2 4 5 4, then ℓ(w) = 8, |w| = 22, and x(w) = x_{1}^{2}x_{2}^{2}x_{3}x_{4}^{2}x_{5}. Given w = w_{1}w_{2} … w_{n} ∈ P^{+}, we define the descent set Des(w), the weak descent set WDes(w), the rise set Ris(w), and the weak rise set WRis(w) as follows:

Des(w) = {i : w_{i} > w_{i+1}},  (13)
WDes(w) = {i : w_{i} ≥ w_{i+1}},  (14)
Ris(w) = {i : w_{i} < w_{i+1}}, and  (15)
WRis(w) = {i : w_{i} ≤ w_{i+1}}.  (16)

Definition 1. Let w = w_{1}w_{2} … w_{n} ∈ P^{+}.

1. We say that w a strict up-down word if w_{1} < w_{2} > w_{3} < w_{4} > w_{5} ⋯, or, equivalently if Ris(w) = O_{n−1} and Des(w) = E_{n−1}.

2. We say that w a strict down-up word if w_{1} > w_{2} < w_{3} > w_{4} < w_{5} ⋯, or, equivalently if Des(w) = O_{n−1} and Ris(w) = E_{n−1}.

3. We say that w a weak up-down word if w_{1} ≤ w_{2} ≥ w_{3} ≤ w_{4} ≥ w_{5} ⋯, or, equivalently if WRis(w) = O_{n−1} and WDes(w) = E_{n−1}.

4. We say that w a weak down-up word if w_{1} ≥ w_{2} ≤ w_{3} ≥ w_{4} ≤ w_{5} ⋯, or, equivalently if WDes(w) = O_{n−1} and WRis(w) = E_{n−1}.

We let SUP_{n}, SDU_{n}, WUD_{n}, and WDU_{n} denote set of all words in {1, …, n}^{∗} which are strict up-down, strict down-up, weak up-down, and weak down-up, respectively. By convention, the empty word ϵ and all one letter words belong to all four sets. Clearly, if w = w_{1}w_{2} … w_{n} ∈ P_{n}^{∗}, then w ∈ SUD_{n} (WUD_{n}, respectively) if and only if the complement of w relative to n,

w^{c,n} = (n + 1 − w_{1})(n + 1 − w_{2}) … (n + 1 − w_{n}) ∈ SDU_{n} (WUD_{n}, respectively).

We let SUP_{n,m}, SDU_{n,m}, WUD_{n,m}, and WDU_{n,m} denote set of all words in P_{n}^{∗} of length m which are strict up-down, strict down-up, weak up-down, and weak down-up, respectively.

Carlitz [4] proved analogues of André’s formulas for strict up-down words. In particular, Carlitz [4] proved that

1 + ∑_{m∈E} |SUD_{n,m}|z^{m} = \frac{1}{Q_{n}(z)} and ∑_{m∈O} |SUD_{n,m}|z^{m} = \frac{P_{n}(z)}{Q_{n}(z)}  (17)

where

P_{n}(z) = ∑_{k=0}^{n}(−1)^{k}\binom{n + k}{2k + 1}z^{2k+1} and  (18)

Q_{n}(z) = ∑_{k=0}^{n}(−1)^{k}\binom{n + k − 1}{2k}z^{2k}.  (19)

Rawlings [16] proved analogues of (17) for weak down-up words. That is, Rawlings proved that

1 + ∑_{m∈E} |WDU_{n,m}|z^{m} = \frac{1}{R_{n}(z)} and ∑_{m∈O} |WDU_{n,m}|z^{m} = \frac{S_{n}(z)}{R_{n}(z)}  (20)

where

R_{n}(z) = ∑_{k≥0}(−1)^{k}\binom{n + k}{2k}z^{2k} and  (21)

S_{n}(z) = ∑_{k≥0}(−1)^{k}\binom{n + k}{2k + 1}z^{2k+1}.  (22)

By our observations above, these are also the generating functions for weak up-down words. Carlitz and Rawlings proved their generating functions by recursions. In fact, Carlitz developed recursions for the up-down words w weighted by x(w) and Rawlings actually proved a generating function for weak down-up words w weighted by q^{|w|}z^{ℓ(w)}. Recently, Fuller and Remmel [8] showed that the generating functions of words w according to the weight x(w)z^{ℓ(w)} of words in either SUD_{n} and WU_{n} can be expressed in term of quasi-symmetric functions. Fuller and Remmel proved their results combinatorially via some simple involutions and their methods actually extend to a much broader class of words with regular up-down patterns.

Now it is easy to see that if (σ, w) = (σ_{1} ⋯ σ_{n}, w_{1} ⋯ w_{n}) ∈ C_{k} ≀ S_{n} where Ris((σ, w)) = O_{n−1} and Des((σ, w)) = E_{n−1}, then it must be the case that Ris(σ) = O_{n−1} and Des(σ) = E_{n−1} so that σ is an up-down permutation and w_{1} ≤ w_{2} ≥ w_{3} ≤ w_{4} ⋯ so that w is a weak up-down word over the alphabet {0, …, k − 1}. It then follows that

A(t) = ∑_{n≥0} \frac{u-d_{2n,k}t^{2n}}{(2n)!} = (\frac{1}{R_{k}(t)}) ⊗ sec t  (23)

and

B(t) = ∑_{n≥0} \frac{u-d_{2n+1,k}t^{2n+1}}{(2n + 1)!} = (\frac{S_{k}(t)}{R_{k}(t)}) ⊗ tan t.  (24)

We can also define a strong product order <_{s} on P×{0, …, k −1} by defining (i_{1}, w_{1}) <_{s} (i_{2}, w_{2}) if and only if i_{1} < i_{2} and w_{1} < w_{2}. We then define

Des_{s}((σ, w)) = {i : (σ_{i+1}, w_{i})} <_{s} (σ_{i}, w_{i+1})} and
Ris_{s}((σ, w)) = {i : (σ_{i}, w_{i}) <_{s} (σ_{i+1}, w_{i+1})}.

We say at that (σ, w) ∈ C_{k} ≀ S_{n} is a strong up-down permutation if Ris_{s}((σ, w)) = O_{n−1} and Des_{s}((σ, w)) = E_{n−1}. We let su-d_{n,k} denote the number of strong up-down permutations of C_{k} ≀ S_{n}. Then clearly,

Ā(t) = ∑_{n≥0} \frac{su-d_{2n,k}t^{2n}}{(2n)!} = (\frac{1}{G_{k}(t)}) ⊗ sec t  (25)

and

B̄(t) = ∑_{n≥0} \frac{su-d_{2n+1,k}t^{2n+1}}{(2n + 1)!} = (\frac{F_{k}(t)}{G_{k}(t)}) ⊗ tan t.  (26)

3 Symmetric Functions

In this section we give the necessary background on symmetric functions needed for our proofs of the generating functions over (C_{k} ≀ S_{n})^{(2)} or (C_{k} ≀ S_{n})_{(2)}.

Let Λ denote the ring of symmetric functions over infinitely many variables x_{1}, x_{2}, … with coefficients in the field complex numbers C. The n^{th} elementary symmetric function e_{n} in the variables x_{1}, x_{2}, … is given by

E(t) = ∑_{n≥0} e_{n}t^{n} = ∏_{i}(1 + x_{i}t)

and the n^{th} homogeneous symmetric function h_{n} in the variables x_{1}, x_{2}, … is given by

H(t) = ∑_{n≥0} h_{n}t^{n} = ∏_{i} \frac{1}{1 − x_{i}t}.

Thus

H(t) = 1/E(−t).  (27)

Let λ = (λ_{1}, …, λ_{ℓ}) be an integer partition, that is, λ is a finite sequence of weakly increasing nonnegative integers. Let ℓ(λ) denote the number of nonzero integers in λ. If the sum of these integers is n, we say that λ is a partition of n and write λ ⊢ n. For any partition λ = (λ_{1}, …, λ_{ℓ}), let e_{λ} = e_{λ_{1}} ⋯ e_{λ_{ℓ}}. The well-known fundamental theorem of symmetric functions says that {e_{λ} : λ is a partition} is a basis for Λ or that {e_{0}, e_{1}, …} is an algebraically independent set of generators for Λ. Similarly, if we define h_{λ} = h_{λ_{1}} ⋯ h_{λ_{ℓ}}, then {h_{λ} : λ is a partition} is also a basis for Λ. Since {e_{0}, e_{1}, …} is an algebraically independent set of generators for Λ, we can specify a ring homomorphism θ on Λ by simply defining θ(e_{n}) for all n ≥ 0.

Since the set of elementary symmetric functions e_{λ} is a basis for Λ, one can expresses h_{n} = ∑_{λ⊢n} a_{λ,n}e_{λ} for any n > 0. Up to a sign, the coefficient a_{λ,n} equals the size of a certain set of combinatorial objects depending on λ. A brick tabloid of shape (n) and type λ = (λ_{1}, …, λ_{k}) is a filling of a row of n squares of cells with brick of lengths λ_{1}, …, λ_{k} such that bricks to not overlap. One brick tabloid of shape (12) and type (1, 1, 2, 3, 5) is displayed below.

Figure 1: A brick tabloid of shape (12) and type (1, 1, 2, 3, 5).

Let B_{λ,n} denote the set of all λ-brick tabloids of shape (n) and let B_{λ,n} = |B_{λ,n}|. Through simple recursions stemming from (27), Eğecioğlu and Remmel proved in [7] that

h_{n} = ∑_{λ⊢n}(−1)^{n−ℓ(λ)}B_{λ,n}e_{λ}.  (28)

Next we define a class of symmetric functions p_{n,ν} which have a relationship with e_{λ} that is analogous to the relationship between h_{n} and e_{λ}. These functions were first introduced in [9] and [11]. Let ν be a function which maps the set of nonnegative integers into the field F. Recursively define p_{n,ν} ∈ Λ_{n} by setting p_{0,ν} = 1 and letting

p_{n,ν} = (−1)^{n−1}ν(n)e_{n} + ∑_{k=1}^{n−1}(−1)^{k−1}e_{k}p_{n−k,ν}

for all n ≥ 1. By multiplying series, this means that

(∑_{n≥0}(−1)^{n}e_{n}t^{n}) (∑_{n≥1} p_{n,ν}t^{n}) = ∑_{n≥1} (∑_{k=0}^{n−1} p_{n−k,ν}(−1)^{k}e_{k}) t^{n} = ∑_{n≥1}(−1)^{n−1}ν(n)e_{n}t^{n},

where the last equality follows from the definition of p_{n,ν}. Therefore,

∑_{n≥1} p_{n,ν}t^{n} = \frac{∑_{n≥1}(−1)^{n−1}ν(n)e_{n}t^{n}}{∑_{n≥0}(−1)^{n}e_{n}t^{n}}  (29)

or, equivalently,

1 + ∑_{n≥1} p_{n,ν}t^{n} = \frac{1 + ∑_{n≥1}(−1)^{n}(e_{n} − ν(n)e_{n})t^{n}}{∑_{n≥0}(−1)^{n}e_{n}t^{n}} .  (30)

When taking ν(n) = 1 for all n ≥ 1, (30) becomes

1 + ∑_{n≥1} p_{n,1}t^{n} = \frac{1}{∑_{n≥0}(−1)^{n}e_{n}t^{n}} = 1 + ∑_{n≥1} h_{n}t^{n}

which implies p_{n,1} = h_{n}. Other special cases for ν give well-known generating functions. For example, if ν(n) = n for n ≥ 1, then p_{n,ν} is the power symmetric function ∑_{i} x_{i}^{n}. By taking ν(n) = (−1)^{k}χ(n ≥ k + 1) for some k ≥ 1, p_{n,(−1)^{k}χ(n≥k+1)} is the Schur function corresponding to the partition (1^{k}, n).

This definition of p_{n,ν} is desirable because of its expansion in terms of elementary symmetric functions. The coefficient of e_{λ} in p_{n,ν} has a nice combinatorial interpretation similar to that of the homogeneous symmetric functions. Suppose T is a brick tabloid of shape (n) and type λ and that the final brick in T has length ℓ. Define the weight of a brick tabloid w_{ν}(T) to be ν(ℓ) and let

w_{ν}(B_{λ,n}) = ∑_{T is a brick tabloid of shape (n) and type λ} w_{ν}(T).

By the recursions found in the definition of p_{n,ν}, it may be shown that

p_{n,ν} = ∑_{λ⊢n}(−1)^{n−ℓ(λ)}w_{ν}(B_{λ,n})e_{λ}

in almost the exact same way that (28) was proved in [7].

For n ≥ 1 and λ ⊢ n, let

[n]_{q} = \frac{1 − q^{n}}{1 − q} = q^{0} + q^{1} + ⋯ + q^{n−1} [n]_{p,q} = \frac{p^{n} − q^{n}}{p − q} = p^{n−1}q^{0} + ⋯ + p^{0}q^{n−1}
[n]_{q}! = [n]_{q} ⋯ [1]_{q}  [n]_{p,q}! = [n]_{p,q} ⋯ [1]_{p,q}
\left[{n \atop λ}\right]_{q} = \frac{[n]_{q}!}{[λ_{1}]_{q}! ⋯ [λ_{ℓ}]_{q}!}  \left[{n \atop λ}\right]_{p,q} = \frac{[n]_{p,q}!}{[λ_{1}]_{p,q}! ⋯ [λ_{ℓ}]_{p,q}!}

be the q- and p, q-analogues of n, n!, and \binom{n}{λ}, respectfully. We shall use the convention that [0]_{q} = [0]_{p,q} = 0 and [0]_{q}! = [0]_{p,q}! = 1. The q- and p, q-analogues for the exponential function are defined by

e_{q}[t] = ∑_{n≥0} \frac{t^{n}}{[n]_{q}!}q^{\binom{n}{2}} e_{p,q}[t] = ∑_{n≥0} \frac{t^{n}}{[n]_{p,q}!}q^{\binom{n}{2}}.

For any permutation σ ∈ S_{n}, we define the number of inversions inv(σ) and the number of coinversions coinv(σ) of σ by

inv(σ) = ∑_{i<j} χ(σ_{i} > σ_{j}) and coinv(σ) = ∑_{i<j} χ(σ_{i} < σ_{j})

where for any statement A, χ(A) = 1 is A is true and χ(A) = 0 if A is false. Note that inv(σ) and coinv(σ) make sense if σ is any sequence of non-negative integers.

We end this section with three lemmas that will be needed a later sections. All of the lemmas follow from simple codings of a basic result of Carlitz [6] that

\left[{n \atop k}\right]_{q} = ∑_{R(1^{k}0^{n−k})} q^{inv(r)}

where R(1^{k}0^{n−k}) is the number of rearrangements of k 1’s and n − k 0’s. We start with a lemma from [13]. Fix a brick tabloid T = (b_{1}, …, b_{ℓ(μ)}) ∈ B_{μ,n}. Let IF (T) denote the set of all fillings of the cells of T = (b_{1}, …, b_{ℓ(μ)}) with the numbers 1, …, n so that the numbers increase within each brick reading from left to right. We then think of each such filling as a permutation of S_{n} by reading the numbers from left to right in each row. For example, Figure 2 pictures an element of IF (3, 6, 3) whose corresponding permutation is 4 6 12 1 5 7 8 10 11 2 3 9.

Figure 2: An element of IF (3, 6, 3)

Then the following lemma from [13] gives a combinatorial interpretation to p∑{ℓ(μ) \atop i=1} ^{\binom{b_{i}}{2}}\left[{n \atop b_{1},...,b_{ℓ(μ)}}\right]_{p,q}.

Lemma 2. If T = (b_{1}, …, b_{ℓ(μ)}) is a brick tabloid in B_{μ,n}, then

p∑^{i} ^{\binom{b_{i}}{2}}\left[{n \atop b_{1}, …, b_{ℓ(μ)}}\right]_{p,q} = ∑_{σ∈IF (T)} q^{inv(σ)}p^{coinv(σ)}.

Let DF (T) denote the set of all fillings of the cells of T = (b_{1}, …, b_{ℓ(μ)}) with the numbers 1, …, n so that the numbers decrease within each brick reading from left to right. It is easy to see that if σ ∈ IF (T), then σ^{r} ∈ DF ((b_{ℓ(μ)}, …, b_{1})) and inv(σ) = coinv(σ^{r}) and coinv(σ) = inv(σ^{r}). Thus we also have the following lemma.

Lemma 3. If T = (b_{1}, …, b_{ℓ(μ)}) is a brick tabloid in B_{μ,n}, then

q∑^{i} ^{\binom{b_{i}}{2}}\left[{n \atop b_{1}, …, b_{ℓ(μ)}}\right]_{p,q} = ∑_{σ∈DF (T)} q^{inv(σ)}p^{coinv(σ)}.

Another well-known combinatorial interpretation for \left[{n+k−1 \atop k−1}\right]_{q} is that it is equal to sum of the sizes of the partitions that are contained in a n × (k − 1) rectangle. Thus we have the following lemma.

Lemma 4.

∑_{0≤a_{1}≤···≤a_{n}≤k−1} q^{a_{1}+···+a_{n}} = \left[{n + k − 1 \atop k − 1}\right]_{q}.

4 The generating functions up-not up permutations

In this section, we shall derive two generating functions that can be specialized to give the generating functions for C(t) and D(t) stated in the introduction. If (σ, w) ∈ C_{k} ≀ S_{n}, we let

Ris_{E}((σ, w)) = {2i : 2i ∈ Ris((σ, w))} and  (31)
ris(σ)_{E}((σ, w)) = |Ris_{E}((σ, w))|.  (32)

We let (C_{k} ≀ S_{n})^{(2)} denote the set of (σ, w) ∈ C_{k} ≀ S_{n} such that O_{n−1} ⊆ Ris((σ, w)). Thus if (σ, w) ∈ (C_{k} ≀S_{n})^{(2)}, (σ, w) is forced to have rises at all odd positions and ris(σ)_{E}(σ, w) counts how many elements of the form 2i are in Ris((σ, w)). In particular, if (σ, w) ∈ (C_{k} ≀ S_{n})^{(2)} and ris(σ)_{E}(σ, w) = 0, then (σ, w) ∈ U-NU_{n,k}.

Our first theorem of this section is the following.

Theorem 5. For all k ≥ 2,

∑_{n≥0} \frac{t^{2n}}{[2n]_{p,q}!} ∑_{(σ,w)∈(C_{k}≀S_{2n})^{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))} =

\frac{1 − x}{1 − x + ∑_{m≥1} ^{\frac{p^{\binom{m}{2}}(x−1)^{m}t^{2m}}{[2m]_{p,q}!}} \left[{2m+k−1 \atop k−1}\right]_{r}}  (33)

Note that when we set x = 0 and p = q = r = 1, then (33) reduces to

∑_{n≥0} \frac{u-nu_{2n,k}t^{2n}}{(2n)!} = \frac{1}{∑m≥0 \frac{t^{2m}(−1)^{m}}{(2m)!} \frac{(2m+k−1)(2m−k−2)···(2m+1)}{(k−1)!}}

= \frac{(k − 1)!}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} cos t}.  (34)

which is the generating function of C(t) claimed in the introduction.

Proof. Define a ring homomorphism θ : Λ → ℚ(p, q, r, x), where ℚ is the set of the rational numbers, by setting

θ(e_{2n}) = (−1)^{2n−1}(x − 1)^{n−1} \frac{\left[{2n+k−1 \atop k−1}\right]r}{[2n]_{p,q}!} p^{\binom{n}{2}}  (35)

if n ≥ 1 and

θ(e_{2n+1}) = 0  (36)

if n ≥ 0. Then we claim that

θ(h_{2n+1}) = 0  (37)

for all n ≥ 0 and

[2n]_{p,q}!θ(h_{2n}) = ∑_{(σ,w)∈(C_{k}≀S_{2n})^{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))}  (38)

for all n ≥ 1. Note that

θ(h_{n}) = ∑_{μ⊢n}(−1)^{n−ℓ(μ)}B_{μ,(n)}θ(e_{μ}).  (39)

First suppose that n is odd. Then clearly every partition μ of n must have an odd part and, hence, θ(h_{n}) = 0 since θ(e_{2k+1}) = 0 for all k ≥ 0. If n is even, then the only μ such that θ(e_{μ}) ≠ 0 on the RHS of (39) are when all the parts of μ are even. That is, μ must be of the form 2λ where λ = (λ_{1}, …, λ_{k}) is partition of n and 2λ = (2λ_{1}, …, 2λ_{k}). Thus

[2n]_{p,q}!θ(h_{2n})  (40)

= [2n]_{p,q}! ∑_{μ⊢n}(−1)^{2n−ℓ(μ)}B_{2μ,(2n)}θ(e_{2μ})

= [2n]_{p,q}! ∑_{μ⊢n}(−1)^{2n−ℓ(μ)} ∑_{(2b_{1},...,2b_{ℓ(μ)})∈B_{2μ,(2n)}} ∏_{j=1}^{ℓ(μ)}(−1)^{2b_{j}−1}(x − 1)^{b_{j}−1} \frac{\left[{2b_{j}+k−1 \atop k−1}\right]r}{[2b_{j}]_{p,q}!} p^{\binom{2b_{j}}{2}}

= ∑_{μ⊢n} ∑_{(2b_{1},...,2b_{ℓ(μ)})∈B_{2μ,(2n)}} p∑{ℓ(μ) \atop j=1} ^{\binom{2b_{j}}{2}}\left[{2n \atop 2b_{1}, …, 2b_{ℓ(μ)}}\right]_{p,q} ∏_{j=1}^{ℓ(μ)}(x − 1)^{b_{j}−1}\left[{2b_{j} + k − 1 \atop k − 1}\right]_{r}.

Next we want to give a combinatorial interpretation to (40). By Lemma 2 for each brick tabloid T = (2b_{1}, …, 2b_{ℓ(μ)}), we can interpret p∑{ℓ(μ) \atop j=1} ^{\binom{2b_{j}}{2}}\left[{2n \atop 2b_{1},...,2b_{ℓ(μ)}}\right]_{p,q} as the sum of the weights of fillings of T with permutations σ ∈ S_{2n} such that σ is increasing in each brick and we weight σ with q^{inv(σ)}p^{coinv(σ)}. By Lemma 4, we can interpret the term ∏_{j=1}^{ℓ(μ)} \left[{2b_{j}+k−1 \atop k−1}\right]_{r} as the sum of the weights of fillings w = w_{1} ⋯ w_{2n} of T where the elements of w are between 0 and k − 1 and are weakly increasing in each brick and we weight w by r^{|w|}. Finally, we interpret ∏_{j=1}^{ℓ(μ)}(x − 1)^{b_{j}−1} as all ways of picking a label of the even cells of each brick except the final cell with either an x or a −1. For completeness, we label the final cell of each brick with 1. We shall call all such objects that can be created by these choices filled labeled brick tabloids and we let F_{2n} denote the set of all filled labeled brick tabloids. Thus a C ∈ F_{2n} consists of a brick tabloid T, a permutation σ ∈ S_{2n}, a sequence w ∈ {0, …, k − 1}^{2n}, and a labeling L of the even cells of T with elements from {x, 1, −1} such that

1. all the bricks of T have even length,

2. σ is strictly increasing in each brick,

3. w is weakly increasing in each brick,

4. the final cell of each brick is labeled with 1, and

5. each even numbered cell which is not a final cell of a brick is labeled with x or −1.

We then define the weight w(C) of C to be q^{inv(σ)}p^{coinv(σ)}r^{|w|} times the product of all the x labels in L and the sign sgn(C) of C to be the product of all the −1 labels in L. For example, if n = 12, k = 4, and T = (4, 6, 2), then Figure 3 pictures such a composite object C ∈ F_{12} where w(C) = q^{23}p^{43}r^{17}x^{2} and sgn(C) = −1.

Thus

[2n]_{p,q}!θ(h_{2n}) = ∑_{C∈F_{2n}} sgn(C)w(C).  (41)

Figure 3: A composite object C ∈ F_{12}.

Next we define a weight preserving sign-reversing involution I_{1} : F_{2n} → F_{2n}. To define I_{1}(C), we scan the cells of C = (T, σ, w, L) from right to left looking for the leftmost cell 2t such that either (i) 2t is labeled with −1 or (ii) 2t is at the end a brick b_{j} and the brick b_{j+1} immediately following b_{j} has the property that σ is strictly increasing in all the cells corresponding to b_{j} and b_{j+1} and w is weakly increasing in all the cells corresponding to b_{j} and b_{j+1}. In case (i), I_{1}(C) = (T′, σ′, w′, L′) where T′ is the result of replacing the brick b in T containing 2t by two bricks b^{∗} and b^{∗∗} where b^{∗} contains the cell 2t plus all the cells in b to the left of 2t and b^{∗∗} contains all the cells of b to the right of 2t, σ′ = σ, w′ = w, and L′ is the labeling that results from L by changing the label of cell 2t from −1 to 1. In case (ii), I_{1}(C) = (T′, σ′, w′, L′) where T′ is the result of replacing the bricks b_{j} and b_{j+1} in T by a single brick b, σ′ = σ, w′ = w, and L′ is the labeling that results from L by changing the label of cell 2t from 1 to −1. If neither case (i) or case (ii) applies, then we let I_{1}(C) = C. For example, if C is the element of F_{12} pictured in Figure 3, then I_{1}(C) is pictured in Figure 4.

Figure 4: I_{1}(C) for C in Figure 3.

It is easy to see that I_{1} is a weight-preserving sign-reversing involution and hence I_{1} shows that

[2n]_{p,q}!θ(h_{2n}) = ∑_{C∈F_{2n},I_{1}(C)=C} sgn(C)w(C).  (42)

Thus we must examine the fixed points C = (T, σ, w, L) of I_{1}. First there can be no −1 labels in L so that sg(C) = 1. Moreover, if b_{j} and b_{j+1} are two consecutive bricks in T and 2t is that last cell of b_{j}, then it can not be the case that σ_{2t} < σ_{2t+1} and w_{2t} ≤ w_{2t+1} since otherwise we could combine b_{j} and b_{j+1}. For any such fixed point, we can think of the pair (σ, w) as an element of C_{k} ≀ S_{2n}. It follows that if cell 2t is at the end of a brick, then 2t ∉ Ris_{E}((σ, w)). However if 2v is a cell which is not at the end of brick, then our definitions force σ_{2v} < σ_{2v+1} and w_{2v} ≤ w_{2v+1} so that 2v ∈ Ris_{E}((σ, w)). Since each such cell 2v must be labeled with an x, it follows that sgn(C)w(C) = q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))}. Moreover our definitions force that O_{2n−1} ⊆ Ris((σ, w)) so that (σ, w) ∈ (C_{k} ≀ S_{2n})^{(2)}. Such a fixed point is pictured in Figure 5. Vice versa, if (σ, w) ∈ (C_{k} ≀ S_{2n})^{(2)}, then we can create a fixed point C = (T, σ, w, L) by having the bricks in T end at cells of the form 2t where 2t ∉ Ris_{E}((σ, w) and labeling each cell 2t ∈ Ris_{E}((σ, w)) with x and labeling all other even numbered cells with 1. Thus we have shown that

[2n]_{p,q}!θ(h_{2}n) = ∑_{(σ,w)∈(C_{k}≀S_{2n})^{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))}

as desired.

Figure 5: A fixed point of I_{1}.

Applying θ to the identity H(t) = (E(−t))^{−1}, we get

∑_{n≥0} θ(h_{n})t^{n} = ∑_{n≥0} \frac{t^{2n}}{[2n]_{p,q}!} ∑_{(σ,w)∈(C_{k}≀S_{2n})^{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}(σ,w)}
= \frac{1}{1 + ∑_{n≥1}(−t)^{n}θ(e_{n})}
= \frac{1}{1 + ∑_{m≥1}(−1)^{2m}t^{2m}^{\frac{(−1)^{2m−1}(x−1)^{m−1}p^{\binom{2m}{2}}}{[2m]_{p,q}!}} \left[{2m+k−1 \atop k−1}\right]_{r}}
= \frac{1 − x}{1 − x + ∑_{m≥1} ^{\frac{p^{\binom{2m}{2}}(x−1)^{m}t^{2m}}{[2m]_{p,q}!}} \binom{2m+k−1}{k−1}}

which proves (33). Theorem 6. For all k ≥ 2,

∑_{n≥0} \frac{t^{2n+1}}{[2n + 1]_{p,q}!} ∑_{(σ,w)∈(C_{k}≀S_{2n+1})^{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))} =

\frac{− ∑_{m≥1} ^{\frac{p^{\binom{2m−1}{2}}(x−1)^{m}t^{2m−1}}{[2m−1]_{p,q}}} \left[{2m−1+k−1 \atop k−1}\right]_{r}}{1 − x + ∑_{m≥1} ^{\frac{p^{\binom{m}{2}}(x−1)^{m}t^{2m}}{[2m]_{p,q}!}} \left[{2m+k−1 \atop k−1}\right]_{r}} .  (43)

Note that when we set x = 0 and p = q = r = 1, then (33) reduces to

∑_{n≥0} \frac{u-nu_{2n+1,k}t^{2n+1}}{(2n + 1)!} = \begin{matrix}∑ & m≥1 & \frac{(−1)^{m−1}t^{2m−1}}{(2m−1)!} & \frac{(2m+k−2)···(2m)}{(k−1)!} \\ ∑ & m≥0 & \frac{t^{2m}(−1)^{m}}{(2m)!} & \frac{(2m+k−1)(2m−k−2)···(2m+1)}{(k−1)!} \end{matrix}
= \frac{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} sin t}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} cos t}  (44)

which is the generating function of D(t) claimed in the introduction. Proof. Let θ be the ring homomorphism defined in Theorem 5. In this case, we will derive (43) by applying θ to the identity

∑_{n≥1} p_{n,ν}t^{n} = \frac{∑_{n≥1}(−1)^{n−1}ν(n)e_{n}t^{n}}{∑_{n≥0}(−1)^{n}e_{n}t^{n}}  (45)

where

ν(2n) = \frac{[2n]_{p,q}[2n]_{r}}{p^{2n−1}[2n + k − 1]_{r}}  (46)
= \frac{p^{\binom{2n−1}{2}}}{p^{\binom{2n}{2}}} \frac{[2n]_{p,q}!}{[2n − 1]_{p,q}!} \begin{matrix}\left[{2n−1+k−1 \atop k−1}\right] & r \\ \left[{2n+k−1 \atop k−1}\right] & r \end{matrix}

for n ≥ 1 and ν(2m + 1) = 0 for m ≥ 0. We have defined ν so that

ν(2n)θ(e_{2n}) = \frac{(−1)^{2n−1}(x − 1)^{n−1}p^{\binom{2n−1}{2}}}{[2n − 1]_{p,q}!} \left[{2n − 1 + k − 1 \atop k − 1}\right]_{r}.  (47)

Again it is easy to see that

θ(p_{2n+1,ν}) = 0  (48)

for all n ≥ 0 since the expansion of p_{2n+1,ν} in terms of the elementary symmetric functions only involves e_{μ}’s where μ contains an odd part. The key fact that we have to prove is that

[2n + 1]_{p,q}!θ(p_{2n+2,ν}) = ∑_{(σ,w)∈(C_{k}≀S_{2n+1})^{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))}  (49)

for all n ≥ 0. Note that

[2n + 1]_{p,q}!θ(p_{2n+2,ν})  (50)

= [2n + 1]_{p,q}! ∑_{μ⊢n+1}(−1)^{2n+2−ℓ(μ)}w_{ν}(B_{2μ,(2n+2)})θ(e_{2μ})

= [2n + 1]_{p,q}! ∑_{μ⊢n+1}(−1)^{2n+2−ℓ(μ)} ∑_{(2b_{1},...,2b_{ℓ(μ)})∈B_{2μ,(2n+2)}} ν(2b_{ℓ(μ)}) ×

∏_{j=1}^{ℓ(μ)}(−1)^{2b_{j}−1}(x − 1)^{b_{j}−1} \frac{\left[{2b_{j}+k−1 \atop k−1}\right]r}{[2b_{j}]_{p,q}!} p^{\binom{2b_{j}}{2}}

= [2n + 1]_{p,q}! ∑_{μ⊢n+1} ∑_{(2b_{1},...,2b_{ℓ(μ)})∈B_{2μ,(2n+2)}} \frac{p^{\binom{2b_{ℓ(μ)}−1}{2}}(x − 1)^{b_{ℓ(μ)}−1}}{[2b_{ℓ(μ)} − 1]_{p,q}!} \left[{2b_{ℓ(μ)} − 1 + k − 1 \atop k − 1}\right]_{r} ×

∏_{j=1}^{ℓ(μ)−1} \frac{p^{\binom{2b_{j}}{2}}(x − 1)^{b_{j}−1}}{[2b_{j}]_{p,q}!} \left[{2b_{j} + k − 1 \atop k − 1}\right]_{r}

= ∑_{μ⊢n+1} ∑_{(2b_{1},...,2b_{ℓ(μ)})∈B_{2μ,(2n+2)}} p^{\binom{2b_{ℓ(μ)}−1}{2}}p∑{ℓ(μ)−1 \atop j=1} ^{\binom{2b_{j}}{2}}\left[{2n + 1 \atop 2b_{1}, …, 2b_{ℓ(μ)−1}, 2b_{ℓ(μ)} − 1}\right]_{p,q} ×

(x − 1)^{b_{ℓ(μ)}−1}\left[{2b_{ℓ(μ)} − 1 + k − 1 \atop k − 1}\right]_{r} ∏_{j=1}^{ℓ(μ)−1}(x − 1)^{b_{j}−1}\left[{2b_{j} + k − 1 \atop k − 1}\right]_{r}.

Again we want to give a combinatorial interpretation to (50). By Lemma 2 for each brick tabloid T = (2b_{1}, …, 2b_{ℓ(μ)}), we can interpret

p^{\binom{2b_{ℓ(μ)}−1}{2}}p∑{ℓ(μ)−1 \atop j=1} ^{\binom{2b_{j}}{2}}\left[{2n + 1 \atop 2b_{1}, …, 2b_{ℓ(μ)−1}, 2b_{ℓ(μ)−1}}\right]_{p,q}

the sum of the weights of fillings of the first 2n+1 cells of T with a permutation σ ∈ S_{2n+1} such that σ is increasing in each brick and where we weight σ with q^{inv(σ)}p^{coinv(σ)}. Note that T has 2n + 2 cells so we will assume that the last cell of T is filled in and we will not place anything in that cell. By Lemma 4, we can interpret the term \left[{2b_{ℓ(μ)}−1+k−1 \atop k−1}\right]_{r} ∏_{j=1}^{ℓ(μ)−1} \left[{2b_{j}+k−1 \atop k−1}\right]_{r} as giving the sum of the weights of fillings w = w_{1} ⋯ w_{2n+1} of the first 2n + 1 cells of T where the elements of w are between 0 and k − 1 and are weakly increasing in each brick and where we weight w by r^{|w|}. Finally, we interpret (x − 1)^{2b_{ℓ(μ)}−1} ∏_{j=1}^{ℓ(μ)−1}(x − 1)^{b_{j}−1} as all ways of picking a label of the even cells of each brick except the final cell with either an x or a −1. For completeness, we label the final cell of each brick with 1. We shall call all such objects that can be created in this way filled labeled brick tabloids and let G_{2n+2} denote the set of all filled labeled brick tabloids. Thus a C ∈ G_{2n+2} consists of a brick tabloid T, a permutation σ ∈ S_{2n+1}, a sequence w ∈ {0, …, k − 1}^{2n+1}, and a labeling L of the even cells of T with elements from {x, 1, −1} such that

1. all the bricks of T have even length,

2. σ is strictly increasing in each brick and fills in the first 2n + 1 cells,

3. w is weakly increasing in each brick and fills in the first 2n + 1 cells,

4. the final cell of each brick is labeled with 1, and

5. each even numbered cell which is not a final cell of a brick is labeled with x or −1.

We then define the weight w(C) of C to be q^{inv(σ)}p^{coinv(σ)}r^{|w|} times the product of all the x labels in L and the sign sgn(C) of C to be the product of all the −1 labels in L. For example, if n = 12, k = 4, and T = (4, 6, 2), then Figure 6 pictures such a composite object C ∈ G_{12} where w(C) = q^{20}p^{35}r^{14}x^{2} and sgn(C) = −1.

Thus

[2n + 1]_{p,q}!θ(p_{2n+2,ν}) = ∑_{C∈G_{2n+2}} sgn(C)w(C).  (51)

Figure 6: A composite object C ∈ G_{12}.

Next we define a weight preserving sign-reversing involution I_{2} : G_{2n+2} → G_{2n+2}. I_{2} is essentially the same as I_{1} of Theorem 6. That is, we scan the cells of C = (T, σ, w, L) from right to left looking for the leftmost cell 2t such that either (i) 2t is labeled with −1 or (ii) 2t is at the end a brick b_{j} and the brick b_{j+1} immediately following b_{j} has the property that the σ is strictly increasing in all the cells corresponding to b_{j} and b_{j+1} and w is weakly increasing in all the cells corresponding to b_{j} and b_{j+1}. In case (i), I_{2}(C) = (T′, σ′, w′, L′) where T′ is the result of replacing the brick b in T containing 2t by two bricks b^{∗} and b^{∗∗} where b^{∗} contains cell 2t plus all the cells in b to the left of 2t and b^{∗∗} contains all the cells of b to the right of 2t, σ′ = σ, w′ = w, and L′ is the labeling that results from L by changing the label of cell 2t from −1 to 1. In case (ii), I_{2}(C) = (T′, σ′, w′, L′) where T′ is the result of replacing the bricks b_{j} and b_{j+1} in T by a single brick b, σ′ = σ, w′ = w, and L′ is the labeling that results from L by changing the label of cell 2t from 1 to −1. If neither case (i) or case (ii) applies, then we let I_{2}(C) = C. For example, if C is the element of G_{12} pictured in Figure 6, then I_{2}(C) is pictured in Figure 7.

Figure 7: I_{2}(C) for C in Figure 6.

Again, it is easy to see that I_{2} is a weight-preserving sign-reversing involution so that

[2n + 1]_{p,q}!θ(p_{2n+2,ν}) = ∑_{C∈G_{2n+2},I_{2}(C)=C} sgn(C)w(C).  (52)

Thus we must examine the fixed points C = (T, σ, w, L) of I_{2}. First there can be no −1 labels in L so that sg(C) = 1. Moreover, if b_{j} and b_{j+1} are two consecutive bricks in T and 2t is that last cell of b_{j}, then it can not be the case that σ_{2t} < σ_{2t+1} and w_{2t} ≤ w_{2t+1} since otherwise we could combine b_{j} and b_{j+1}. For any such fixed point, we can think of (σ, w) as an element of C_{k} ≀ S_{2n+1}. It follows that if cell 2t is at the end of a brick, then 2t ∉ Ris_{E}((σ, w)). However if 2v is a cell which is not at the end of brick, then our definitions force σ_{2v} < σ_{2v+1} and w_{2v} ≤ w_{2v+1} so that 2v ∈ Ris_{E}((σ, w)). Since each such cell 2v must be labeled with an x, it follows that sgn(C)w(C) = q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))}. Moreover our definitions force that O_{2n−1} ⊆ Ris((σ, w)) so that (σ, w) ∈ (C_{k} ≀ S_{2n+1})^{(2)}. Such a fixed point is pictured in Figure 8. Vice versa, if (σ, w) ∈ (C_{k} ≀S_{2n+1})^{(2)}, then we can create a fixed point C = (T, σ, w, L) by having the bricks in T end at cells of the form 2t where 2t ∉ Ris_{E}((σ, w) and labeling each cell 2t ∈ Ris_{E}((σ, w)) with x and labeling all other even numbered cells with 1. Thus we have shown that

[2n + 1]_{p,q}!θ(p_{2n+2,ν}) = ∑_{(σ,w)∈(C_{k}≀S_{2n+1})^{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))}

as desired.

Figure 8: A fixed point of I_{2}.

Applying θ to the identity (45), we get

∑_{n≥1} θ(p_{n,ν})t^{n} = ∑_{n≥1} \frac{t^{2n+2}}{[2n + 1]_{p,q}!} ∑_{(σ,w)∈(C_{k}≀S_{2n+1})^{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))}

= \frac{∑_{m≥1}(−1)^{2m−1}t^{2m}ν(2m)θ(e_{2m})}{1 + ∑_{n≥1}(−t)^{n}θ(e_{n})}

= \frac{∑_{m≥1} t^{2m}^{\frac{p^{\binom{2m−1}{2}}(x−1)^{m−1}}{[2n−1]_{p,q}}} \left[{2n−1+k−1 \atop k−1}\right]_{r}}{1 + ∑_{m≥1}(−1)^{2m}t^{2m}^{\frac{(−1)^{2m−1}(x−1)^{m−1}p^{\binom{2m}{2}}}{[2m]_{p,q}!}} \left[{2m+k−1 \atop k−1}\right]_{r}}

= \frac{− ∑_{m≥1} t^{2m}^{\frac{p^{\binom{2n−1}{2}}(x−1)^{m}}{[2n−1]_{p,q}}} \left[{2n−1+k−1 \atop k−1}\right]_{r}}{1 − x + ∑_{m≥1} ^{\frac{p^{\binom{2m}{2}}(x−1)^{m}t^{2m}}{[2m]_{p,q}!}} \binom{2m+k−1}{k−1}}

That is, we have shown that

∑_{n≥0} \frac{t^{2n+2}}{[2n + 1]_{q}!} ∑_{(σ,w)∈(C_{k}≀S_{2n+1})^{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))} =  (53)

\frac{− ∑_{m≥1} t^{2m}^{\frac{p^{\binom{2n−1}{2}}(x−1)^{m}}{[2n−1]_{p,q}}} \left[{2n−1+k−1 \atop k−1}\right]_{r}}{1 − x + ∑_{m≥1} ^{\frac{p^{\binom{m}{2}}(x−1)^{m}t^{2m}}{[2m]_{q}!}} \left[{2m+k−1 \atop k−1}\right]_{r}} .

Then dividing both sides of (53) by t yields (43).

5 The generating functions for not down-down permutations

In this section, we shall prove two generating functions which specialize to the generating functions E(t) and F (t) described in the introduction. In particular, we let (C_{k}≀S_{n})_{(2)} denote the set of all (σ, w) ∈ C_{k} ≀ S_{n} such that O_{n−1} ∩ Des((σ, w)) = ∅. We let

NonDes_{E}((σ, w)) = {2i : 2i ∉ Des((σ, w))} and  (54)
nondes_{E}((σ, w)) = |NonDes_{E}((σ, w))|.  (55)

It is easy to see that the generating functions

1 + ∑_{n≥1} \frac{t^{2n}}{[2n]_{p,q}!} ∑_{(σ,w)∈ (C_{k}≀S_{2n})_{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{nondes_{E}((σ,w))}.  (56)

and

∑_{n≥0} \frac{t^{2n+1}}{[2n + 1]_{p,q}!} ∑_{(σ,w)∈ (C_{k}≀S_{2n+1})_{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{nondes_{E}((σ,w))}.  (57)

specialize to E(t) and F (t) respectively when we set x = 0 and p = q = r = 1.

Our strategy for finding these generating functions is very similar to finding the generating function (33) and (43). That is, if one reflects on the proof of Theorem 5, the main role of the definition of a ring homomorphism θ : Λ → ℚ(p, q, r, x) was to ensure that [2n]_{p,q}!θ(h_{2n}) could be interpreted as the sum of the weights of labeled fillings (T, L, σ, w) such that (σ, w) was strictly increasing within each brick relative to the product ordering. Then the combinatorics of the involution I_{1} showed that

[2n]_{p,q}!θ(h_{2n}) = ∑_{(σ,w)∈(C_{k}≀S_{2n})^{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))}

from which we could find the generating function by applying the ring homomorphism to the identity H(t) = 1/E(−t). Now suppose that we could define a ring homomorphism Δ : Λ → ℚ(p, q, r, x) so that [2n]_{p,q}!Δ(h_{2n}) could be interpreted as the sum of the weights of labeled fillings (T, L, σ, w) such that (σ, w) was non-increasing within each brick relative to the product ordering. Then it is not difficult to see that we can define an analogue of the involution I_{1} where replace the condition that (σ, w) is strictly increasing in each brick by the condition that (σ, w) is non-increasing in each brick to show that

[2n]_{p,q}!Δ(h_{2n}) = ∑_{(σ,w)∈(C_{k}≀S_{2n})_{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{nondes_{E}((σ,w))}  (58)

We shall show at the end of this section that

Z(p, q, r, t) = ∑_{n≥0} \frac{t^{n}}{[n]_{p,q}!} ∑_{(σ,w)∈ND_{n,k}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}  (59)

= \frac{1}{1 + ∑_{m≥1} ^{\frac{q^{\binom{m}{2}}(−t)^{m}}{[2m]_{p,q}!}} \left[{m+k−1 \atop k−1}\right]_{r}}

where ND_{n,k} is the set of permutations σ ∈ C_{k} ≀ S_{n} such that Des((σ, w)) = ∅. Then clearly

\frac{Z(p, q, r, t) + Z(p, q, r, −t)}{2} = 1 + ∑_{n≥1} \frac{t^{2n}}{[2n]_{p,q}!} ∑_{(σ,w)∈ND_{2n,k}} q^{inv(σ)}p^{coinv(σ)}r^{|w|} and

\frac{Z(p, q, r, t) − Z(p, q, r, −t)}{2} = ∑_{n≥0} \frac{t^{2n+1}}{[2n + 1]_{p,q}!} ∑_{(σ,w)∈ND_{2n+1,k}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}.

Hence for all n ≥ 1,

\frac{Z(p^{2}, qp, r, t) + Z(p^{2}, qp, r, −t)}{2}|_{\frac{t^{2n}}{[2n]p,q!}} = ∑_{(σ,w)∈ND_{2n,k}}(pq)^{inv(σ)}(p^{2})^{coinv(σ)}r^{|w|}
= p^{\binom{2n}{2}} ∑_{(σ,w)∈ND_{2n,k}} q^{inv(σ)}p^{coinv(σ)}r^{|w|} (60)

since for all σ ∈ S_{2n}, inv(σ) + coinv(σ) = \binom{2n}{2}. Similarly,

\frac{Z(p^{2}, qp, r, t) − Z(p^{2}, qp, r, −t)}{2}|_{\frac{t^{2n+1}}{[2n+1]p,q!}} = ∑_{(σ,w)∈ND_{2n+1,k}}(pq)^{inv(σ)}(p^{2})^{coinv(σ)}r^{|w|}
= p^{\binom{2n+1}{2}} ∑_{(σ,w)∈ND_{2n+1,k}} q^{inv(σ)}p^{coinv(σ)}r^{|w|} (61)

since for all σ ∈ S_{2n+1}, inv(σ) + coinv(σ) = \binom{2n+1}{2}.

We define our desired ring homomorphism Δ : Λ → ℚ(p, q, r, x) by setting

Δ(e_{2n}) = \frac{(−1)^{2n−1}(x − 1)^{n−1}}{[2n]_{p,q}!} (\frac{Z(p^{2}, pq, r, t) + Z(p^{2}, pq, r, −t)}{2}|_{\frac{t^{2n}}{[2n]p,q!}} )
= \frac{(−1)^{2n−1}(x − 1)^{n−1}}{[2n]_{p,q}!} p^{\binom{2m}{2}} ∑_{(σ,w)∈ND_{2n,k}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}.  (62)

if n ≥ 1 and

Δ(e_{2n+1}) = 0  (63)

if n ≥ 0. Again it is easy to see that

Δ(h_{2n+1}) = 0  (64)

for all n ≥ 0. Now

[2n]_{p,q}!Δ(h_{2n})  (65)

= [2n]_{p,q}! ∑_{μ⊢n}(−1)^{2n−ℓ(μ)}B_{2μ,(2n)}Δ(e_{2μ})

= [2n]_{p,q}! ∑_{μ⊢n}(−1)^{2n−ℓ(μ)} ∑_{(2b_{1},...,2b_{ℓ(μ)})∈B_{2μ,(2n)}} ∏_{j=1}^{ℓ(μ)} \frac{(−1)^{2b_{j}−1}(x − 1)^{b_{j}−1}}{[2b_{j}]_{p,q}!} ×

(\frac{Z(p^{2}, pq, r, t) + Z(p^{2}, pq, r, −t)}{2}|_{\frac{t^{2b_{j}}}{[2b_{j}]p,q!}} )

= ∑_{μ⊢n} ∑_{(2b_{1},...,2b_{ℓ(μ)})∈B_{2μ,(2n)}} p^{∑_{j=1}^{ℓ(μ)} p^{\binom{2b_{j}}{2}}} \left[{2n \atop 2b_{1}, …, 2b_{ℓ(μ)}}\right]_{p,q} ∏_{j=1}^{ℓ(μ)}(x − 1)^{b_{j}−1} ×

∏_{j=1}^{ℓ(μ)} ( ∑_{(σ,w)∈ND_{2b_{j} ,k}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}) .

Next we want to give a combinatorial interpretation to (65). By Lemma 2, for each brick tabloid T = (2b_{1}, …, 2b_{ℓ(μ)}), we can interpret p∑{ℓ(μ) \atop j=1} ^{\binom{2b_{j}}{2}}\left[{2n \atop 2b_{1},...,2b_{ℓ(μ)}}\right]_{p,q} as the sum of the weights of fillings of T with a permutation τ ∈ S_{2n} such that τ is increasing in each brick and we weight τ with q^{inv(τ)}p^{coinv(τ)}. Next the product

∏_{j=1}^{ℓ(μ)} ∑_{(σ,w)∈ND_{2b_{j} ,k}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}

can be interpreted as all ways to pick a permutation (σ^{(j)}, w^{(j)}) ∈ C_{k} ≀ S_{2b_{i}} for each brick 2b_{j} in T such that Des(σ^{(j)}, w^{(j)})) = ∅ with weight q^{inv(σ^{(j)},w^{(j)})}p^{coinv(σ^{(j)},w^{(j)}))}r^{|w^{(j)}|}. For example, Figure 9 pictures such a choice for σ and choices for (σ^{(1)}, w^{(2)}), (σ^{(2)}, w^{(2)}), (σ^{(3)}, w^{(3)}) for the brick tabloid T = (4, 6, 2). Here we have written the (σ^{(j)}, w^{(j)})’s in two line arrays as we did in the previous proofs, namely, the bottom line of the array gives σ^{(j)} and the top line of the array gives w^{(j)}. We can then combine these two diagrams into single diagram which is pictured at the bottom of Figure 9 by rearranging the elements of σ in each brick b_{j} according to the permutation σ^{(j)} and bringing down the top sequence w^{(j)} to be the top sequence in each brick. The result is a pair (σ, w) such that (σ, w) has no descents that occur between two cells in the same brick and where we weight the pair (σ, w) by q^{inv(σ)}p^{coinv(σ)}r^{|w|}. Finally, we interpret ∏_{j=1}^{ℓ(μ)}(x − 1)^{b_{j}−1} as all ways of picking a label of the even cells of each brick except the final cell with either an x or a −1. For completeness, we label the final cell of each brick with 1. We shall call such objects filled labeled brick tabloids and we let K_{2n} denote the set of all filled labeled brick tabloids that arise in this way. Thus a C ∈ K_{2n} consists of a brick tabloid T, a permutation σ ∈ S_{2n}, a sequence w ∈ {0, …, k − 1}^{2n}, and a labeling L of the even cells of T with elements from {x, 1, −1} such that

1. all the bricks of T have even length,

2. if i ∈ Des((σ, w)), then i must be the final cell of some brick,

3. the final cell of each brick is labeled with 1, and

4. each even numbered cell which is not a final cell of a brick is labeled with x or −1.

We then define the weight w(C) of C to be q^{inv(σ)}p^{coinv(σ)}r^{|w|} times the product of all the x labels in L and the sign sgn(C) of C to be the product of all the −1 labels in L. For example, if n = 12, k = 4, and T = (4, 6, 2), then the composite object C pictured at the bottom of Figure 9 is an element of K_{12} where w(C) = q^{33}p^{33}r^{15}x^{2} and sgn(C) = −1.

Thus

[2n]_{p,q}!Δ(h_{2n}) = ∑_{C∈K_{2n}} sgn(C)w(C).  (66)

At this point, we can follow the analogous steps in Theorem 5 to prove that

[2n]_{p,q}!Δ(h_{2n}) = ∑_{(σ,w)∈(C_{k}≀S_{2n})_{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{nondes_{E}((σ,w))}.

Figure 9: A composite object C ∈ K_{12}.

Applying Δ to the identity H(t) = (E(−t))^{−1}, we get

∑_{n≥0} Δ(h_{n})t^{n} = ∑_{n≥0} \frac{t^{2n}}{[2n]_{p,q}!} ∑_{(σ,ϵ)∈ (C_{k}≀S_{2n})_{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|ϵ|}x^{nondes_{E}(σ,ϵ)}
= \frac{1}{1 + ∑_{n≥1}(−t)^{n}Δ(e_{n})}
= \frac{1}{1 + ∑_{m≥1}(−1)^{2m}t^{2m} \frac{(−1)^{2m−1}(x−1)^{m−1}}{[2m]_{p,q}!} (\frac{Z(p^{2},pq,r,t)+Z(p^{2},pq,r,−t)}{2}|_{\frac{t^{2m}}{[2m]p,q!}} )}
= \frac{1 − x}{1 − x + ∑_{m≥1} \frac{((x−1)^{1/2}t)^{2m}}{[2m]_{p,q}!} (\frac{Z(p^{2},pq,r,t)+Z(p^{2},pq,r,−t)}{2}|_{\frac{t^{2m}}{[2m]p,q!}} )}
= \frac{1 − x}{−x + \frac{Z(p^{2},pq,r,(x−1)^{1/2}t)+Z(p^{2},pq,r,−(x−1)^{1/2}t)}{2}} .

Thus we have proved the following. Theorem 7. For all k ≥ 2,

1 + ∑_{n≥1} \frac{t^{2n}}{[2n]_{p,q}!} ∑_{(σ,w)∈(C_{k}≀S_{2n})_{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{nondes_{E}((σ,w))} =

\frac{1 − x}{−x + \frac{Z(p^{2},qp,r,(x−1)^{1/2}t)+Z(p^{2},qp,r,−(x−1)^{1/2}t)}{2}} .  (67)

Note that setting x = 0 and p = q = r = 1 in (67) and using Corollary 11, we obtain that

∑_{n≥0} \frac{nd-d_{2n,k}t^{2n}}{(2n)!} = \frac{1}{\frac{Z(1,1,1,it)+Z(1,1,1,−it)}{2}}

= \frac{1}{\frac{1}{2} (_{\frac{1}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{−it}}} + _{\frac{1}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{it}}} )}

= \frac{(\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{−it})(\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{it})}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} (\frac{e^{−it}+e^{it}}{2} )}

= \frac{(\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{−it})(\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{it})}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} cos t}.

Let

P_{k−1}(t) = \frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{it}  (68)

for k ≥ 2. Observe that if D = \frac{d}{dt} is the ordinary differential operator, then

D^{n}(f(t) · g(t)) = ∑_{k=0}^{n} \binom{n}{k}D^{k}(f(t))D^{n−k}(g(t)).  (69)

Hence in the special case where f(t) = e^{it} and g(t) = t^{n}, we have that

P_{n}(t) = ∑_{k=0}^{n} \binom{n}{k}i^{k}e^{it}(n) ↓_{n−k} t^{k}

= e^{it} ∑_{k=0}^{n} \binom{n}{k}^{2}(n − k)!i^{k}t^{k}

where (n) ↓_{0}= 1 and (n) ↓_{s}= n(n − 1) ⋯ (n − s + 1) for s ≥ 1. It follows that

P_{n}(it)P_{n}(−it) = ∑_{s=0}^{2n} t^{s} ∑_{r=0}^{s} \binom{n}{r}^{2}(n − r)!i^{r}\binom{n}{s − r}^{2}(n − (s − r))!(−i)^{s−r}

= ∑_{s=0}^{2n}(i)^{s}t^{s} ∑_{r=0}^{s}(−1)^{s−r}\binom{n}{r}^{2}(n − r)!\binom{n}{s − r}^{2}(n − (s − r))!.

Note that when s is odd, then term

∑_{r=0}^{s}(−1)^{s−r}\binom{n}{r}^{2}(n − r)!\binom{n}{s − r}^{2}(n − (s − r))! = 0

since the r-th term in the sum is the negative of (s − r)-th term in the sum. Thus

P_{n}(it)P_{n}(−it) = ∑_{s=0}^{n} t^{2s} ∑_{r=0}^{2s}(−1)^{s−r}\binom{n}{r}^{2}(n − r)!\binom{n}{2s − r}^{2}(n − (2s − r))!.  (70)

We can rewrite the sum

∑_{r=0}^{2s}(−1)^{s−r}\binom{n}{r}^{2}(n − r)!\binom{n}{s − r}^{2}(n − (s − r))!

as a hypergeometric series. That is, we can rewrite this sum in terms of rising factorials (a)_{n} where (a)_{0} = 1 and (a)_{n} = a(a + 1) ⋯ (a + n − 1) for n ≥ 1 to obtain that

∑_{r=0}^{2s}(−1)^{s−r}\binom{n}{r}^{2}(n − r)!\binom{n}{s − r}^{2}(n − (s − r))! =

\frac{(−1)^{s}n!n!(−n)_{2s}}{(2s)!(2s)!} ∑_{r=0}^{2s} \frac{(−n)_{r}(−2s)_{r}(−2s)_{r}}{(n − 2s + 1)_{r}(1)_{r}} \frac{1}{r!} =

\frac{(−1)^{s}n!n!(−n)_{2s}}{(2s)!(2s)!} _{3}F_{2}(−n, −2s, −2s; n − 2s + 1, 1; 1).  (71)

This is a special case of the following hypergeometric series identity found in [15]:

3F_{2}(b, c, −2n; 1 − b − 2n, 1 − c − 2n; 1) = \frac{(2n)!(b)_{n}(c)_{n}(b + c)_{2n}}{n!(b)_{2n}(c)_{2n}(b + c)_{n}} .  (72)

Using (72), we see that (71) is equal to

\frac{(−1)^{s}n!n!(−n)_{2s}}{(2s)!(2s)!} \frac{(2s)!(−n)_{s}(−2s)_{s}(−n − 2s)_{2s}}{s!(−n)_{2s}(−2s)_{2s}(−n − 2s)_{s}} =

\frac{(−1)^{s}n!n!}{(2s)!} \frac{(−1)^{s}n ↓_{s} (−1)^{s}(2s) ↓_{s} (−1)^{2s}(n + 2s) ↓_{2s}}{s!(−1)^{2s}(2s)!(−1)^{s}(n + 2s) ↓_{s}} =

\frac{(n!)^{2}}{(2s)!}\binom{n}{s}\binom{n + s}{s}

where a ↓_{0}= 1 and a ↓_{n}= a(a − 1) ⋯ (a − n + 1) for n ≥ 1. Hence

P_{n}(it)P_{n}(−it) = ∑_{s=0}^{n} \frac{(n!)^{2}}{(2s)!}\binom{n}{s}\binom{n + s}{s}t^{2s}.  (73)

Thus we have the following corollary.

Corollary 8. For k ≥ 2,

1 + ∑_{n≥1} \frac{nd-d_{2n,k}t^{2n}}{(2n)!} = \frac{∑_{s=0}^{k−1} \frac{((k−1)!)^{2}}{(2s)!} \binom{k−1}{s}\binom{k−1+s}{s}t^{2s}}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} cos t} .  (74)

We can also prove an analogue of Theorem 6. That is, suppose that we define

ν(2n) = \frac{1}{Δ(e_{2n})} \frac{(−1)^{2n−1}(x − 1)^{n−1}}{[2n − 1]_{p,q}!} (\frac{Z(p^{2}, pq, r, t) + Z(p^{2}, pq, r, −t)}{2}|_{\frac{t^{2n−1}}{[2n−1]p,q!}} )

= \frac{1}{Δ(e_{2n})} \frac{(−1)^{2n−1}p^{\binom{2n−1}{2}}(x − 1)^{n−1}}{[2n − 1]_{p,q}!} ∑_{(σ,w)∈ND_{2n−1,k}} q^{inv(σ,w)}p^{coinv(σ,w)}r^{|w|} (75)

for n ≥ 1 and ν(2m + 1) = 0 for m ≥ 0. In this case we have defined ν so that

ν(2n)Δ(e_{2n}) = \frac{(−1)^{2n−1}(x − 1)^{n−1}}{[2n − 1]_{p,q}!} (\frac{Z(p^{2}, pq, r, t) − Z(p^{2}, pq, r, −t)}{2}|_{t^{2n−1}[2n−1]_{p,q}!})
= \frac{(−1)^{2n−1}p^{\binom{2n−1}{2}}(x − 1)^{n−1}}{[2n − 1]_{p,q}!} ∑_{(σ,w)∈ND_{2n−1,k}} q^{inv(σ,w)}p^{coinv(σ,w)}r^{|w|}.  (76)

We can then follow the same sequence of steps as in the proof of Theorem 6 to prove that

[2n + 1]_{p,q}!Δ(p_{2n+2,ν}) = ∑_{(σ,w)∈(C_{k}≀S_{2n+1})_{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{nondes_{E}((σ,w))}.

Applying Δ to the identity (45), we get

∑_{n≥1} Δ(p_{n,ν})t^{n} = ∑_{n≥1} \frac{t^{2n+2}}{[2n + 1]_{p,q}!} ∑_{(σ,w)∈(C_{k}≀S_{2n+1})_{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{nondes_{E}((σ,w))}
= \frac{∑_{m≥1}(−1)^{2m−1}t^{2m}ν(2m)Δ(e_{2m})}{1 + ∑_{n≥1}(−t)^{n}Δ(e_{n})}
= \frac{∑_{m≥1}(−1)^{2m−1}t^{2m} \frac{(−1)^{2m−1}(x−1)^{m−1}}{[2m−1]_{p,q}!} (\frac{Z(p^{2},pq,r,t)−Z(p^{2},pq,r,−t)}{2}|_{t^{2m−1}[2m−1]_{p,q}!})}{1 + ∑_{m≥1}(−1)^{2m}t^{2m} \frac{(−1)^{2m−1}(x−1)^{m−1}}{[2m]_{p,q}!} (\frac{Z(p^{2},pq,r,t)+Z(p^{2},pq,r,−t)}{2}|_{t^{2m}[2m]_{p,q}!})}

= \frac{−t(x − 1)^{1/2} ∑_{m≥1} \frac{((x−1)^{1/2}t)^{2m−1}}{[2m−1]_{p,q}!} (\frac{Z(p^{2},pq,r,t)−Z(p^{2},pq,r,−t)}{2}|_{t^{2m−1}[2m−1]_{p,q}!})}{1 + ∑_{m≥1}(t^{2m} \frac{((x−1)^{1/2}t)^{2m}}{[2m]_{p,q}!} (\frac{Z(p^{2},pq,r,t)+Z(p^{2},pq,r,−t)}{2}|_{t^{2m}[2m]_{p,q}!})}
= \frac{−t(x − 1)^{1/2}(\frac{Z(p^{2},pq,r,t)−Z(p^{2},pq,r,−t)}{2})}{−x + \frac{Z(p^{2},pq,r,t)+Z(p^{2},pq,r,−t)}{2}}
= \frac{−t(x − 1)^{1/2}(Z(p^{2}, pq, r, t) − Z(p^{2}, pq, r, −t))}{−2x + Z(p^{2}, pq, r, t) + Z(p^{2}, pq, r, −t)}.

That is, we have shown that

∑_{n≥0} \frac{t^{2n+2}}{[2n + 1]_{q}!} ∑_{(σ,w)∈(C_{k}≀S_{2n+1})_{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{ris(σ)_{E}((σ,w))}  (77)

= \frac{−t(x − 1)^{1/2}(Z(p^{2}, pq, r, t) − Z(p^{2}, pq, r, −t))}{−2x + Z(p^{2}, pq, r, t) + Z(p^{2}, pq, r, −t)}

Then dividing both sides of (77) by t yields the following result. Theorem 9. For all k ≥ 2,

∑_{n≥0} \frac{t^{2n+1}}{[2n + 1]_{p,q}!} ∑_{(σ,w)∈(C_{k}≀S_{2n+1})_{(2)}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{nondes_{E}((σ,w))} =

\frac{−(x − 1)^{1/2} (Z(p^{2}, pq, r, (x − 1)^{1/2}t) − Z(p^{2}, pq, r, −(x − 1)^{1/2}t))}{−2x + Z(p^{2}, pq, r, (x − 1)^{1/2}t) + Z(p^{2}, pq, r, −(x − 1)^{1/2}t)}  (78)

∑_{n≥0} \frac{nd-d_{2n+1,k}t^{2n+1}}{(2n + 1)!} = \frac{−i(Z(1, 1, 1, it) − Z(1, 1, 1, −it))}{Z(1, 1, 1, it) + Z(1, 1, 1, −it))}

= \frac{−i (\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{−it} − \frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{it})}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{−it} + \frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{it}}

= \frac{−i\frac{d^{k−1}}{dt^{k−1}} (e^{it} − e^{−it})}{\frac{d^{k−1}}{dt^{k−1}} (e^{it} + e^{−it})}

= \frac{\frac{d^{k−1}}{dt^{k−1}} sin t}{\frac{d^{k−1}}{dt^{k−1}} cos t}.

which is the generating function of F (t) claimed in the introduction.

We note that the generating functions of Theorems 6 and 9 are two different generating functions that can be specialized to

\frac{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} sin t}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1} cos t}.

We end this section by proving a result which specializes to (59).

Theorem 10. For all k ≥ 2,

1 + ∑_{n≥1} \frac{t^{n}}{[n]_{p,q}!} ∑_{(σ,w)∈C_{k}≀S_{n}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{des((σ,w))} =

\frac{1 − x}{1 − x + ∑_{n≥1} ^{\frac{q^{\binom{n}{2}}((x−1)t)^{n}}{[n]_{p,q}!}} \left[{n+k−1 \atop k−1}\right]_{r}} .  (79)

Proof. Define a ring homomorphism Γ : Λ → ℚ(p, q, r, x) by setting

Γ(e_{n}) = (−1)^{n−1}(x − 1)^{n−1} \frac{\left[{n+k−1 \atop k−1}\right]r}{[n]_{p,q}!} q^{\binom{n}{2}}.  (80)

Then we claim that

[n]_{p,q}!Γ(h_{n}) = ∑_{(σ,w)∈C_{k}≀S_{n}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{des((σ,w))}  (81)

for all n ≥ 1. That is,

[n]_{p,q}!Γ(h_{n})  (82)

= [n]_{p,q}! ∑_{μ⊢n}(−1)^{n−ℓ(μ)}B_{μ,(n)}Γ(e_{μ})

= [n]_{p,q}! ∑_{μ⊢n}(−1)^{n−ℓ(μ)} ∑_{(b_{1},...,b_{ℓ(μ)})∈B_{μ,(n)}} ∏_{j=1}^{ℓ(μ)}(−1)^{b_{j}−1}(x − 1)^{b_{j}−1} \frac{\left[{b_{j}+k−1 \atop k−1}\right]r}{[b_{j}]_{p,q}!} q^{\binom{b_{j}}{2}}

= ∑_{μ⊢n} ∑_{(2b_{1},...,2b_{ℓ(μ)})∈B_{2μ,(2n)}} q∑{ℓ(μ) \atop j=1} ^{\binom{b_{j}}{2}}\left[{n \atop b_{1}, …, b_{ℓ(μ)}}\right]_{p,q} ∏_{j=1}^{ℓ(μ)}(x − 1)^{b_{j}−1}\left[{b_{j} + k − 1 \atop k − 1}\right]_{r}.

Next we want to give a combinatorial interpretation to (82). By Lemma 3 for each brick tabloid T = (b_{1}, …, b_{ℓ(μ)}), we can interpret q∑{ℓ(μ) \atop j=1} ^{\binom{b_{j}}{2}}\left[{n \atop b_{1},...,b_{ℓ(μ)}}\right]_{p,q} as the sum of the weights of all fillings of T with a permutation σ ∈ S_{n} such that σ is decreasing in each brick and we weight σ with q^{inv(σ)}p^{coinv(σ)}. By Lemma 4, we can interpret the term ∏_{j=1}^{ℓ(μ)} \left[{b_{j}+k−1 \atop k−1}\right]_{r} as the sum of the weights of fillings w = w_{1} ⋯ w_{n} where the elements of w are between 0 and k − 1 and are weakly decreasing in each brick and where we weight w by r^{|w|}. Finally, we interpret ∏_{j=1}^{ℓ(μ)}(x − 1)^{b_{j}−1} as all ways of picking a label of the cells of each brick except the final cell with either an x or a −1. For completeness, we label the final cell of each brick with 1. We shall call all such objects created in this way filled labeled brick tabloids and let H_{n} denote the set of all filled labeled brick tabloids that arise in this way. Thus a C ∈ H_{n} consists of a brick tabloid T, a permutation σ ∈ S_{n}, a sequence w ∈ {0, …, k − 1}^{n}, and a labeling L of the cells of T with elements from {x, 1, −1} such that

1. σ is strictly decreasing in each brick,

2. w is weakly decreasing in each brick,

3. the final cell of each brick is labeled with 1, and

4. each cell which is not a final cell of a brick is labeled with x or −1.

We then define the weight w(C) of C to be q^{inv(σ)}p^{coinv(σ)}r^{|w|} times the product of all the x labels in L and the sign sgn(C) of C to be the product of all the −1 labels in L. For example, if n = 12, k = 4, and T = (4, 3, 3, 2), then Figure 10 pictures such a composite object C ∈ H_{12} where w(C) = q^{35}p^{31}r^{17}x^{5} and sgn(C) = −1.

Thus

[n]_{p,q}!Γ(h_{n}) = ∑_{C∈H_{n}} sgn(C)w(C).  (83)

Next we define a weight preserving sign-reversing involution I_{3} : H_{n} → H_{n}. To define I_{3}(C), we scan the cells of C = (T, σ, s, L) from right to left looking for the leftmost cell t such that either (i) t is labeled with −1 or (ii) t is at the end a brick b_{j} and the brick b_{j+1} immediately following b_{j} has the property that the σ is strictly decreasing in all the cells corresponding to b_{j} and b_{j+1} and w is weakly decreasing in all the cells corresponding to b_{j}

Figure 10: A composite object C ∈ H_{12}.

and b_{j+1}. In case (i), I_{3}(C) = (T′, σ′, w′, L′) where T′ is the result of replacing the brick b in T containing t by two bricks b^{∗} and b^{∗∗} where b^{∗} contains the cell t plus all the cells in b to the left of t and b^{∗∗} contains all the cells of b to the right of t, σ′ = σ, w′ = w, and L′ is the labeling that results from L by changing the label of cell t from −1 to 1. In case (ii), I_{3}(C) = (T′, σ′, w′, L′) where T′ is the result of replacing the bricks b_{j} and b_{j+1} in T by a single brick b, σ′ = σ, w′ = w, and L′ is the labeling that results from L by changing the label of cell t from 1 to −1. If neither case (i) or case (ii) applies, then we let I_{3}(C) = C. For example, if C is the element of H_{12} pictured in Figure 10, then I_{3}(C) is pictured in Figure 11.

Figure 11: I_{3}(C) for C in Figure 10.

It is easy to see that I_{3} is a weight-preserving sign-reversing involution and hence I_{3} shows that

[n]_{p,q}!Γ(h_{n}) = ∑_{C∈H_{n},I_{3}(C)=C} sgn(C)w(C).  (84)

Thus we must examine the fixed points C = (T, σ, w, L) of I_{3}. First there can be no −1 labels in L so that sg(C) = 1. Moreover, if b_{j} and b_{j+1} are two consecutive bricks in T and t is that last cell of b_{j}, then it can not be the case that σ_{t} > σ_{t+1} and w_{t} ≥ w_{t+1} since otherwise we could combine b_{j} and b_{j+1}. For any such fixed point, we can think of (σ, w) as an element of C_{k} ≀ S_{n}. Such a fixed point is pictured in 12. It follows that if cell t is at the end of a brick, then t ∉ Des((σ, w)). However if v is a cell which is not at the end of brick, then our definitions force σ_{v} > σ_{v+1} and w_{v} ≥ w_{v+1} so that v ∈ Des((σ, w)). Since each such cell v must be labeled with an x, it follows that sgn(C)w(C) = q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{des((σ,w))}. Vice versa, if (σ, w) ∈ C_{k} ≀S_{n}, then we can create a fixed point C = (T, σ, w, L) by having the bricks in T end as cells of the form t where t ∉ Des((σ, w), labeling each cell t ∈ Des((σ, w)) with x, and labeling the remaining cells with 1. Thus we have shown that

[n]_{p,q}!Γ(h_{n}) = ∑_{(σ,w)∈C_{k}≀S_{2n}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{des((σ,w))}

as desired.

Figure 12: A fixed point of I_{3}.

Applying Γ to the identity H(t) = (E(−t))^{−1}, we obtain

∑_{n≥0} Γ(h_{n})t^{n} = ∑_{n≥0} \frac{t^{n}}{[n]_{p,q}!} ∑_{(σ,w)∈C_{k}≀S_{n}} q^{inv(σ)}p^{coinv(σ)}r^{|w|}x^{des(σ,w)}
= \frac{1}{1 + ∑_{n≥1}(−t)^{n}Γ(e_{n})}
= \frac{1}{1 + ∑_{m≥1}(−1)^{m}t^{m}^{\frac{(−1)^{m−1}(x−1)^{m−1}q^{\binom{m}{2}}}{[m]_{p,q}!}} \left[{m+k−1 \atop k−1}\right]_{r}}
= \frac{1 − x}{1 − x + ∑_{m≥1} ^{\frac{q^{\binom{m}{2}}(x−1)^{m}t^{m}}{[m]_{p,q}!}} \left[{m+k−1 \atop k−1}\right]_{r}}

which proves (79).

Observe that if we set x = 0 in (79), we obtain (59) as desired. Moreover, if we set x = 0 and r = 1 in (79), then we obtain that

1 + ∑_{n≥1} \frac{t^{n}}{[n]_{p,q}!} ∑_{(σ,w)∈ND_{n,k}} q^{inv(σ)}p^{coinv(σ)} =

\frac{1}{1 + ∑_{n≥1} ^{\frac{q^{\binom{n}{2}}(−t)^{n}}{[n]_{p,q}!}} \frac{(n+k−1)(n+k−2)···(n+1)}{(k−1)!}} =

\frac{(k − 1)!}{(k − 1)! + ∑_{n≥1} ^{\frac{q^{\binom{n}{2}}(−t)^{n}}{[n]_{p,q}!}} (n + k − 1)(n + k − 2) ⋯ (n + 1)} =

\frac{(k − 1)!}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e_{p,q}(−t)}.

Thus we have the following corollary. Corollary 11. For all k ≥ 2,

1 + ∑_{n≥1} \frac{t^{n}}{[n]_{p,q}!} ∑_{(σ,w)∈ND_{n,k}} q^{inv(σ)}p^{coinv(σ)} = \frac{(k − 1)!}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e_{p,q}(−t)}.  (85)

and

1 + ∑_{n≥1} \frac{nd_{n,k}t^{n}}{n!} = \frac{(k − 1)!}{\frac{d^{k−1}}{dt^{k−1}} t^{k−1}e^{−t}}  (86)

where nd_{n,k} = |ND_{n,k}|.

References

[1] R. M. Adin and Y. Roichman, The flag major index and group actions on polynomial rings, European J. of Combinatorics, 22 (2001), 431–446.

[2] D. André, Développements de sec x et de tang x, C. R. Acad. Sci. Paris 88 (1879), 965–967.

[3] D. André, Mémoire sur les permutations alternées, J. Math. Pures. Appl. 7 (1881), 167–184.

[4] L. Carlitz, Enumeration of up-down sequences, Discrete Math. 4 (1973), 273–286.

[5] L. Carlitz and R. Scoville, Up-down sequences, Duke Math. J. 39 (1972), 583–598.

[6] Leonard Carlitz, Sequences and inversions, Duke Math. J. 37 (1970), 193–198.

[7] Ömer Eğecioğlu and Jeffrey Remmel, Brick tabloids and the connection matrices between bases of symmetric functions, Discrete Appl. Math. 34 (1991), 107–120.

[8] E. Fuller and J. B. Remmel, Quasi-symmetric functions and up-down words, preprint.

[9] T. M. Langley and J. B. Remmel, Enumeration of m-tuples of permutations and a new class of power bases for the space of symmetric functions, Adv. in Appl. Math. 36 (2006), 30–66.

[10] I. G. Macdonald, Symmetric Functions and Hall polynomials, 2nd ed., Oxford Mathematical Monographs, Oxford University Press, 1995. With contributions by A. Zelevinsky.

[11] Anthony Mendes, Building generating functions brick by brick, Ph.D. thesis, University of California, San Diego, 2004.

[12] Anthony Mendes and Jeffrey Remmel, Generating functions for statistics on C_{k} ≀ S_{n}, Sém. Lothar. Combin. 54A (2005/07), Art. B54At, 40 pp. (electronic).

[13] T. Mendes, J. Remmel, and A. Riehl, Permutations with k-regular descent patterns, to appear in Permutation Patterns, (S. Linton, N. Rus̆kuc, V. Vatter, eds.), London. Math. Soc. Lecture Notes 376.

[14] D. J. Lemming and R. A. MacLeod, Some properties of the generalized Euler numbers, Canad. J. Math. 33 (1981), 606–617.

[15] M. Petkovek, H. S. Wilf, and D. Zeilberger, A = B, A. K. Peters, 1996.

[16] D. Rawlings, Restricted words by adjacencies, Discrete Math. 220 (2000), 183–200.

[17] Richard Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A 20 (1976), 336–356.

[18] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 1997.

2000 Mathematics Subject Classification: Primary 05A05; Secondary 05A15.

Keywords:

(Concerned with sequences \underline{A000111}, \underline{A000182}, and \underline{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.