A Bijective Proof of Garsia’s q-Lagrange Inversion Theorem

Dan W. Singer Tiernan Communications 5751 Copley Drive San Diego, CA 92111

                  dsinger@tiernan.com

Submitted: March 4, 1997 Accepted: April 25, 1998

Abstract A q-Lagrange inversion theorem due to A. M. Garsia is proved by means of two sign-reversing, weight-preserving involutions on Catalan trees.

1 Introduction

Let F (u) be a formal power series with F (0) = 0, F′(0) ≠ 0 (delta series). Then F (u) has an inverse f(u) which satisfies

∑_{n=k}^{∞} F (u)^{k}|u_{n} f(u)^{n} = u^{k}

and

∑_{n=k}^{∞} f(u)^{k}|u_{n} F (u)^{n} = u^{k}

for all k ≥ 1, where |u^{n} means extract the coefficient of u^{n}.

The coefficients of f(u)^{n} may be expressed in terms of the coefficients of F (u) by means of the Lagrange inversion formula

f(u)^{n}|u^{k} = \frac{u^{n}F′(u)}{F (u)^{k+1}} |u^{−1} .

AMS Subject Classification 05E99 (primary), 05A17 (secondary)

Keywords: q-Lagrange inversion, Catalan trees

The q-Lagrange inversion problem may be stated as follows: given a delta series F (u) and a sequence of formal power series {F_{k}(u)} which is a q-analogue of {F (u)^{k}}, find {f_{k}(u)} such that

∑_{n=k}^{∞} F_{k}(u)|u^{n} f_{n}(u) = u^{k}  (1.1)

and

∑_{n=k}^{∞} f_{k}(u)|u^{n} F_{n}(u) = u^{k}  (1.2)

for all k ≥ 1. If {f_{k}(u)} satisfies equations (1.1) and (1.2) then f_{k}(u) is a qanalogue of f(u)^{k} for each k, where f(u) = F^{−1}(u). We say that {F_{k}(u)} and {f_{k}(u)} are inverse sequences.

There are several solutions to the q-Lagrange inversion problem appearing in the literature — see for example Andrews [2], Garsia [7], Garsia and Remmel [9], Gessel [10], Gessel and Stanton [11][12], Hofbauer [13], Krattenthaler [15], Singer [17][18]. Singer [17] proved an inversion theorem, based on a generalization of Garsia’s operator techniques, which unifies and extends the q-Lagrange inversion theorems of Garsia [7] and Garsia-Remmel [9]. Garsia, Gessel and Stanton, and Singer have shown that Rogers-Ramanujan type identities may be derived by means of q-Lagrange inversion.

Several authors have given quite distinct bijective proofs of q-series identities, many of which may be interpreted as statements about partitions – see Andrews [1][3], Bressoud [4], Garsia and Milne [8], Joichi and Stanton [14], Sylvester [19]. An exceptional example is Garsia and Milne’s proof of the Rogers-Ramanujan identities [16], making use of the involution principle. Bressoud and Zeilberger gave an alternative, much shorter proof of these identities in [5]. Zeilberger gave a q-Foata proof of the q-Pfaff-Saalschütz identity [20], inspired by Foata’s bijective proof of the Pfaff-Saalschütz identity [6].

In view of the fact that so many q-series identities may be derived by means of q-Lagrange inversion as well as by bijective methods, it is desirable to have a combinatorial interpretation of the inverse relations (1.1) and (1.2).

In this paper we will give a bijective proof, using sign-reversing, q-weight preserving involutions applied to Catalan trees, of the following q-Lagrange inversion theorem due to Garsia ([7], Theorem 1.1):

Theorem 1.1. Let F (u) be a delta series with F′(0) = 1. Then there is a unique delta series f(u) which satisfies

∑_{k=1}^{∞} F_{k}f(u)f(uq) ⋯ f(uq^{k−1}) = u.  (1.3)

Moreover, {f(u)f(uq) ⋯ f(uq^{k−1})} and {F (u)F (u/q) ⋯ F (u/q^{k−1})} are inverse sequences, that is

∑_{i=k}^{∞} F (u)F (u/q) ⋯ F (u/q^{k−1})|u^{i} f(u)f(uq) ⋯ f(uq^{i−1}) = u^{k}  (1.4)

and

∑_{i=k}^{∞} f(u)f(uq) ⋯ f(uq^{k−1})|u^{i} F (u)F (u/q) ⋯ F (u/q^{i−1}) = u^{k}  (1.5)

for all k ≥ 1.

Our proof of Theorem 1.1 is organized as follows. We will assume

F (u) = ∑_{k=1}^{∞} F_{k}u^{k}  (1.6)

is given to us with F_{1} = 1. In Section 2 we will define C, the set of Catalan trees. We will exhibit f(u) in terms of C, show that it satisfies (1.3), and prove uniqueness. In Section 3 we will make some additional definitions regarding Catalan trees and prove three lemmas we shall require later. We will then give distinct bijective proofs of equations (1.4) and (1.5), in Sections 4 and 5, respectively.

2 The set of Catalan trees

We exhibit f(u) combinatorially as follows. Let C be the set of rooted, planar trees whose internal vertices have out-degree ≥ 2. We refer to C as the set of Catalan trees. We denote by C_{p} the set of Catalan trees with p external vertices. We have

C_{1} = { }
C_{2} = { }
C_{3} = { , , }
C_{4} = {  , , , , , , , ,  , , }

and so on. We denote by |T | the number of external vertices of the tree T. Observe that for p ≥ 2 we have

C_{p} = ⋃_{k=2}^{p} { : T_{1}, …, T_{k} ∈ C, |T_{1}| + ⋯ + |T_{k}| = p}.

For each tree T in C we will define a scalar-weight w_{s}(T), a q-weight w_{q}(T), and a composite weight w(T) = w_{s}(T)w_{q}(T). We then set

f(u) = ∑_{T ∈C} w(T)u^{|T |},

and show that f(u) has the desired properties.

The scalar-weight function w_{s} is defined recursively by

w_{s}( ) = 1,

w_{s}(  ) = −F_{k}w_{s}(T_{1})w_{s}(T_{2}) ⋯ w_{s}(T_{k}),

where the coefficients F_{k} are provided by (1.6). If T ∈ C and V_{I}(T) is the set of internal vertices of T, then clearly

w_{s}(T) = ∏_{v∈V_{I}(T)} (−F_{d(v)}),

where d(v) is the out-degree of v.

The q-weight function w_{q} is defined recursively by

w_{q}( ) = 1,

