ON q–OLIVIER FUNCTIONS

HELMUT PRODINGER AND TUWANI A. TSHIFHUMULO

Abstract. We consider words w_{1} … w_{n} with letters w_{i} ∈ {1, 2, 3, … } satisfying an up– up–down pattern like a_{1} ≤ a_{2} ≤ a_{3} ≥ a_{4} ≤ a_{5} ≤ a_{6} ≥ . . .. Attaching the (geometric) probability pq^{i−1} to the letter i (with p = 1−q), every word gets a probability by assuming indepence of letters. We are interested in the probability that a random word of length n satisfies the up–up–down condition. It turns out that one has to consider the 3 residue classes (mod 3) separately; then one can compute the associated probability generating function. They turn out to be q–analogues of so called Olivier functions.

1. Introduction

We consider words w_{1} … w_{n} with letters w_{i} ∈ {1, 2, 3, … } satisfying an up–up–down pattern like a_{1} ≤ a_{2} ≤ a_{3} ≥ a_{4} ≤ a_{5} ≤ a_{6} ≥ . . .. Attaching the (geometric) probability pq^{i−1} to the letter i (with p = 1 − q), every word gets a probability by assuming independence of letters. We are interested in the probability that a random word of length n satisfies the up–up–down condition. It turns out that one has to consider the 3 residue classes (mod 3) separately; then one can compute the associated probability generating function.

This extends previous research of the first author about up-down patterns, leading to q– tangent and q–secant numbers, see [4]. There are several variations possible, since “up” might mean ≤ or < and similar for “down.” Also, one can consider down–down–up patterns.

As it was discussed already in [4], the limit q → 1 yields the model of permutations (in one line notation). Thus we get the generating functions of permutations satisfying the up–up–down condition as corollaries. These results are due to Carlitz [1]. The generating functions he obtained are known as Olivier functions [3, 2]:

Φ_{k,t}(z) := ∑_{n≥0} \frac{z^{kn+t}}{(kn + t)!}.

In this way we get various different q–Olivier functions.

We arrange these functions in a table and prove only one significant instance, the other ones being similar. More details can be found in the forthcoming thesis of the second author [7].

Extensions to patterns like (≤ ⋯ ≤≥)^{∗} and (≤≤>>)^{∗} are also discussed.

We need the following notations: (x; q)_{n} := (1 − x)(1 − qx) … (1 − q^{n−1}x) and [n]_{q}! = (q; q)_{n}/p^{n}, which in the limit q → 1 are the ordinary factorials.

2. Results

We first consider n ≡ 1 mod 3. The probability generating function is given by

∑_{n≥0}(−1)^{n} \frac{z^{3n+1}q^{An^{2}+Bn}}{[3n + 1]_{q}!} / ∑_{n≥0}(−1)^{n} \frac{z^{3n}q^{Cn^{2}+Dn}}{[3n]_{q}!} ,

Date: November 13, 2002.

with the parameters A, B, C, D given in the following table.

\begin{aligned}& A & B & C & D \\ (≤≤≥)^{∗} & \frac{3}{2} & −\frac{1}{2} & \frac{3}{2} & −\frac{3}{2} \\ (≤≤>)^{∗} & 0 & 0 & 0 & 0 \\ (≤<≥)^{∗} & 3 & 0 & 3 & −2 \\ (≤<>)^{∗} & \frac{3}{2} & \frac{1}{2} & \frac{3}{2} & −\frac{1}{2} \\ (<≤≥)^{∗} & 3 & 1 & 3 & −1 \\ (<≤>)^{∗} & \frac{3}{2} & \frac{3}{2} & \frac{3}{2} & \frac{1}{2} \\ (<<≥)^{∗} & \frac{9}{2} & \frac{3}{2} & \frac{9}{2} & −\frac{3}{2} \\ (<<>)^{∗} & 3 & 2 & 3 & 0 \end{aligned}  \begin{aligned}& A & B & C & D \\ (≥≥≤)^{∗} & \frac{3}{2} & \frac{3}{2} & \frac{3}{2} & −\frac{3}{2} \\ (≥≥<)^{∗} & 0 & 0 & 0 & 0 \\ (≥>≤)^{∗} & 3 & 2 & 3 & −1 \\ (≥><)^{∗} & \frac{3}{2} & \frac{1}{2} & \frac{3}{2} & \frac{1}{2} \\ (>≥≤)^{∗} & 3 & 1 & 3 & −2 \\ (>≥<)^{∗} & \frac{3}{2} & −\frac{1}{2} & \frac{3}{2} & −\frac{1}{2} \\ (>>≤)^{∗} & \frac{9}{2} & \frac{3}{2} & \frac{9}{2} & −\frac{3}{2} \\ (>><)^{∗} & 3 & 0 & 3 & 0 \end{aligned}

Now we consider n ≡ 2 mod 3. The probability generating function is given by

∑_{n≥0}(−1)^{n} \frac{z^{3n+2}q^{An^{2}+Bn+E}}{[3n + 2]_{q}!} / ∑_{n≥0}(−1)^{n} \frac{z^{3n}q^{Cn^{2}+Dn}}{[3n]_{q}!} ,

with the parameters A, B, C, D, E given in the following table.

\begin{aligned}& A & B & C & D & E \\ (≤≤≥)^{∗} ≤ & \frac{3}{2} & \frac{1}{2} & \frac{3}{2} & −\frac{3}{2} & 0 \\ (≤≤>)^{∗} ≤ & 0 & 0 & 0 & 0 & 0 \\ (≤<≥)^{∗} ≤ & 3 & 2 & 3 & −2 & 0 \\ (≤<>)^{∗} ≤ & \frac{3}{2} & \frac{3}{2} & \frac{3}{2} & −\frac{1}{2} & 0 \\ (<≤≥)^{∗} < & 3 & 3 & 3 & −1 & 1 \\ (<≤>)^{∗} < & \frac{3}{2} & \frac{5}{2} & \frac{3}{2} & \frac{1}{2} & 1 \\ (<<≥)^{∗} < & \frac{9}{2} & \frac{9}{2} & \frac{9}{2} & −\frac{3}{2} & 1 \\ (<<>)^{∗} < & 3 & 4 & 3 & 0 & 1 \end{aligned}  \begin{aligned}& A & B & C & D & E \\ (≥≥≤)^{∗} ≥ & \frac{3}{2} & \frac{3}{2} & \frac{3}{2} & −\frac{3}{2} & 0 \\ (≥≥<)^{∗} ≥ & 0 & 0 & 0 & 0 & 0 \\ (≥>≤)^{∗} ≥ & 3 & 2 & 3 & −1 & 0 \\ (≥><)^{∗} ≥ & \frac{3}{2} & \frac{1}{2} & \frac{3}{2} & \frac{1}{2} & 0 \\ (>≥≤)^{∗} > & 3 & 4 & 3 & −2 & 1 \\ (>≥<)^{∗} > & \frac{3}{2} & \frac{5}{2} & \frac{3}{2} & −\frac{1}{2} & 1 \\ (>>≤)^{∗} > & \frac{9}{2} & \frac{9}{2} & \frac{9}{2} & −\frac{3}{2} & 1 \\ (>><)^{∗} > & 3 & 3 & 3 & 0 & 1 \end{aligned}

Finally, we consider n ≡ 0 mod 3. The probability generating function is given by

1/ ∑_{n≥0}(−1)^{n} \frac{z^{3n}q^{Cn^{2}+Dn}}{[3n]_{q}!} ,

with the parameters C, D given in the following table.

\begin{aligned}& C & D \\ (≤≤≥)^{∗} ≤≤ & \frac{3}{2} & −\frac{3}{2} \\ (≤≤>)^{∗} ≤≤ & 0 & 0 \\ (≤<≥)^{∗} ≤< & 3 & −2 \\ (≤<>)^{∗} ≤< & \frac{3}{2} & −\frac{1}{2} \\ (<≤≥)^{∗} <≤ & 3 & −1 \\ (<≤>)^{∗} <≤ & \frac{3}{2} & \frac{1}{2} \\ (<<≥)^{∗} << & \frac{9}{2} & −\frac{3}{2} \\ (<<>)^{∗} << & 3 & 0 \end{aligned}  \begin{aligned}& C & D \\ (≥≥≤)^{∗} ≥≥ & \frac{3}{2} & −\frac{3}{2} \\ (≥≥<)^{∗} ≥≥ & 0 & 0 \\ (≥>≤)^{∗} ≥> & 3 & −1 \\ (≥><)^{∗} ≥> & \frac{3}{2} & \frac{1}{2} \\ (>≥≤)^{∗} >≥ & 3 & −2 \\ (>≥<)^{∗} >≥ & \frac{3}{2} & −\frac{1}{2} \\ (>>≥)^{∗} >> & \frac{9}{2} & −\frac{3}{2} \\ (>><)^{∗} >> & 3 & 0 \end{aligned}

As an illustration, we prove the instance of (≤≤≥)^{∗}, i. e. we consider words of length 1, 4, 7, . . .. Denote by a_{n}(u) the following probability generating function: the coefficient of u^{i} in a_{n}(u) is the probability that a word of length 3n − 2 has the desired shape and ends with i. The initial value is immediate:

a_{1}(u) = \frac{pu}{1 − qu}.

To get a recursion, we compute what can become of the variable u^{i}:

\begin{aligned}u^{i} & ⟶ ∑_{i≤j≤k≥l} pq^{j−1}pq^{k−1}pq^{l−1}u^{l} \\ & = \frac{p^{3}uq^{2i}}{q^{2}(1 − q)(1 − q^{2})(1 − qu)} − \frac{up^{3}u^{i}q^{3i}}{q^{2}(1 − qu)(1 − q^{2}u)(1 − q^{3}u)}. \end{aligned}  (1)

The multiple sum was computed with Maple. This gives us the following recursion which involves substitutions as well:

a_{n+1}(u) = \frac{p^{3}u}{q^{2}(q; q)_{2}(1 − qu)}a_{n}(q^{2}) − \frac{p^{3}u}{q^{2}(qu; q)_{3}} a_{n}(q^{3}u).

We translate that into a generating function: Set

f(u) = ∑_{n≥1} a_{n}(u)z^{3n−2},

then

f(u) = z \frac{pu}{1 − qu} + \frac{z^{3}p^{3}u}{q^{2}(q; q)_{2}(1 − qu)}f(q^{2}) − \frac{z^{3}p^{3}u}{q^{2}(qu; q)_{3}} f(q^{3}u).

The nature of that functional equation makes it necessary to compute first f(q^{2}), something that can be achieved by iteration:

f(q^{2}) = z \frac{pq^{2}}{1 − q^{3}} + \frac{z^{3}p^{3}q^{2}}{q^{2}(q; q)_{2}(1 − q^{3})}f(q^{2})

− \frac{z^{3}p^{3}q^{2}}{q^{2}(q^{3}; q)_{3}} [z \frac{pq^{5}}{1 − q^{6}} + \frac{z^{3}p^{3}q^{5}}{q^{2}(q; q)_{2}(1 − q^{6})}f(q^{2})

− \frac{z^{3}p^{3}q^{5}}{q^{2}(q^{6}; q)_{3}} [z \frac{pq^{8}}{1 − q^{9}} + \frac{z^{3}p^{3}q^{8}}{q^{2}(q; q)_{2}(1 − q^{9})}f(q^{2})

− \frac{z^{3}p^{3}q^{8}}{q^{2}(q^{9}; q)_{3}} [ …,

4 H. PRODINGER AND T. A. TSHIFHUMULO

or

f(q^{2})[1 − \frac{z^{3}p^{3}}{(q; q)_{3}} + \frac{z^{6}p^{6}q^{3}}{(q; q)_{6}} − \frac{z^{9}p^{9}q^{0+3+6}}{(q; q)_{9}} + …]

= \frac{zpq^{2}}{(q^{3}; q)_{1}} − \frac{z^{4}p^{4}q^{5}}{(q^{3}; q)_{4}} + \frac{z^{7}p^{7}q^{11}}{(q^{3}; q)_{7}} − \frac{z^{10}p^{10}q^{2+(0+3+6+9)}}{(q^{3}; q)_{10}} + …,

which gives us the explicit form

f(q^{2}) = ∑_{n≥0}(−1)^{n} \frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2} n^{2}+ \frac{3}{2} n+2}}{(q^{3}; q)_{3n+1}} / ∑_{n≥0}(−1)^{n} \frac{z^{3n}p^{3n}q^{\frac{3}{2} n^{2}− \frac{3}{2} n}}{(q; q)_{3n}} .

Now that this quantity is known, we can compute f(u), again by iteration:

f(u) = z \frac{pu}{1 − qu} + \frac{z^{3}p^{3}u}{q^{2}(q; q)_{2}(1 − qu)}f(q^{2})

− \frac{z^{3}p^{3}u}{q^{2}(qu; q)_{3}} [z \frac{puq^{3}}{1 − q^{4}u} + \frac{z^{3}p^{3}q^{3}u}{q^{2}(q; q)_{2}(1 − q^{4}u)}f(q^{2})

− \frac{z^{3}p^{3}q^{3}u}{q^{2}(q^{4}u; q)_{3}} [z \frac{puq^{6}}{1 − q^{7}u} + \frac{z^{3}p^{3}q^{6}u}{q^{2}(q; q)_{2}(1 − q^{7}u)}f(q^{2})

− \frac{z^{3}p^{3}q^{6}u}{q^{2}(q^{7}; q)_{3}} [ …,

or

f(u) = ∑_{n≥0}(−1)^{n} \frac{z^{3n+1}p^{3n+1}u^{n+1}q^{\frac{3}{2} n^{2}− \frac{1}{2} n}}{(qu; q)_{3n+1}} − f(q^{2}) ∑_{n≥1}(−1)^{n} \frac{z^{3n}p^{3n}u^{n}q^{\frac{3}{2} n^{2}− \frac{7}{2} n}}{(q; q)_{2}(qu; q)_{3n−2}} .

Of course, we are especially interested in u = 1:

f(1) = ∑_{n≥0}(−1)^{n} \frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2} n^{2}− \frac{1}{2} n}}{(q; q)_{3n+1}}

− ∑_{n≥0}(−1)^{n} \frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2} n^{2}+ \frac{3}{2} n+2}}{(q; q)_{3n+3}} ∑_{n≥1}(−1)^{n} \frac{z^{3n}p^{3n}q^{\frac{3}{2} n^{2}− \frac{7}{2} n}}{(q; q)_{3n−2}} / ∑_{n≥0}(−1)^{n} \frac{z^{3n}p^{3n}q^{\frac{3}{2} n^{2}− \frac{3}{2} n}}{(q; q)_{3n}} .