w_{q}(  ) = ∏_{i=1}^{k} w_{q}(T_{i})q^{(i−1)|T_{i}|}.

We now prove equation (1.3). We have

f(u) = ∑_{T ∈C} w_{s}(T)w_{q}(T)u^{|T |}
= u + ∑_{T ∈C\{ }} w_{s}(T)w_{q}(T)u^{|T |}

= u + ∑_{k=2}^{∞} ∑_{T_{1},...,T_{k}∈C} w_{s}(  )w_{q}(  )u^{|T_{1}|+···+|T_{k}|}

= u + ∑_{k=2}^{∞} ∑_{T_{1},...,T_{k}∈C} (−F_{k}) ∏_{i=1}^{k} w_{s}(T_{i})w_{q}(T_{i})q^{(i−1)|T_{i}|}u^{|T_{i}|}

= u − ∑_{k=2}^{∞} F_{k} ∏_{i=1}^{k} ∑_{T ∈C} w_{s}(T)w_{q}(T)q^{(i−1)|T |}u^{|T |}

= u − ∑_{k=2}^{∞} F_{k} ∏_{i=1}^{k} f(uq^{i−1}),

which implies (1.3).

We next show that f(u) is unique. Suppose a(u) is a delta series which satisfies

∑_{k=1}^{∞} F_{k}a(u)a(uq) ⋯ a(uq^{k−1}) = u.

We will prove

a(u)|u^{p} = ∑_{T ∈C_{p}} w(T) = f(u)|u^{p}

by induction on p.

We have

a(u) = u − ∑_{k=2}^{∞} F_{k}f(u)f(uq) ⋯ f(uq^{k−1}),

hence

a(u)|u^{1} = 1 = w( ).

Assume

a(u)|u^{n} = ∑_{T ∈C_{n}} w(T)

for all 1 ≤ n < p. Then

a(u)|u^{p} = − ∑_{k=2}^{∞} F_{k}a(u)a(uq) ⋯ a(uq^{k−1})|u_{p}
= − ∑_{k=2}^{∞} F_{k} ∑_{e_{1}+···+e_{k}=p} a(u)|u^{e_{1}} ⋯ a(u)|u^{e_{k}} q^{∑{k \atop i=1} (i−1)e_{i}}
= ∑_{k=2}^{∞} ∑_{e_{1}+···+e_{k}=p} (−F_{k}) ∏_{i=1}^{k} ∑_{T ∈C_{e_{i}}} w(T)q^{(i−1)|T |}

= ∑_{k=2}^{∞} ∑_{e_{1}+···+e_{k}=p} ∑_{T_{1}∈C_{e_{1}} ...T_{k}∈C_{e_{k}}} w(  )
= ∑_{T ∈C_{p}} w(T).

Therefore a(u) = f(u).

3 A closer look at Catalan trees

For any T ∈ C we define the crown of T, C(T), recursively as follows. If T is a height 0 or 1 tree then C(T) = T. If T has height ≥ 2, write

T = .

Let r be the least index such that T_{r} has height ≥ 1. We set C(T) = C(T_{r}).

If T ∈ C\{ } then C(T) is the height 1 subtree of T consisting of the depthfirst occurring height-maximal internal vertex of T and its successors in T. We will denote by D(T) the tree derived from T by replacing C(T) with an external vertex.

We label the position of the external vertices of any tree T by 1,2, …, |T | in depth-first order. We denote by P (T) the position of the depth-first external vertex of C(T) in T. These definitions are illustrated in Figure 3.1 and Figure 3.2.

Figure 3.1: C(T) and P (T)

The statistics P (T) and P (D(T)) are related as follows.

Lemma 3.1. For any tree T in C we have

P (T) ≤ P (D(T)) + |C(D(T))| − 1.  (3.1)

Figure 3.2: D(T)

Proof. If

T =  or  T =

then C(T) = T and D(T) = . Therefore P (T) = P (D(T)) = |C(D(T))| = 1, and (3.1) is true in this case.

Now let T be a height ≥ 2 tree. Write

T = .

Let r be least such that ht(T_{r}) > 0. Then we may write

T =  and  D(T) =  .

Suppose ht(T_{r}) = 1. Then C(T) = C(T_{r}) = T_{r} and P (T) = r. There are two cases to consider.

Case 1. ht(D(T)) = 1. In this case we have

C(D(T)) = D(T) = ,

P (D(T)) = 1, and

P (T) = r ≤ k = P (D(T)) + |C(D(T))| − 1.

Case 2. ht(D(T)) > 1. We are assuming that ht(T_{r}) = 1, hence D(T_{r}) = , and there must be a least index s > r such that ht(T_{s}) > 0. This implies C(D(T)) = C(T_{s}) and P (D(T)) ≥ s. Therefore

P (T) = r < s ≤ P (D(T)) ≤ P (D(T)) + |C(D(T))| − 1.

We prove the lemma in general by induction on ht(T), having treated the case ht(T) ≤ 1 above. Assume (3.1) is true for all trees of height ≤ a. Let T be a tree of height a + 1. Write

T = .

Since the root (as does every internal vertex) has out-degree ≥ 2, ht(T_{i}) ≤ a for each i. Let r be least such that ht(T_{r}) > 0. As before we may write

T =  and  D(T) =  .

We have C(T) = C(T_{r}) and P (T) = r − 1 + P (T_{r}). We may assume without loss of generality that ht(T_{r}) > 1, having treated the case ht(T_{r}) = 1 above. This allows us to write ht(D(T_{r})) > 0, C(D(T)) = C(D(T_{r})), and P (D(T)) = r − 1 + P (D(T_{r})). By the induction hypothesis we have

P (T_{r}) ≤ P (D(T_{r})) + |C(D(T_{r}))| − 1.

Therefore

P (T) = r − 1 + P (T_{r})
≤ r − 1 + P (D(T_{r})) + |C(D(T_{r}))| − 1
= P (D(T)) + |C(D(T))| − 1.

This completes the proof.

Let N be a height 1 tree. We denote by T ∨_{a}N the tree obtained by replacing the a^{th} external vertex of T in depth first order by N. We will need the following result.

Lemma 3.2. With notation as above, let S = T ∨_{a} N, where a ≤ P (T) + |C(T)| − 1. Then C(S) = N.

Proof. By induction on ht(T). The case ht(T) ≤ 1 is trivial. Consider ht(T) > 1. Write

T = .

Let r be the least index such that ht(T_{r}) > 0. Then we may write

T = .

Clearly C(S) = N in case a < r.

Now suppose we have