We will write everything over a common denominator and thus have to compute

∑_{n≥0}(−1)^{n} \frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2} n^{2}− \frac{1}{2} n}}{(q; q)_{3n+1}} ∑_{n≥0}(−1)^{n} \frac{z^{3n}p^{3n}q^{\frac{3}{2} n^{2}− \frac{3}{2} n}}{(q; q)_{3n}}

+ ∑_{n≥0}(−1)^{n+1} \frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2} n^{2}+ \frac{3}{2} n+2}}{(q; q)_{3n+3}} ∑_{n≥1}(−1)^{n} \frac{z^{3n}p^{3n}q^{\frac{3}{2} n^{2}− \frac{7}{2} n}}{(q; q)_{3n−2}} .

The coefficient of (pz)^{3n+1} in the first sum is

(−1)^{n} ∑_{k=0}^{n} \frac{q^{\frac{3}{2} k^{2}− \frac{1}{2} k}}{(q; q)_{3k+1}} \frac{q^{\frac{3}{2} (n−k)^{2}− \frac{3}{2} (n−k)}}{(q; q)_{3n−3k}} = (−1)^{n}q^{\frac{3}{2} n(n−1)} ∑_{k=0}^{n} \frac{q^{k(3k+1)−3kn}}{(q; q)_{3k+1}(q; q)_{3n−3k}};

the coefficient of (pz)^{3n+1} in the second sum is

(−1)^{n+1}q^{\frac{3}{2} n(n−1)} ∑_{k=0}^{n} \frac{q^{3k^{2}−k(3n−1)}}{(q; q)_{3k+1}(q; q)_{3n−3k}} + (−1)^{n} \frac{q^{\frac{3}{2} n^{2}− \frac{1}{2} n}}{(q; q)_{3n+1}} ;

so the combination of both is simply

(−1)^{n} \frac{q^{\frac{3}{2} n^{2}− \frac{1}{2} n}}{(q; q)_{3n+1}} .

This proves that

f(1) = ∑_{n≥0}(−1)^{n} \frac{z^{3n+1}p^{3n+1}q^{\frac{3}{2} n^{2}− \frac{1}{2} n}}{(q; q)_{3n+1}} / ∑_{n≥0}(−1)^{n} \frac{z^{3n}p^{3n}q^{\frac{3}{2} n^{2}− \frac{3}{2} n}}{(q; q)_{3n}} ,

as claimed.

3. A generalization

We briefly report on the more general pattern up… up–down, with k − 1 up steps always followed by a down step (except possibly at the right border). Details of these computations are to be found in [7]. There are four cases to be considered:

First, we consider n ≡ 0 mod k. For the pattern (≤≤ ⋯ ≤≥)^{∗}, the probability generating function is

1/ ∑_{n≥0}(−1)^{n} \frac{z^{kn}q^{\frac{k}{2} n^{2}− \frac{k}{2} n}}{[kn]_{q}!} .

For the pattern (≤≤ ⋯ ≤>)^{∗}, the probability generating function is

1/ ∑_{n≥0}(−1)^{n} \frac{z^{kn}}{[kn]_{q}!}.

For the pattern (<< ⋯ <≥)^{∗}, the probability generating function is

1/ ∑_{n≥0}(−1)^{n} \frac{z^{kn}q^{\frac{k^{2}}{2} n^{2}− \frac{k}{2} n}}{[kn]_{q}!} .

Finally, for the pattern (<< ⋯ <>)^{∗}, the probability generating function is given by

1/ ∑_{n≥0}(−1)^{n} \frac{z^{kn}q^{\frac{k(k−1)}{2} n^{2}}}{[kn]_{q}!} .

Next, we consider n ≡ t mod k, where t = 1, 2, …, k −1. That means that we consider t−1 extra up steps at the right border. For the pattern (≤≤ ⋯ ≤≥)^{∗} ≤^{t−1}, the probability generating function is

∑_{n≥0} (−1)^{n} \frac{z^{kn+t}q^{\frac{k}{2} n^{2}+(t− \frac{k}{2})n}}{[kn + t]_{q}!} / ∑_{n≥0}(−1)^{n} \frac{z^{kn}q^{\frac{k}{2} n^{2}− \frac{k}{2} n}}{[kn]_{q}!} .

For the pattern (≤≤ ⋯ ≤>)^{∗} ≤^{t−1}, the probability generating function is

∑_{n≥0} (−1)^{n} \frac{z^{kn+t}}{[nk + t]_{q}!}/ ∑_{n≥0}(−1)^{n} \frac{z^{kn}}{[kn]_{q}!}.

For the pattern (<< ⋯ <≥)^{∗} <^{t−1}, the probability generating function is

∑_{n≥0} (−1)^{n} \frac{z^{kn+t}q^{\frac{k^{2}}{2} n^{2}+(t− \frac{1}{2} )kn+ \frac{t(t−1)}{2}}}{[kn + t]_{q}!} / ∑_{n≥0}(−1)^{n} \frac{z^{kn}q^{\frac{k^{2}}{2} n^{2}− \frac{k}{2} n}}{[kn]_{q}!} .