r ≤ a ≤ P (T) + |C(T)| − 1.

Since the depth-last external vertex of C(T) occupies position

P (T) + |C(T)| − 1

within T, and C(T) is found in T_{r}, N must be attached to T_{r}. Moreover, regarding T_{r} as an independent tree, N is attached to T_{r} at position a − r + 1. Write S_{r} = T_{r} ∨_{a−r+1} N. Then we may write

S = .

We have P (T) = r − 1 + P (T_{r}) and C(T) = C(T_{r}), hence

a − r + 1 ≤ (P (T) + |C(T)| − 1) − r + 1 = P (T_{r}) + |C(T_{r})| − 1.

Since ht(T_{r}) < ht(T), by the induction hypothesis we must have C(S_{r}) = N. Since C(S) = C(S_{r}), we are done.

We may q-label the external vertices of a tree T with positive integers in such a way that its q-weight is

w_{q}(T) = q sum of labels in T .

The labelling is defined by induction on the height of a tree.

Label the height 0 tree by 0. Having labelled the external vertices of all trees of height a or less, we label any height a + 1 tree

T =

by increasing every label in T_{i} by i − 1 for each i. The sum of the labels in T is

∑_{i=1}^{k} (i − 1)|T_{i}| + sum of labels in T_{i}.

Set

w_{L}(T) = q sum of labels in T .

We have

w_{L}( ) = 1,

w_{L}(  ) = q^{∑{k \atop i=1} (i−1)|T_{i}|+ sum of labels in T_{i}}
= ∏_{i=1}^{k} q^{(i−1)|T_{i}|}w_{L}(T_{i}),

hence w_{L}(T) = w_{q}(T) for all T.

The q-labelling of the tree shown in Figure 3.1 is depicted in Figure 3.3.

An important fact about the q-weight of a tree is recorded in the following lemma.

Lemma 3.3. For any T in C, w_{q}(T) and w_{q}(D(T)) are related by the equation

w_{q}(T) = w_{q}(D(T))q^{(P (T)−1)(|C(T)|−1)+\binom{|C(T)|}{2}}.  (3.2)

Proof. It will suffice to show that the depth-first q-label on C(T) in T is P (T)−1. If this is true then the labels on C(T) are

P (T) − 1, (P (T) − 1) + 1, …, (P (T) − 1) + |C(T)| − 1,

hence the sum of the labels on C(T) is

(P (T) − 1)|C(T)| + \binom{|C(T)|}{2}.

Figure 3.3: q-Labels

This contribution to the exponent of q in w_{q}(T) is replaced by P (T) − 1 in w_{q}(D(T)), since D(T) is obtained from T by replacing the crown by a single external vertex. Hence

sum of labels in T =

sum of labels in D(T) − (P (T) − 1) + (P (T) − 1)|C(T)| + \binom{|C(T)|}{2} =

sum of labels in D(T) + (P (T) − 1)(|C(T)| − 1) + \binom{|C(T)|}{2}.

This implies (3.2).

We show that the depth-first q-label on C(T) in T is P (T) − 1 by induction on |D(T)|. If |D(T)| = 1 then

T =  or  T =  .

In either case C(T) = T, hence P (T) = 1 and the depth-first label of C(T) is 0 = P (T) − 1.

Now assume that for all T such that |D(T)| ≤ a, the depth-first q-label on C(T) in T is P (T) − 1. Let T be a tree with |D(T)| = a + 1. Write

T = .

Since |D(T)| > 1, it must be true that some T_{i} has height ≥ 1. Let r be least such that ht(T_{r}) ≥ 1. Then T may be expressed in the form

.

We have |D(T_{r})| ≤ a. By the induction hypothesis, the depth-first q-label on C(T_{r}) in T_{r} (regarded as an independent tree, not a subtree of T) is P (T_{r}) − 1. By the way q-labelling is defined, the q-labels on T_{r} as a subtree of T are obtained by increasing each of the q-labels of T_{r} as an independent tree by r − 1. Hence the depth-first q-label on C(T_{r}) in T is P (T_{r})+r −2. But P (T) = r −1+P (T_{r}), therefore the depth-first q-label on C(T_{r}) in T is P (T)−1. Since C(T) = C(T_{r}), we are done.

On occasion we will identify C^{k}, the cartesian product of k copies of the set C, with the set of all Catalan trees whose root branches out to k subtrees. In this context we have

P (T_{1}, …, T_{k}) = P ( )

and

|(T_{1}, …, T_{k})| = |T_{1}| + ⋯ + |T_{k}|.

Given

T =

we define the statistic