Finally, for the pattern (<< ⋯ <>)^{∗} <^{t−1}, the probability generating function is given by

∑_{n≥0} (−1)^{n} \frac{z^{kn+t}q^{\frac{k(k−1)}{2} n^{2}+(k−1)tn+ \frac{t(t−1)}{2}}}{[nk + t]_{q}!} / ∑_{n≥0}(−1)^{n} \frac{z^{kn}q^{\frac{k(k−1)}{2} n^{2}}}{[kn]_{q}!} .

We sketch again the instance (≤≤ ⋯ ≤≥)^{∗}: Maple computes in analogy to (1)

u^{i} ⟶ ∑_{i≤j≤k≤l≥h} pq^{j−1}pq^{k−1}pq^{l−1}pq^{h−1}u^{h}

= \frac{p^{4}uq^{3i}}{q^{3}(q; q)_{3}(1 − qu)} − \frac{up^{4}u^{i}q^{4i}}{q^{3}(qu; q)_{4}} ,

as well as the next instance (a five fold sum)

u^{i} ⟶ \frac{p^{5}uq^{4i}}{q^{4}(q; q)_{4}(1 − qu)} − \frac{up^{5}u^{i}q^{5i}}{q^{4}(qu; q)_{5}} ,

from which it is easy to guess the general substitution formula and to prove it by induction. This leads to the recursion

a_{n+1}(u) = \frac{p^{k}u}{q^{k−1}(q; q)_{k−1}(1 − qu)}a_{n}(q^{k−1}) − \frac{p^{k}u}{q^{k−1}(qu; q)_{k}} a_{n}(q^{k}u).

The rest of the proof is then as in the previous section.

4. Other patterns

The method we use is suitable to deal with other patterns as well. As an example, we consider words (and permutations in the limit) of length ≡ 1 mod 4 satisfying the pattern (≤≤>>)^{∗}. A relatively straight forward computation leads to

a_{1}(u) = \frac{pu}{1 − qu},

and for n ≥ 1

a_{n+1}(u) = \frac{p^{3}u}{q(q; q)_{2}(1 − q^{2}u)}a_{n}(q^{2}) − \frac{p^{4}u}{q^{3}(q; q)_{3}(1 − qu)}a_{n}(q^{3}) + \frac{p^{4}}{q^{4}(qu; q)_{4}} a_{n}(q^{4}u).

We translate that into a generating function,

f(u) = ∑_{n≥1} z^{4n−3}a_{n}(u).

With this notation we get the functional equation

f(u) = \frac{zpu}{1 − qu} + \frac{z^{4}p^{3}u}{q(q; q)_{2}(1 − q^{2}u)}f(q^{2}) − \frac{z^{4}p^{4}u}{q^{3}(q; q)_{3}(1 − qu)}f(q^{3}) + \frac{z^{4}p^{4}}{q^{4}(qu; q)_{4}} f(q^{4}u). (2)

We must compute f(q^{2}) and f(q^{3}):

f(q^{2}) = \frac{zpq^{2}}{1 − q^{3}} + \frac{z^{4}p^{3}q^{2}}{q(q; q)_{2}(1 − q^{4})}f(q^{2}) − \frac{z^{4}p^{4}q^{2}}{q^{3}(q; q)_{3}(1 − q^{3})}f(q^{3})