B(T) = \{ \begin{matrix}0 & if T_{1} = ⋯ = T_{k} = , \\ max\{i : T_{i} ≠ \} & otherwise. \end{matrix}

We also set

B(T_{1}, …, T_{k}) = B( )

for any (T_{1}, …, T_{k}) ∈ C^{k}.

4 Proof of Equation 1.4

We will prove 1.4 for all k ≥ 2, the case k = 1 having been treated in Section 2. We denote by N the set of height 1 trees (nests). For each k ≥ 2 let R_{k} be the set of composite objects defined by

R_{k} = {(N, T) : N ∈ N^{k}, T ∈ C^{|N|}}.

For each composite object (N, T) ∈ R_{k} we define a scalar-weight W_{s}(N, T) and a q-weight W_{q}(N, T) as follows. Write N = (N_{1}, …, N_{k}) and T = (T_{1}, …, T_{|N|}). Say |N_{i}| = e_{i} for each i. We set

W_{s}(N, T) = ∏_{i=1}^{k} F_{e_{i}} ∏_{j=1}^{|N|} w_{s}(T_{j})

and

W_{q}(N, T) = ∏_{i=1}^{k} q^{−(i−1)e_{i}} · w_{q}(T).

We also set

W (N, T) = W_{s}(N, T)W_{q}(N, T).

Lemma 4.1.

∑_{(N,T)∈R_{k}} W (N, T)u^{|T |} =

∑_{p=k}^{∞} F (u)F (u/q) ⋯ F (u/q^{k−1})|u_{p} f(u)f(uq) ⋯ f(uq^{p−1}).

Proof. Observe that

W (N, T) = ∏_{i=1}^{k} F_{e_{i}}q^{−(i−1)e_{i}} ∏_{j=1}^{|N|} w(T_{j})q^{(j−1)|T_{j}|}.

Hence

∑_{(N,T)∈R_{k}} W (N, T)u^{|T |} =

∑_{p=k}^{∞} ∑_{e_{1}+···+e_{k}=p} ∑_{T_{1},...,T_{p}∈C} ∏_{i=1}^{k} F_{e_{i}}q^{−(i−1)e_{i}} ∏_{j=1}^{p} w(T_{j})q^{(j−1)|T_{j}|}u^{|T_{j}|} =

∑_{p=k}^{∞} ∑_{e_{1}+···+e_{k}=p} ∏_{i=1}^{k} F_{e_{i}}q^{−(i−1)e_{i}} ∏_{j=1}^{p} ∑_{T ∈C} w(T)q^{(j−1)|T |}u^{|T |} =

∑_{p=k}^{∞} F (u)F (u/q) ⋯ F (u/q^{k−1})|u_{p} f(u)f(uq) ⋯ f(uq^{p−1}).

Let N_{k} denote the vector ( \overbrace{, , …,}^{k} ). Then W (N_{k}, N_{k}) = 1 and |N_{k}| = k. In order to prove (1.4), we partition the set R′_{k} = R_{k}\{(N_{k}, N_{k})} into two disjoint sets R_{k}^{+} and R_{k}^{−}, and exhibit a sign reversing involution θ on R′_{k} which maps R_{k}^{+} onto R_{k}^{−}. That is, θ^{2} = identity and

W (θ(N, T)) = −W (N, T).  (4.1)

This will give us

∑_{(N,T)∈R_{k}} W (N, T)u^{|T |} = W (N_{k}, N_{k})u^{|N_{k}|} = u^{k}.  (4.2)

We then combine this result with Lemma 4.1.

We set

R_{k}^{+} = {(N, T) ∈ R_{k}\{(N_{k}, N_{k})} : B(T) ≤ |N| − P (N) + 1 and N ≠ N_{k}}

and

R_{k}^{−} = {(N, T) ∈ R_{k}\{(N_{k}, N_{k})} : B(T) > |N| − P (N) + 1 or N = N_{k}}.

We will actually construct two maps,

θ^{+} : R_{k}^{+} → R_{k}^{−}  and  θ^{−} : R_{k}^{−} → R_{k}^{+},

and show θ^{−}θ^{+} = θ^{+}θ^{−} = identity.

It is helpful to visualize composite objects in R_{k} as marked trees. Let (N, T) ∈ R_{k} be given. Write N = (N_{1}, …, N_{k}) and T = (T_{1}, …, T_{|N|}). We may form a single tree by placing each non-trivial T_{i} on top of the i^{th} external vertex of the tree

.

We mark the tree by distinguishing N.

For example, let

N = ( , ,  , ,  , ),

T = (  , , , ,  , , , ,  , , ).

We identify (N, T) with the marked tree in Figure 4.1.

Figure 4.1: (N, T)

This particular tree lies in R_{6}^{+}: we have |N| = 11, P (N) = 3, and B(T) = 9, therefore

B(T) ≤ |N| − P (N) + 1.

The maps θ^{+} and θ^{−} are defined as follows. The reader may wish to consult Figures 4.3–4.5 at this point for an illustration of the action of θ^{+}. Let (N, T) ∈ R_{k} be given. As before, we write N = (N_{1}, …, N_{k}) and = (T_{1}, …, T_{|N|}). We can regard N as a height ≤ 2 tree with a base branching out to k subtrees. Suppose (N, T) ∈ R_{k}^{+}. Then

B(T) ≤ |N| − P (N) + 1 and N ≠ N_{k}.

We set

θ^{+}(N, T) = (θ_{1}^{+}(N, T), θ_{2}^{+}(N, T)),

where

θ_{1}^{+}(N, T) = D(N),

θ_{2}^{+}(N, T) = (T_{1}, …, T_{|N|−|C(N)|−P (N)+1}, , \overbrace{, …,}^{P (N)−1} ),

and

S_{i} = T_{|N|−|C(N)|−P (N)+1+i} for 1 ≤ i ≤ |C(N)|.

Observe that the depth-last vertex of C(N) occupies position P (N)+|C(N)|−1 within N, hence P (N) + |C(N)| − 1 ≤ |N|. Therefore θ^{+} is well-defined in so far as |N| − |C(N)| − P (N) + 1 ≥ 0.

Lemma 4.2. With notation as above, the composite object θ^{+}(N, T) lies in R_{k}^{−}.

Proof. This is clear if D(N) = N_{k}. If D(N) ≠ N_{k}, we must verify

B(θ_{2}^{+}(N, T)) > |D(N)| − P (D(N)) + 1.  (4.3)

By construction we have B(θ_{2}^{+}(N, T)) = |N|−|C(N)|−P (N)+2. We also have |D(N)| = |N| − |C(N)| + 1. Hence (4.3) is equivalent to

|N| − |C(N)| − P (N) + 2 > |N| − |C(N)| + 1 − P (D(N)) + 1,

that is P (D(N)) > P (N). But this is clear because the restriction D(N) ≠ N_{k} means that N must be a height 2 tree with at least two nests at height one. The crown of N is the depth-first nest at height one in N. The crown of D(N) is the depth-second nest at height one in N. See Figure 4.2.

Figure 4.2: N versus D(N)

We now define θ^{−}. Consider (N, T) ∈ R_{k}^{−}. Then B(T) > |N| − P (N) + 1 or N = N_{k}.

Claim: B(T) > 0. This is clear if N = N_{k}, for then T ≠ N_{k}. If N ≠ N_{k}, then we must have

B(T) > |N| − P (N) + 1 ≥ 1.

Hence we may write

T = (T_{1}, …, T_{B(T)−1}, , \overbrace{, …,}^{|N|−B(T)} )

for some S_{1}, …, S_{b} ∈ C. We set

θ^{−}(N, T) = (θ_{1}^{−}(N, T), θ_{2}^{−}(N, T)),

where θ_{1}^{−}(N, T) is obtained by replacing N_{|N|−B(T)+1} by the nest

in N, and

θ_{2}^{−}(N, T) = (T_{1}, …, T_{B(T)−1}, S_{1}, …, S_{b}, \overbrace{, …,}^{|N|−B(T)} ).

Lemma 4.3. With notation as above, the composite object θ^{−}(N, T) lies in R_{k}^{+}.

Proof. Clearly θ_{1}^{−}(N, T) ≠ N_{k}. We must verify

B(θ_{2}^{−}(N, T)) ≤ |θ_{1}^{−}(N, T)| − P (θ_{1}^{−}(N, T)) + 1.  (4.4)

Note that if N=N_{k}, then the crown of θ_{1}^{−}(N, T) is the nest

.

If N ≠ N_{k}, then the condition

B(T) > |N| − P (N) + 1

forces

P (N) > |N| − B(T) + 1,

and the crown of θ_{1}^{−}(N, T) is again the nest

.

In either case, we have

P (θ_{1}^{−}(N, T)) = |N| − B(T) + 1.

We also have

|θ_{1}^{−}(N, T)| = |N| + b − 1.

Hence the inequality (4.4) is equivalent to

B(θ_{2}^{−}(N, T)) ≤ b + B(T) − 1.

This inequality is true because S_{b} occupies coordinate b+B(T)−1 in θ_{2}^{−}(N, T).

In order to see that θ^{−}θ^{+} = θ^{+}θ^{−} = identity, it is useful to look at an example. Consider the composite object (N, T) ∈ R^{+} depicted in Figure 4.1. The action of θ^{+} on (N, T) is the following. Write (N, T) as an exploded diagram by separating the non-trivial trees in T from N and recording their relative positions in depth-first order. See Figure 4.3.

Figure 4.3: (N, T) exploded

Remove C(N) from N and reattach at the external vertex of D(N) located by walking back P (N) positions from the depth-last external vertex. Call this new tree I(N). See Figure 4.4. The relocated nest is labelled R.

Figure 4.4: I(N)

The position of R on D(N) is

|D(N)| − P (N) + 1 = |N| − |C(N)| − P (N) + 2.

R forms the base for a tree in θ_{2}^{+}(N, T). To obtain θ^{+}(N, T) we reattach the non-trivial trees of T at the same relative positions on I(N). See Figure 4.5.

Since the depth-last external vertex on R occupies position

(|N| − |C(N)| − P (N) + 2) + (|C(N)| − 1) = |N| − P (N) + 1 ≥ B(T)

within I(N), none of the non-trivial trees in T clear R. Therefore R is the base for the depth-last non-trivial tree sitting on D(N) in θ^{+}(N, T), and

B(θ_{2}^{+}(N, T)) = |N| − |C(N)| − P (N) + 2.

The action of θ^{−} reverses this procedure. The base R is removed and then replaced on D(N) at position

|θ_{1}^{+}(N, T)| − B(θ_{2}^{+}(N, T)) + 1 =

(|N| − |C(N)| + 1) − (|N| − |C(N)| − P (N) + 2) + 1 = P (N).

Therefore N is recovered. The non-trivial trees among

T_{1}, …, T_{B}(T)

Figure 4.5: θ^{+}(N, T)

are replaced on N in the same relative positions they occupied on I(N). Hence T is recovered.

The action of θ^{−} in general is to take the base

of

T_{B(T)} =

and replace it on N at position |N| − B(T) + 1, forming the crown of θ_{1}^{−}(N, T). The non-trivial trees among

T_{1}, …, T_{B(T)−1}, S_{1}, …, S_{b}

are replaced on θ_{1}^{−}(N, T) at the same relative positions. θ^{+} reverses this procedure: I(θ_{1}^{−}(N, T)) is obtained from θ_{1}^{−}(N, T) by removing

C(θ_{1}^{−}(N, T)) =

from θ_{1}^{−}(N, T) and replacing it on D(θ_{1}^{−}(N, T)) at position

|θ_{1}^{−}(N, T)| − |C(θ_{1}^{−}(N, T))| − P (θ_{1}^{−}(N, T)) + 2 =

(|N| + b − 1) − b − (|N| − B(T) + 1) + 2 = B(T).

Hence N and the base of T_{B(T)} are recovered. T is recovered when the nontrivial trees among

T_{1}, …, T_{B(T)−1}, S_{1}, …, S_{b}

are replaced on N.

The next two Lemmas show that θ is a sign-reversing, q-weight-preserving involution. It will suffice to show that θ^{+} is sign-reversing and q-weight-preserving.

Lemma 4.4.

W_{s}(θ^{+}(N, T)) = −W_{s}(N, T).

Proof. Write N = (N_{1}, …, N_{k}) and T = (T_{1}, …, T_{|N|}). Recall that

θ^{+}(N, T) = (θ_{1}^{+}(N, T), θ_{2}^{+}(N, T)),

where

θ_{1}^{+}(N, T) = D(N),

θ_{2}^{+}(N, T) = (T_{1}, …, T_{|N|−|C(N)|−P (N)+1}, , \overbrace{, …,}^{P (N)−1} ),

and

S_{i} = T_{|N|−|C(N)|−P (N)+1+i} for 1 ≤ i ≤ |C(N)|.

For any S = (S_{1}, …, S_{k}) ∈ C^{k} let V_{I}^{k}(S) denote the set of internal vertices of the trees S_{1}, S_{2}, …, S_{k}. Then

W_{s}(N, T) = ( ∏_{v∈V_{I}^{k}(N)} F_{d(v)})( ∏_{v∈V_{I}^{k}(T)} (−F_{d(v)}))

and

W_{s}(θ^{+}(N, T)) = ( ∏_{v∈V_{I}^{k}(D(N))} F_{d(v)})( ∏_{v∈V_{I}^{k}(θ_{2}^{+}(N,T))} (−F_{d(v)})),

where d(v) is the out-degree of v. V_{I}^{k}(D(N)) is obtained from V_{I}^{k}(N) by removing the root of C(N). V_{I}^{k}(θ_{2}^{+}(N, T)) is obtained from V_{I}^{k}(T) by adding the root of C(N) in its new position in θ_{2}^{+}(N, T). Hence the factor F_{|C(N)|} in W_{s}(N, T) is replaced by −F_{|C(N)|} in W_{s}(θ^{+}(N, T)). Therefore W_{s}(θ^{+}(N, T)) = −W_{s}(N, T). the electronic journal of combinatorics 5 (1997), #R26 22 Lemma 4.5.

W_{q}(θ^{+}(N, T)) = W_{q}(N, T).

Proof. We have

W_{q}(N, T) = q^{−0|N_{1}|−1|N_{2}|−···(P (N)−1)|C(N)|−···−(k−1)|N_{k}|}
×w_{q}( )

and

W_{q}(θ^{+}(N, T)) = q^{−0|N_{1}|−1|N_{2}|−···−(P (N)−1)·1−···−(k−1)|N_{k}|}

×w_{q}( ),

where a = |N| − P (N) + 1 ≥ B(T) and b = |N| − |C(N)| − P (N) + 1. Note that T_{1}, …, T_{a} have the same q-labels in both

A =

and

B = .

Hence

w_{q}(A) = ∏_{i=1}^{a} w_{q}(T_{i})q^{(i−1)|T_{i}|}q^{∑{|N| \atop i=a+1} (i−1)}
= ∏_{i=1}^{a} w_{q}(T_{i})q^{(i−1)|T_{i}|}q^{\binom{|N|}{2}−\binom{|N|−P (N)+1}{2}}

and

w_{q}(B) = ∏_{i=1}^{a} w_{q}(T_{i})q^{(i−1)|T_{i}|}q^{∑{|N|−|C(N)|+1 \atop i=b+2} (i−1)}

= ∏_{i=1}^{a} w_{q}(T_{i})q^{(i−1)|T_{i}|}q^{\binom{|N|−|C(N)|+1}{2}−\binom{|N|−|C(N)|−P (N)+2}{2}}.

Therefore

\frac{W_{q}(N, T)}{W_{q}(θ^{+}(N, T))} =

q^{−(P (N)−1)(|C(N)|−1)+\binom{|N|}{2}−\binom{|N|−P (N)+1}{2}−\binom{|N|−|C(N)|+1}{2}+\binom{|N|−|C(N)|−P (N)+2}{2}} = 1.

Lemmas 4.4 and 4.5 taken together yield equations (4.1) and (4.2), hence we have completed the proof of equation (1.4).

5 Proof of Equation 1.5

For each k ≥ 1 let S_{k} be the set of composite objects defined by

S_{k} = {(T, N) : T ∈ C^{k} and N ∈ N^{|T |}},

where as before N is the set of height one trees. For each composite object (T, N) ∈ S_{k} we define a scalar weight W′_{s}(T, N) and a q-weight W′_{q}(T, N) as follows. Write T = (T_{1}, …, T_{k}) and N = (N_{1}, …, N_{|T |}). Say |N_{i}| = e_{i} for each i. We set

W′_{s}(T, N) = ∏_{i=1}^{k} w_{s}(T_{i}) ∏_{j=1}^{|T |} F_{e_{j}}

and

W′_{q}(T, N) = w_{q}(T) ∏_{j=1}^{|T |} q^{−(j−1)e_{j}}.

We also set

W′(T, N) = W′_{s}(T, N)W′_{q}(T, N).

Lemma 5.1.

∑_{(T,N)∈S_{k}} W′(T, N)u^{|N|} =

∑_{p=k}^{∞} f(u)f(uq) ⋯ f(uq^{k−1})|u_{p} F (u)F (u/q) ⋯ F (u/q^{p−1}).

Proof. Observe that

W′(T, N) = ∏_{i=1}^{k} w(T_{i})q^{(i−1)|T_{i}|} ∏_{j=1}^{|T |} F_{e_{j}}q^{−(j−1)e_{j}}.

Hence

∑_{(T,N)∈S_{k}} W′(T, N)u^{|N|} =

∑_{p=k}^{∞} ∑_{(T_{1},...,T_{k})∈C_{p}} ∑_{e_{1},...,e_{p}≥1} ∏_{i=1}^{k} w(T_{i})q^{(i−1)|T_{i}|} ∏_{j=1}^{p} F_{e_{j}}q^{−(j−1)e_{j}}u^{e_{j}} =

∑_{p=k}^{∞} ∏_{i=1}^{k} ( ∑_{T ∈C} w(T)q^{(i−1)|T |}u^{|T |})|u^{p} ∏_{j=1}^{p} ∑_{r=1}^{∞} F_{r}q^{−(j−1)r}u^{r} =

∑_{p=k}^{∞} f(u)f(uq) ⋯ f(uq^{k−1})|u_{p} F (u)F (u/q) ⋯ F (u/q^{p−1}).

As before, let N_{k} denote the vector ( \overbrace{, , …,}^{k} ). Then W′(N_{k}, N_{k}) = 1. In order to prove (1.5), we partition the set S_{k}\{(N_{k}, N_{k})} into two disjoint sets S_{k}^{+} and S_{k}^{−} and exhibit a sign-reversing involution ϕ which maps S_{k}^{+} onto S_{k}^{−}. This will give us

∑_{(T,N)∈S_{k}} W′(T, N)u^{|N|} = W′(N_{k}, N_{k})u^{|N_{k}|} = u^{k}.  (5.1)

We then combine this result with Lemma 5.1

We set

S_{k}^{+} = {(T, N) ∈ S_{k}\{(N_{k}, N_{k})} : |T | − |C(T)| − P (T) + 2 > B(N)} and

S_{k}^{−} = {(T, N) ∈ S_{k}\{(N_{k}, N_{k})} : |T | − |C(T)| − P (T) + 2 ≤ B(N)}.

We will actually construct two maps,

ϕ^{+} : S_{k}^{+} → S_{k}^{−}  and  ϕ^{−} : S_{k}^{−} → S_{k}^{+},

and show ϕ^{−}ϕ^{+} = ϕ^{+}ϕ^{−} = identity.

As before it is helpful to visualize composite objects as marked trees. Let (T, N) ∈ S_{k} be given. Write T = (T_{1}, …, T_{k}) and N = (N_{1}, …, N_{|T |}). We may form a single tree by placing each non-trivial N_{i} on top of the i^{th} external vertex of the tree

.

We mark the tree by distinguishing T.

For example, let

T = ( ,  , , ,  ),

N = ( ,  , , , , ,  , , , , , , , , , )

We identify (T, N) with marked tree in Figure 5.1. This particular tree lies in

S_{5}^{+}: we have |T | = 16, P (T) = 3, |C(T)| = 3, and B(N) = 7, therefore

|T | − |C(T)| − P (T) + 2 > B(N).

The maps ϕ^{+} and ϕ^{−} are defined as follows. (The reader may wish to consult Figures 5.2–5.4.) Let (T, N) ∈ S_{k} be given. Write T = (T_{1}, …, T_{k}) and N = (N_{1}, …, N_{|T |}). We can regard T as a tree whose root branches out to k subtrees. Suppose (T, N) ∈ S_{k}^{+}. Then

|T | − |C(T)| − P (T) + 2 > B(N).

We set

ϕ^{+}(T, N) = (ϕ_{1}^{+}(T, N), ϕ_{2}^{+}(T, N)),

where

ϕ_{1}^{+}(T, N) = D(T),

Figure 5.1: (T, N)

ϕ_{2}^{+}(T, N) = ( \overbrace{N_{1}, …, N_{B(N)}, , …, C(T), …,}^{|D(T)|} ),

and C(T) is in position

|T | − |C(T)| − P (T) + 2.

ϕ^{+} is well-defined because |D(T)| = |T | − |C(T)| + 1 ≥ |T | − |C(T)| − P (T) + 2 > B(N).

Lemma 5.2. With notation as above, ϕ^{+}(T, N) lies in S_{k}^{−}. Proof. We need to verify

|D(T)| − |C(D(T))| − P (D(T)) + 2 ≤ B(ϕ_{2}^{+}(T, N)).  (5.2)

We have

|D(T)| = |T | − |C(T)| + 1

and

B(ϕ_{2}^{+}(T, N)) = |T | − |C(T)| − P (T) + 2,

hence (5.2) is equivalent to

P (T) ≤ P (D(T)) + |C(D(T))| − 1.

But this is true by Lemma 3.1 the electronic journal of combinatorics 5 (1997), #R26 27

Now suppose (T, N) ∈ S_{k}^{−}. Then

|T | − |C(T)| − P (T) + 2 ≤ B(N).

We set

ϕ^{−}(T, N) = (ϕ_{1}^{−}(T, N), ϕ_{2}^{−}(T, N)),

where

ϕ_{1}^{−}(T, N) = T ∨_{|T |−B(N)+1} N_{B(N)}

and

ϕ_{2}^{−}(T, N) = (N_{1}, …, \overbrace{N_{B(N)}}^{omit} , \overbrace{, …,}^{|N_{B(N)}|} ).

Recall that T ∨_{a} N is the result of attaching N to T at external vertex a. Note that

|T | ≥ P (T) + |C(T)| − 1

implies

B(N) ≥ |T | − |C(T)| − P (T) + 2 ≥ 1.

Lemma 5.3. With notation as above, ϕ^{−}(T, N) lies in S_{k}^{+}. Proof. We must verify

|ϕ_{1}^{−}(T, N)| − |C(ϕ_{1}^{−}(T, N))| − P (ϕ_{1}^{−}(T, N)) + 2 > B(ϕ_{2}^{−}(T, N)).  (5.3)

We have

|ϕ_{1}^{−}(T, N)| = |T | + |N_{B(N)}| − 1.

The condition

|T | − |C(T)| − P (T) + 2 ≤ B(N)

forces

|T | − B(N) + 1 ≤ P (T) + |C(T)| − 1.

By Lemma 3.2 this implies

C(ϕ_{1}^{−}(T, N)) = N_{B(N)}.

Therefore

P (ϕ_{1}^{−}(T, N)) = |T | − B(N) + 1.

Hence (5.3) is equivalent to

(|T | + |N_{B(N)}| − 1) − |N_{B(N)}| − (|T | − B(N) + 1) + 2 > B(ϕ_{2}^{−}(T, N)),

that is

B(N) > B(ϕ_{2}^{−}(T, N)).

But this is true by construction.

In order to see that ϕ^{−}ϕ^{+} = ϕ^{+}ϕ^{−} = identity, it is again useful to have an example in mind. Consider the composite object (T, N) ∈ S_{k}^{+} depicted in Figure 5.1. The action of ϕ^{+} on (T, N) is the following. Write (T, N) as an exploded diagram by separating the non-trivial trees in N from T and recording their relative positions in depth-first order. See Figure 5.2.

Figure 5.2: (T, N) exploded

Remove C(T) from T and reattach as part of ϕ_{2}^{+}(T, N) at the external vertex of D(T) located by walking back P (T) positions from the depth-last external vertex. See Figure 5.3. The relocated nest is labelled S.

The position of S on D(T) is

|D(T)| − P (T) + 1 = |T | − |C(T)| − P (T) + 2 > B(N).

Figure 5.3: relocated nest

Hence the non-trivial nests of N may be reattached to D(T) in their same relative positions, all to the left of S in depth-first order. The result is ϕ^{+}(T, N). See Figure 5.4. Note that we now have

B(ϕ_{2}^{+}(T, N)) = |T | − |C(T)| − P (T) + 2.

The action of ϕ^{−} reverses this procedure. The nest S is removed and replaced on D(T) at position

|D(T)| − B(ϕ_{2}^{+}(T, N)) + 1 =
(|T | − |C(T)| + 1) − (|T | − |C(T)| − P (T) + 2) + 1 = P (T).

Hence T is recovered. The non-trivial nests among

N_{1}, …, N_{B(N)}

are then replaced in the same relative positions. Hence N is recovered.

The action of ϕ^{−} in general is to remove N_{B(N)} and replace it on T at position

|T | − B(N) + 1,

forming the crown of ϕ_{1}^{−}(T, N). The remaining non-trivial nests of N are placed on ϕ_{1}^{−}(T, N) in the same relative positions. ϕ^{+} reverses this procedure: the crown

C(ϕ_{1}^{−}(T, N)) = N_{B(N)}

Figure 5.4: ϕ^{+}(T, N)

is removed and replaced as a nest on

D(ϕ_{1}^{−}(T, N)) = T

at position

|ϕ_{1}^{−}(T, N)| − |C(ϕ_{1}^{−}(T, N))| − P (ϕ_{1}^{−}(T, N)) + 2 =

(|T | + |N_{B(N)}| − 1) − |N_{B(N)}| − (|T | − B(N) + 1) + 2 = B(N).

The rest of the non-trivial nests of N are then placed on T in the same relative positions. Hence (T, N) is recovered.

We now show

W′(ϕ^{+}(T, N)) = −W′(T, N).  (5.4)

We clearly have

W′_{s}(ϕ^{+}(T, N)) = −W′_{s}(T, N)  (5.5)

because, arguing as in Lemma 4.4, the factor −F_{|C(N)|} in W′_{s}(T, N) is replaced by F_{|C(N)|} in W′_{s}(ϕ^{+}(T, N)).

Lemma 5.4. With notation as above, W′_{q}(ϕ^{+}(T, N)) = W′_{q}(T, N). the electronic journal of combinatorics 5 (1997), #R26 31 Proof. We have

W′_{q}(T, N) = w_{q}(T) ∏_{i=1}^{|T |} q^{−(i−1)|N_{i}|}
= w_{q}(T) ∏_{i=1}^{B(N)} q^{−(i−1)|N_{i}|} · q^{− ∑_{j=B(N)+1}^{|T |} (j−1)}
= w_{q}(T) ∏_{i=1}^{B(N)} q^{−(i−1)|N_{i}|} · q^{−\binom{|T |}{2}+\binom{B(N)}{2}}

Now

ϕ^{+}(T, N) = (D(T), ϕ_{2}^{+}(T, N)),

where

ϕ_{2}^{+}(T, N)) = ( \overbrace{N_{1}, …, N_{B(N)}, , …, C(T), …,}^{|D(T)|} )

and C(T) is in position

|T | − |C(T)| − P (T) + 2.

Hence

W′_{q}(ϕ^{+}(T, N)) =

w_{q}(D(T)) ∏_{i=1}^{B(N)} q^{−(i−1)|N_{i}|}

×q^{− ∑_{j=B(N)+1}^{|D(T)|} (j−1) + |T |−|C(T)|−P (T)+2−1} ×q^{−(|T |−|C(T)|−P (T)+2−1)|C(T)|}

= w_{q}(D(T)) ∏_{i=1}^{B(N)} q^{−(i−1)|N_{i}|} · q^{−\binom{|D(T)|}{2}+\binom{B(N)}{2}−(|T |−|C(T)|−P (T)+1)(|C(T)|−1)}.

Hence

\frac{W′_{q}(T, N)}{W′_{q}(ϕ^{+}(T, N))} =

\frac{w_{q}(T)}{w_{q}(D(T))}q^{−\binom{|T |}{2}+\binom{|D(T)|}{2}+(|T |−|C(T)|−P (T)+1)(|C(T)|−1)} =

\frac{w_{q}(T)}{w_{q}(D(T))}q^{−\binom{|T |}{2}+\binom{|T |−|C(T)|+1}{2}+(|T |−|C(T)|−P (T)+1)(|C(T)|−1)}.