+ \frac{z^{4}p^{4}}{q^{4}(q^{3}; q)_{4}} [\frac{zpq^{6}}{1 − q^{7}} + \frac{z^{4}p^{3}q^{6}}{q(q; q)_{2}(1 − q^{8})}f(q^{2}) − \frac{z^{4}p^{4}q^{6}}{q^{3}(q; q)_{3}(1 − q^{7})}f(q^{3})

+ \frac{z^{4}p^{4}}{q^{4}(q^{7}; q)_{4}} [\frac{zpq^{10}}{1 − q^{11}} + \frac{z^{4}p^{3}q^{10}}{q(q; q)_{2}(1 − q^{12})}f(q^{2}) − \frac{z^{4}p^{4}q^{10}}{q^{3}(q; q)_{3}(1 − q^{11})}f(q^{3})

+ \frac{z^{4}p^{4}}{q^{4}(q^{11}; q)_{4}} [ + …

So defining the auxiliary quantities

α = q^{2} ∑_{n≥0} \frac{z^{4n+1}p^{4n+1}}{(q^{3}; q)_{4n+1}} ,

β = 1 − \frac{q}{p} ∑_{n≥1} \frac{z^{4n}p^{4n}}{(q; q)_{4n−2}(1 − q^{4n})},

γ = −\frac{1}{q(q; q)_{3}} ∑_{n≥1} \frac{z^{4n}p^{4n}}{(q^{3}; q)_{4n−3}} ,

we get

f(q^{2})β = α + γf(q^{3}).

Similarly,

f(q^{3}) = \frac{zpq^{3}}{1 − q^{4}} + \frac{z^{4}p^{3}q^{3}}{q(q; q)_{2}(1 − q^{5})}f(q^{2}) − \frac{z^{4}p^{4}q^{3}}{q^{3}(q; q)_{3}(1 − q^{4})}f(q^{3})

+ \frac{z^{4}p^{4}}{q^{4}(q^{4}; q)_{4}} [\frac{zpq^{7}}{1 − q^{8}} + \frac{z^{4}p^{3}q^{7}}{q(q; q)_{2}(1 − q^{9})}f(q^{2}) − \frac{z^{4}p^{4}q^{7}}{q^{3}(q; q)_{3}(1 − q^{8})}f(q^{3})

+ \frac{z^{4}p^{4}}{q^{4}(q^{8}; q)_{4}} [\frac{zpq^{11}}{1 − q^{12}} + \frac{z^{4}p^{3}q^{11}}{q(q; q)_{2}(1 − q^{13})}f(q^{2}) − \frac{z^{4}p^{4}q^{11}}{q^{3}(q; q)_{3}(1 − q^{12})}f(q^{3})

+ \frac{z^{4}p^{4}}{q^{4}(q^{12}; q)_{4}} [ …,

or, with

δ = q^{3} ∑_{n≥0} \frac{z^{4n+1}p^{4n+1}}{(q^{4}; q)_{4n+1}} ,

ρ = \frac{q^{2}}{p(q; q)_{2}} ∑_{n≥1} \frac{z^{4n}p^{4n}}{(q^{4}; q)_{4n−4}(1 − q^{4n+1})},

σ = ∑_{n≥0} \frac{z^{4n}p^{4n}}{(q; q)_{4n}} ,

we get

f(q^{3})σ = δ + ρf(q^{2}).

Solving the system we find

f(q^{2}) = \frac{ασ + γδ}{βσ − γρ},
f(q^{3}) = \frac{αρ + βδ}{βσ − γρ}.

Now we can compute f(1):

f(1) = \frac{zp}{1 − q} + \frac{z^{4}p^{3}}{q(q; q)_{2}(1 − q^{2})}f(q^{2}) − \frac{z^{4}p^{4}}{q^{3}(q; q)_{3}(1 − q)}f(q^{3})

+ \frac{z^{4}p^{4}}{q^{4}(q; q)_{4}} [\frac{zpq^{4}}{1 − q^{5}} + \frac{z^{4}p^{3}q^{4}}{q(q; q)_{2}(1 − q^{6})}f(q^{2}) − \frac{z^{4}p^{4}q^{4}}{q^{3}(q; q)_{3}(1 − q^{5})}f(q^{3})

+ \frac{z^{4}p^{4}}{q^{4}(q^{5}; q)_{4}} [\frac{zpq^{8}}{1 − q^{9}} + \frac{z^{4}p^{3}q^{8}}{q(q; q)_{2}(1 − q^{10})}f(q^{2}) − \frac{z^{4}p^{4}q^{8}}{q^{3}(q; q)_{3}(1 − q^{9})}f(q^{3})

+ \frac{z^{4}p^{4}}{q^{4}(q^{9}; q)_{4}} [ …,

or, with

λ = ∑_{n≥0} \frac{z^{4n+1}p^{4n+1}}{(q; q)_{4n+1}} ,

μ = \frac{1}{pq(q; q)_{2}} ∑_{n≥0} \frac{z^{4n+4}p^{4n+4}}{(q; q)_{4n}(1 − q^{4n+2})},

ν = \frac{1}{q^{3}(q; q)_{3}} ∑_{n≥1} \frac{z^{4n}p^{4n}}{(q; q)_{4n−3}} ,

f(1) = λ + μf(q^{2}) − νf(q^{3}).

We are not aiming to simplify this expression in the general case. However, we move straight to the limit q → 1, to study permutations. At this stage it seems necessary to make the variable z (and residue class (mod 4)) explicit: We write H_{1}(z) := f(1). Then

H_{1}(z) = λ + μ\frac{ασ + γδ}{βσ − γρ} − ν \frac{αρ + βδ}{βσ − γρ},

with

α = 2 ∑_{n≥0} \frac{z^{4n+1}}{(4n + 3)!},

β = 1 − ∑_{n≥1} \frac{z^{4n}}{(4n − 2)!(4n)},

γ = −\frac{1}{3} ∑_{n≥1} \frac{z^{4n}}{(4n − 1)!},

δ = 6 ∑_{n≥0} \frac{z^{4n+1}}{(4n + 4)!},

ρ = 3 ∑_{n≥1} \frac{z^{4n}}{(4n − 1)!(4n + 1)},

σ = ∑_{n≥0} \frac{z^{4n}}{(4n)!},

λ = ∑_{n≥0} \frac{z^{4n+1}}{(4n + 1)!},

μ = \frac{1}{2} ∑_{n≥0} \frac{z^{4n+4}}{(4n)!(4n + 2)},

ν = \frac{1}{6} ∑_{n≥1} \frac{z^{4n}}{(4n − 3)!}.

All these series can be expressed by exponential functions as follows:

α = \frac{1}{2z^{2}} [e^{z} + ie^{iz} − e^{−z} − ie^{−iz}] ,
β = \frac{1}{4} [e^{z} + e^{iz} + e^{−z} + e^{−iz}] − \frac{z}{4} [e^{z} + ie^{iz} − e^{−z} − ie^{−iz}] ,
γ = −\frac{z}{12} [e^{z} + ie^{iz} − e^{−z} − ie^{−iz}] ,
δ = −\frac{6}{z^{3}} + \frac{3}{2z^{3}} [e^{z} + e^{iz} + e^{−z} + e^{−iz}] ,
ρ = \frac{3}{4} [e^{z} + e^{iz} + e^{−z} + e^{−iz}] − \frac{3}{4z} [e^{z} − ie^{iz} − e^{−z} + ie^{−iz}] ,
σ = \frac{1}{4} [e^{z} + e^{iz} + e^{−z} + e^{−iz}] ,
λ = \frac{1}{4} [e^{z} − ie^{iz} − e^{−z} + ie^{−iz}] ,
μ = \frac{z^{3}}{8} [e^{z} − ie^{iz} − e^{−z} + ie^{−iz}] − \frac{z^{2}}{8} [e^{z} − e^{iz} + e^{−z} − e^{−iz}] ,
ν = \frac{z^{3}}{24} [e^{z} − ie^{iz} − e^{−z} + ie^{−iz}] .

Finally, this allows to express the generating function of interest as

H_{1}(z) = (1 + i)\frac{−ie^{(1+i)z} − e^{(−1+i)z} + ie^{(−1−i)z} + e^{(1−i)z}}{e^{(1+i)z} + e^{(−1+i)z} + 4 + e^{(−1−i)z} + e^{(1−i)z}} .

Here is the list of the first coefficients (normalized by factorials, to make them the number of permutations satisfying the pattern (≤≤>>)^{n}, for n = 0, 1, 2, …):

1, 6, 1456, 2020656, 9336345856, 108480272749056, 2664103110372192256, 122840808510269863827456, 9758611490955498257378246656, 1251231616578606273788469919481856, 245996119743058288132230759497577005056, ….

This sequence is not in Sloane’s encyclopedia [5, 6].

Now we sketch briefly what happens for the other residue classes (mod 4). They can all be obtained from f(u) by appropriate substitutions.

For an extra up step ≤, we must compute H_{2}(z) := \frac{z}{q} f(q). Starting from the functional equation (2) we obtain

\frac{1}{q}f(q) = ∑_{n≥0} \frac{p^{4n+1}z^{4n+1}}{(q^{2}; q)_{4n+1}} + \frac{f(q^{2})}{pq(q; q)_{2}} ∑_{n≥1} \frac{p^{4n}z^{4n}}{(q^{2}; q)_{4n−4}(1 − q^{4n−1})} − \frac{f(q^{3})}{q^{3}(q; q)_{3}} ∑_{n≥1} \frac{p^{4n}z^{4n}}{(q^{2}; q)_{4n−3}} .

If we let

λ_{1} = ∑_{n≥0} \frac{p^{4n+1}z^{4n+1}}{(q^{2}; q)_{4n+1}} ,

ϱ = \frac{1}{pq(q^{2}; q)} ∑_{n≥1} \frac{p^{4n}z^{4n}}{(q; q)_{4n−3}(1 − q^{4n−1})},

ω = \frac{1}{q^{3}(q; q)_{3}} ∑_{n≥1} \frac{p^{4n}z^{4n}}{(q^{2}; q)_{4n−3}} ,

we obtain

\frac{1}{q}f(q) = λ_{1} + \frac{σα + γδ}{βα − γρ}ϱ − \frac{ρα + βδ}{βα − γρ}ω.

Again, we concentrate on the limit q → 1, to study permutations. So

H_{2}(z) = z(λ_{1} + \frac{σα + γδ}{βα − γρ}ϱ − \frac{ρα + βδ}{βα − γρ}ω)

where

λ_{1} = ∑_{n≥0} \frac{z^{4n+1}}{(4n + 1)!},
ϱ = \frac{1}{2} ∑_{n≥1} \frac{z^{4n}}{(4n − 3)!(4n − 1)},
ω = \frac{1}{6} ∑_{n≥1} \frac{z^{4n}}{(4n − 2)!}.

The three series ω, ϱ and λ_{1} can be expressed by exponential functions as follows:

λ_{1} = \frac{1}{4}[e^{z} − ie^{iz} − e^{−z} + ie^{−iz}],
ϱ = \frac{z^{2}}{8} [e^{z} − e^{iz} + e^{−z} − e^{−iz}) − \frac{z}{8}(e^{z} + ie^{iz} − e^{−z} − ie^{−iz}],
ω = \frac{z^{2}}{24}[e^{z} − e^{iz} + e^{−z} − e^{−iz}].

This allows us to express the generating function of interest as follows:

H_{2}(z) = −i\frac{e^{(1+i)z} − e^{(1−i)z} − e^{(−1+i)z} + e^{(−1−i)z}}{e^{(1+i)z} + e^{(1−i)z} + 4 + e^{(−1+i)z} + e^{(−1−i)z}} .

The first few values are 1, 26, 10576, 20551376, 122087570176, 1733786041150976, corresponding to n = 2, 6, 10, 14, 18. For two extra up steps ≤≤, we must compute H_{3}(z) := \frac{z^{2}}{q(1+q)}f(q^{2}). In the limit q → 1, this becomes

H_{3}(z) = 2\frac{e^{z} − e^{−z} + ie^{iz} − ie^{−iz}}{e^{(1+i)z} + e^{(1−i)z} + 4 + e^{(−1+i)z} + e^{(−1−i)z}} .

The first few values are 1, 71, 45541, 120686411, 908138776681, corresponding to n = 3, 7, 11, 15, 19. Finally, for 3 extra steps ≤≤> we compute

H_{0}(z) := 1 + \frac{z^{3}}{q^{2}(1 + q)}f(q^{2}) − \frac{z^{3}}{q^{3}(1 + q)(1 + q + q^{2})}f(q^{3}).

In the limit q → 1, this becomes

H_{0}(z) = 2\frac{e^{z} + e^{−z} + e^{iz} + e^{−iz}}{e^{(1+i)z} + e^{(1−i)z} + 4 + e^{(−1+i)z} + e^{(−1−i)z}} .

The first few values are 1, 3, 413, 397023, 1402815833, corresponding to n = 0, 4, 8, 12, 16. Remark. Alternative expressions are as follows: If we define (following Carlitz)

ϕ_{i}(z) = ∑_{n≥0} \frac{z^{4n+i}}{(4n + i)!}, for i = 0, 1, 2, 3,

(these are the functions Φ_{4,i}(z) from the Introduction) and N := ϕ_{0}(z)^{2} − ϕ_{1}(z)ϕ_{3}(z), then

H_{1}(z) = \frac{ϕ_{1}(z)ϕ_{0}(z) − ϕ_{2}(z)ϕ_{3}(z)}{N},

H_{2}(z) = \frac{ϕ_{2}(z)ϕ_{0}(z) − ϕ_{3}^{2}(z)}{N} = \frac{ϕ_{1}^{2}(z) − ϕ_{3}^{2}(z)}{2N},
H_{3}(z) = \frac{ϕ_{3}(z)}{N},
H_{0}(z) = \frac{ϕ_{0}(z)}{N}.

Carlitz and Scoville in [2, 3] have such results. However, in [2, p. 47] we see a result that is difficult to interpret; there is a drawing of an up-up-down-down permutation of a length ≡ 1 mod 4, but its length is denoted by 4n − 1; as a generating function the authors give

\frac{ϕ_{1}(z)ϕ_{2}(z) − ϕ_{0}(z)ϕ_{3}(z)}{N} = 2\frac{z^{3}}{3!} + 132\frac{z^{7}}{7!} + …,

but there is only one permutation of length 3 satisfying that pattern.

The equivalence of the two forms for H_{2}(z) follow from the relation ϕ_{1}^{2}(z) + ϕ_{3}^{2}(z) = 2ϕ_{0}(z)ϕ_{2}(z), given by [3, (3.12)].

References

[1] L. Carlitz, Generating Functions for a Special Class of Permutations. Proc. Amer. Math. Soc. 47 (1975), 251–256.

[2] L. Carlitz and R. Scoville, Enumeration of Rises and Falls by Position. Discrete Math. 5 (1973), 45–59.

[3] L. Carlitz and R. Scoville, Generating Functions for Certain Types of Permutations. J. Comb. Theory (A) 18 (1975), 262–275.

[4] H. Prodinger, Combinatorics of Geometrically Distributed Random Variables: New q–Tangent and q– Secant Numbers. Internat. J. Math. and Math. Sci. 24 (2000), 825–838.

[5] N. J. A. Sloane, The On–line Encyclopedia of Integer Sequences, 2001, published electronically, http://www.research.att.com/∼njas/sequences/.

[6] N. J. A. Sloane and S. Plouffe, The On–line Encyclopedia of Integer Sequences, 1995, Academic Press.

[7] T. A. Tshifhumulo, Combinatorics of Geometrically Distributed Random Variables: Words and Permutations Avoiding and Satisfying Contiguous Patterns. PhD Thesis (2002).

(H. P.) The John Knopfmacher Centre for Applicable Analysis and Number Theory, University of the Witwatersrand, Private Bag 3, WITS 2050, South Africa

E-mail address: helmut@cam.wits.ac.za
URL: http://www.wits.ac.za/helmut/index.htm

(T. A. T) The John Knopfmacher Centre for Applicable Analysis and Number Theory, University of the Witwatersrand, Private Bag 3, WITS 2050, South Africa

E-mail address: tat@univen.ac.za