By Lemma 3.3,

\frac{w_{q}(T)}{w_{q}(D(T))} = q^{(P (T)−1)(|C(T)|−1)+\binom{|C(T)|}{2}}.

Hence

\frac{W′_{q}(T, N)}{W′_{q}(ϕ^{+}(T, N))} = q^{−\binom{|T |}{2}+\binom{|T |−|C(T)|+1}{2}+(|T |−|C(T)|)(|C(T)|−1)+\binom{|C(T)|}{2}} = 1.

Combining equation (5.5) with Lemma 5.4, we arrive at equation (5.4). This yields (5.1) and completes the proof of (1.5).

6 Conclusion

In the course of proving Theorem 1.1 we have discovered some properties of Catalan trees. While there may be many sign-reversing involutions giving rise to a bijective proof of equations (1.4) and (1.5) when q = 1, it appears that only two of these are invariant with respect to the q-labelling of trees. In [17] the author derived the Rogers-Ramanujan type identity

∑_{k=0}^{∞} \frac{(−q^{2}; q^{4})_{k}q^{k^{2}}}{(q^{4}; q^{4})_{k}(q; q^{2})_{k}} = \frac{(−q^{4}; q^{8})_{∞}}{(q; q^{2})_{∞}} ,

which has a ready interpretation in terms of partitions. This identity was derived by replacing q by q^{2} and u by −q in

∑_{k=0}^{∞} \frac{(−q; q^{2})_{k}(−1)^{k}q^{\binom{k}{2}}u^{k}}{(q^{2}; q^{2})_{k}(−u; q)_{k}} = \frac{(−u^{2}q; q^{4})_{∞}}{(−u; q)_{∞}} .

The latter identity was derived as an example of q-functional composition, and the left-hand side can be expressed combinatorially in terms of weighted Catalan trees. It would be fruitful to seek bijective proofs for identities such as these for the information they contain about trees in addition to partitions and Ferrers diagrams.

References

[1] G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics 2, Addison- Wesley Publishing Company, Reading, Massachusetts, 1976.

[2] G. E. Andrews, Identities in combinatorics, II: A q–analog of the Lagrange inversion theorem, Proc. Amer. Math. Soc. 53 (1975), 240–245.

[3] G. E. Andrews, Multiple series Rogers-Ramanujan type identities, Pacific J. Math. 114 (1984), 267–283.

[4] D. M. Bressoud, Analytic and Combinatorial generalizations of the Rogers-Ramanujan identities, Memoirs Amer. Math. Soc. 227 (1980).

[5] D. M. Bressoud and D. Zeilberger, A short Rogers-Ramanujan bijection, Discrete Math. 38 (1982), 313–315.

[6] D. Foata, Une demonstration combinatoire de l’identité de Pfaff-Saalschütz, C. R. Acad. Sci. Paris, Ser. I, 297 (1983), 221–224.

[7] A. M. Garsia, A q–analogue of the Lagrange inversion formula, Houston J. Math. 7 (1981), 205–237.

[8] A. M. Garsia and S. C. Milne, A Rogers-Ramanujan Bijection, J. Comb. Theory Ser. A 31 (1981), 289–339.

[9] A. M. Garsia and J. Remmel, A novel form of q–Lagrange inversion, Houston J. Math. 12 (1986), 503–523.

[10] I. Gessel, A non-commutative generalization and q-analogue of the Lagrange inversion formula, Trans. Amer. Math. Soc. 257 (1980), 455–481.

[11] I. M. Gessel and D. Stanton, Applications of q–Lagrange inversion to basic hypergeometric series, Trans. Amer. Math. Soc. 277 (1983), 173–201.

[12] I. M. Gessel and D. Stanton, Another family of q–Lagrange inversion inversion formulas, Rocky Mountain J. Math 16 (1986), 373–384.

[13] J. Hofbauer, A q–analogue of the Lagrange expansion, Arch. Math. 42 (1984), 536–544.

[14] J. T. Joichi and D. Stanton, Bijective proofs of basic hypergeometric series identities, Pacific J. Math., 127, no. 1, (1987), 103–120.

[15] C. Krattenthaler, Operator methods and Lagrange inversion: a unified approach to Lagrange formulas, Trans. Amer. Math. Soc. 305 (1988), 431-465.

[16] S. Ramanujan and L. J. Rogers, Proof of certain identities in combinatory analysis, Proc. London Math. Soc. 19 (1919), 211–216.

[17] D. Singer, Q-Analogues of Lagrange Inversion, Adv. Math. 155 (1995), no. 1, 99–116.

[18] D. Singer, Errata in Q-Analogues of Lagrange Inversion, submitted to Advances in Mathematics.

[19] J. J. Sylvester, A constructive theory of partitions, arranged in three acts an interact and exodion, Amer. J. Math. 5 (1882), 251–330, or pages 1– 83 of The Collected Papers, Vol. 4, Cambridge University Press, London, 1912; reprinted by Chelsea, New York, 1974.

[20] D. Zeilberger, A q-Foata proof of the q-Saalschütz identity, Europ. J. Combin. 8 (1987), 461–463.