Séminaire Lotharingien de Combinatoire 54 (2006), Article B54f

COUNTING UPPER INTERACTIONS IN DYCK PATHS

YVAN LE BORGNE^{1}

Dédié à Xavier Viennot^{∗}

Abstract. Upper and lower interactions are parameters of Dyck paths which are motivated by corresponding parameters in a model of partially directed polymers. We investigate the problem of obtaining the generating function for Dyck paths with respect to upper interactions in terms of basic hypergeometric q-series in which an algebraic term occurs.

1. Introduction

A Dyck word w is a word over the alphabet \{x, \overline{x}\} that contains as many letters x as letters \overline{x} and such that any prefix contains at least as many letters x as letters \overline{x}. The size of w is the number of letters x in w. A Dyck path is a walk in the plane, that starts from the origin, is made up of rises, i.e. steps (1, 1), and falls, i.e. steps (1, −1), remains above the horizontal axis and finishes on it. Figure 1 gives an example of a Dyck path of size 12. The Dyck path related to a Dyck word w is the walk obtained by representing a letter x by a rise, and a letter \overline{x} by a fall. In this paper we identify the two notions. An upper interaction, respectively a lower interaction, in a Dyck word w is an occurrence of a factor \overline{x}^{k}x^{k}, respectively x^{k}\overline{x}^{k}, for any k ≥ 1. The example of Figure 1 contains 7 upper interactions and 9 lower interactions.

x x x  x  x x  x  x x x  x x \overline{x}  \overline{x} \overline{x} \overline{x}  \overline{x} \overline{x}  \overline{x}  \overline{x} \overline{x}  \overline{x} \overline{x} \overline{x} A  Lower interaction Upper interaction  B = (21, 3)

Figure 1. A Dyck path and its upper and lower interactions

These upper and lower interactions are translations in terms of Dyck paths of physical quantities studied by physicists [13], [7] in a model of self-interacting partially directed polymers near a surface. Enumeration of Dyck paths leads to generating functions syntactically smaller than those of partially directed polymers without avoiding the main enumerative difficulty. Thus we restrict ourselves to the study of Dyck paths. To simplify the enumeration we distinguish between upper and lower interactions. We consider both enumerations of Dyck paths: according to the size and the number of lower interactions and according to the size and the number of upper interactions. It remains to consider the enumeration according to the three parameters to recover a variation of the model suggested by physicists. It is still an open problem to take into account both types of interactions.

Key words and phrases. Dyck paths, catalytic parameters, slice functional equations, linearization of q-algebraic equations, basic hypergeometric series.

1The author was partially supported by the network Algebraic Combinatorics in Europe (ACE).

∗The starting point of this work is an act of faith in the ”Viennotique”: Equation (3) is an instance of the inversion lemma for a class of heaps of pieces. This article describes some clues found during the inverstigation of these heaps of pieces. The frustration, generated by the lack of a final proof using the bijective method, is eased by the opportunity to present to Xavier Viennot a problem where it just remains to find the bijection.

Lower interactions are the easier kind of interaction to take into account in enumeration. According to the usual decomposition of Dyck paths which splits them at the first return to the horizontal axis, the vertex A in Figure 1, each lower interaction is included in one of the two sub-walks. Denise and Simion [6] have already used this fact to enumerate Dyck paths according to their size and their number of lower interactions. In contrast, there are upper interactions above the vertex A that belong to the two sub-walks. The number of upper interactions above the vertex A depends on the numbers of consecutive falls just before A and consecutive rises just after A. Hence, in contrast to the situation for lower interactions, counting upper interactions is not directly compatible with the usual recursive decomposition of Dyck paths. It is the purpose of this paper to investigate how this additional difficulty may be approached.

We present two methods to find an expression for the generating function

A(t, u) = ∑_{w} t^{n}u^{k}  (1)

where w runs over non-empty Dyck paths, n is the size of w and k the number of upper interactions.

In Section 2, the first method, inspired by a work of Bousquet-Mélou and Rechnitzer [3], consists of building Dyck words by inserting a factor x^{i}\overline{x}^{i} after the last letter x. This leads to a functional equation that can be solved through calculations over formal power series involving four main steps: an iteration, the kernel method [2], a division and the use of a relation between the roots of a polynomial. The resulting generating function, see (3), has a rather unusual form: it is a ratio of q-series, with q = tu, in which an algebraic series σ ≡ σ(t, u) occurs.

Delest and Fédou Klarner  ^{B_{2}}^{A_{2}}^{B_{1}}^{A_{1}}^{A}  ^{B}

Figure 2. A staircase polyomino and two kinds of decomposition

With the first approach we obtain a formula for the generating function A(t, u). Before we explain our motivation for other methods, we briefly summarise the solutions of a similar problem: the enumeration of staircase polyominos according to their half-perimeter and their area. The leftmost picture in Figure 2 gives an example of a staircase polyomino. It is a convex subset of the plane whose frontier is defined by two walks, made up of North, (0, 1), and East, (1, 0) steps that intersect only at their endpoints A = (0, 0) and B. The half-perimeter is the common length of the two walks and the area is the number of unit squares enclosed by the two walks. Three approaches have been proposed for this enumeration. Klarner [9] considers the addition of a column to the right of the polyomino to write a q-linear equation. This equation is similar to (2) of Section 2, but is simpler in the sense that its solution does not require the kernel method, thus there is no algebraic term like σ in the resulting ratio of q-series. Delest and Fédou [12] detect a recursive factorisation of a polyomino into two smaller polyominos by inspection of the first column of height 1 if there is one. This decomposition leads to a q-quadratic equation for which there is no general solution, but they were able to guess the solution and check that it was correct. Bousquet-Mélou and Viennot [4] defined a bijection between polyominos and certain heaps of segments. Thus the generating function appears as an instance of the general inversion lemma for heap models [14]: the numerator and denominator of the formula are generating functions of certain simpler subsets of heaps which satisfy solvable q-linear equations.

The generating functions for Dyck paths according to their size and their number of upper interactions, and for polyominos according to their half-perimeter and their area, are very similar ratios of q-Bessel-like series with, in our case, the additional algebraic term σ. This similarity suggests that the same three approaches for the enumeration of Dyck paths may be feasible. The likelihood of some hidden combinatorics in A(t, u) is increased by the fact that σ, resulting from an application of the kernel method, is the generating function for Dyck paths according to their size and their number of lower interactions. With regards to the physical model, we are interested in a more combinatorial derivation of A(t, u) in order to propose combinatorial objects whose generating functions reflect the different dominant singularities of A(t, u), which correspond to different phases of the model. From a combinatorial point of view, we are looking for another example, in a more general context, of three derivations of the same result respectively based on a slice-equation, on a q-quadratic equation and on a bijection with a heap model. We want to compare these approaches in order to improve them. For example, the solution of certain q-quadratic equations seems to rely on a Riccatti-like Ansatz already discussed in particular cases in [5].

In Section 3, we consider Dyck paths with small valleys, i.e. Dyck words that avoid the factor \overline{x}\overline{x}xx. An ad hoc valuation of the valleys, i.e. the factors \overline{x}x, may be chosen in such a way that the generating function for weighted Dyck paths with small valleys coincides with the generating function A(t, u). We can recursively split these words, and after the introduction of an additional parameter we obtain a q-algebraic equation. Solving this equation requires a change of unknown functions. The choice of this change is crucial to the solution. One change, proposed in (18), implies less calculation than others, suggested by the literature, in order to obtain the generating function (16).

In Section 4 we compare the two methods. First, the additional parameter of the second method can be taken into account by the first method, leading to the same syntactical generating function as in Section 3. In fact, we guessed the efficient Ansatz (18) by inspecting the generating function obtained this way. Then we discuss the possible homographic changes of unknown functions to solve certain quadratic q-algebraic equations, comparing them with previous work [5], [8], [1].

This work is an extract from the chapter on upper interactions of the author’s thesis [10], where the third approach, using heaps of pieces introduced by Viennot [14], is also presented. An extended abstract of this chapter is available in [11].

2. Appending a factor x^{k}\overline{x}^{k} and a slice equation

In [3], Bousquet-Mélou and Rechnitzer use a factorisation of partially directed walks. We use their method for the enumeration of Dyck paths according to their size and their number of upper interactions. In Section 2.1 we find the functional equation (2) satisfied by the generating function and in Section 2.2 we solve this equation and obtain in (3) an expression in terms of q-series.

2.1. A decomposition using the last factor x^{k}\overline{x}^{k}

Let w be a Dyck path/word. The height of a vertex (i, j) in w is j. A peak, respectively a valley, is a vertex of w following a rise and preceding a fall, respectively following a fall and preceding a rise. The length of the last descent l(w) of w is the height of the rightmost peak. This is also the number of letters \overline{x} after the last letter x. In the path w_{1} in Figure 1 the rightmost peak is B = (21, 3) so l(w_{1}) = 3.

A non-empty Dyck path w is either of the form x^{k}\overline{x}^{k} with k ≥ 1, or else contains at least one valley, thus factors as u\overline{x}x^{k}\overline{x}^{k}\overline{x}^{j}, where v = u\overline{x}^{j+1} is a non-empty Dyck path, j ≥ 0 and k ≥ 1. In the second case we want to deduce from v, j and k the number of upper interactions in w. In addition to the number up(v) of upper interactions in v we have to know the length l(v) of the last descent of v:

up(w) = up(v) + min(k, l(v) − j).

Moreover, the length of the last descent of w is l(w) = k + j. Thus, given a Dyck path v and an appropriate choice of j and k, we can build the Dyck path w. The knowledge of l(v) allows us to compute the number of added upper interactions and l(w). We are not interested in the enumeration according to the length of the last descent but we will use this parameter as a temporary information in the decomposition the Dyck path, a terminology proposed by Zeilberger [15] calls it a catalytic parameter.

We add the length of the last descent to the enumeration to define the generating function

B(t, u; s) = ∑_{w} t^{n}u^{m}s^{l}

where w runs over non-empty Dyck paths, n is the size of w, m the number of upper interactions in w and l is the length of the last descent.

We will often write B(s) instead of B(t, u; s), and, accordingly, B(1) instead of B(t, u; 1) and B(uts) instead of B(t, u; uts).

Lemma 1. The generating function B(s) for non-empty Dyck paths counted according to their size, their number of upper interactions and their length of the last descent satisfies

\begin{aligned}B(s) & = & \frac{ts}{1 − ts} + \frac{ut}{1 − ut} \frac{ts (B(s) − B(uts))}{1 − ts} \\ & & +\frac{ut}{1 − ut} (\frac{s}{1 − s} (B(1) − B(s)) − \frac{uts (B(1) − B(uts))}{1 − uts}) . \end{aligned}  (2)

Proof. We split the set of Dyck paths into three disjoint subsets, as illustrated on Figure 3: the set B_{1} of paths with one peak, the set B_{2} of paths where the last peak is strictly higher than the previous one, and the set B_{3} of paths where the last peak is below the previous one. For each set we define a generating function B_{i}(s) ≡ B_{i}(t, u; s) as above. Thus

B(s) = B_{1}(s) + B_{2}(s) + B_{3}(s).

B^{1}  +  A B B^{2} C  j i +  DB^{3} F E  j i

Figure 3. The ”slice” decomposition of Dyck paths

Each path of each subset is obtained by adding a factor x^{k}\overline{x}^{k} to a smaller one: to the empty path for the first subset B_{1}, or to any non-empty Dyck path otherwise. The length of the last descent is sufficient to determine in each case, both the number of ways in which one can extend a Dyck path and the number of additional upper interactions. Figure 3 gives examples of each kind of extension leading to paths of each of the three subsets. The summation of the extensions over all Dyck paths leads to the generating function for each subset and contains different evaluations of the series B(s) (B(s), B(qs) and B(1)):

• The paths of B_{1} = \{x^{k}\overline{x}^{k}, k ≥ 1\} are defined by the height k of their single peak which is also the rightmost one, thus

B_{1}(s) = ∑_{k=1}^{∞} t^{k}s^{k} = \frac{ts}{1 − ts}.

• Let v = ux\overline{x}^{l} be a non-empty Dyck path whose rightmost peak is denoted A. To build a path w ∈ B_{2} we insert into the rightmost vertex at height l − i a factor x^{i+j}\overline{x}^{j+i}, 1 ≤ i ≤ l and j ≥ 1. We insert a valley B at height l − i and a peak C at height l + j into the path w = ux\overline{x}^{l−i}x^{i+j}\overline{x}^{j+l}. This insertion increases the size of v by i + j and creates exactly i upper interactions. The new rightmost peak is at height l + j. In terms of generating functions, the previous remark leads to

B_{2}(s) = ∑_{l≥1} ∑_{v∈D_{l}} (∑_{i=1}^{l} ∑_{j=1}^{∞} t^{n+i+j}u^{m+i}s^{l+j}) ,

where D_{l} is the set of Dyck paths whose rightmost peak is at height l, n is the size of v, m the number of upper interactions in v. The summations of geometric sums with respect to i and j give

B_{2}(s) = \frac{ts}{1 − ts} \frac{ut}{1 − ut} ∑_{l≥1} ∑_{v∈D_{l}} (t^{n}u^{m}s^{l} − t^{n}u^{m}(tus)^{l}) ,

where we recognise B(s) and B(uts), thus

B_{2}(s) = \frac{ts}{1 − ts} \frac{ut}{1 − ut} (B(s) − B(uts)) .

• Let v = ux\overline{x}^{l} be a non-empty Dyck path whose rightmost peak is D. To build a path w ∈ B_{3} we insert in the rightmost vertex of height i − j a factor x^{j}\overline{x}^{j} where j ≤ i ≤ l. We create a valley F at height i − j and a new rightmost peak E at height i into w = ux\overline{x}^{l−i+j}x^{j}\overline{x}^{i}. The size increases by j and the number of upper interactions also by j. In terms of generating functions, keeping the same notations, we have

B_{3}(s) = ∑_{l≥1} ∑_{v∈D_{l}} t^{n}u^{m} (∑_{i=1}^{l} s^{i} (∑_{j=1}^{i} t^{j}u^{j})) .

In that case the two geometric sums according to i and j are not independent. Their summations lead to

B_{3}(s) = \frac{ut}{1 − ut} ∑_{l≥1} ∑_{v∈D_{l}} (\frac{s}{1 − s} (t^{n}u^{m} − t^{n}u^{m}s^{l}) − \frac{uts}{1 − uts} (t^{n}u^{m} − t^{n}u^{m}(uts)^{l})) ,

where we recognise B(1), B(s) and B(uts). Thus

B_{3}(s) = \frac{ut}{1 − ut} (\frac{s}{1 − s} (B(1) − B(s)) − \frac{uts}{1 − uts} (B(1) − B(uts))) .

The generating function for each subset gives one of the three terms in the right-hand side of (2). □

2.2. Solution

The solution of (2) requires an iteration to remove B(uts) and then an application of the kernel method, presented for example in [2], to remove B(s). As in [3], we obtain for B(1) = A(t, u) a ratio of two q-series in which an algebraic term occurs. Let q ≡ ut be a notation has used in q-calculus and consistent with the usual notation (x)_{n} = ∏_{k=0}^{n−1}(1 − q^{k}x), intensively used here.

Proposition 2. The generating function for Dyck paths counted according to their size and their number of upper interactions can be written as

A(t, u) = B(1) = −\frac{t ∑_{n≥0} (\frac{(q − t)σ}{1 − q} )^{n} \frac{q^{\binom{n+2}{2}−1}}{(q)_{n}(qtσ^{2})_{n}}}{∑_{n≥0} (\frac{(q − t)σ}{1 − q} )^{n} \frac{q^{\binom{n+2}{2}}}{(q)_{n}(qtσ^{2})_{n}} \frac{1 − tq^{n}σ}{(1 − q^{n}σ)(1 − q^{n+1}σ)}} ,  (3)

where σ = \frac{1 + t − 2q − \sqrt{(1 − t)(1 − t − 4q + 4q^{2})}}{2t(1 − q)}.

Proof. (2) can be rewritten as

B(s) = a(s) + b(s)B(1) + c(s)B(qs) + d(s)B(s),  (4)

where

\{ \begin{matrix}a(s) & = & \frac{ts}{1 − ts} \\ b(s) & = & \frac{q}{1 − q} (\frac{s}{1 − s} − \frac{qs}{1 − qs}) \\ c(s) & = & \frac{q}{1 − q} (\frac{qs}{1 − qs} − \frac{ts}{1 − ts}) \\ d(s) & = & \frac{q}{1 − q} (\frac{ts}{1 − ts} − \frac{s}{1 − s}) . \end{matrix}

The calculation of B(1) involves four main steps: an iteration that removes B(qs), the kernel method that removes B(s), the relation between the roots of a polynomial which leads to terms (q)_{n}(qtσ^{2})_{n}, and a division that explains the quotient of q-series.

• For n ≥ 1, the substitution s ⟶ q^{n}s in (4) leads to

B(q^{n}s) = \frac{1}{1 − d(q^{n}s)} (a(q^{n}s) + b(q^{n}s)B(1) + c(q^{n}s)B(q^{n+1}s)) ,  (5)

where 1/(1 − d(q^{n}s)) is a formal power series in t whose coefficients are polynomials in s and u. Using (5) we recursively rewrite B(q^{n}s) in (4), and after N steps we obtain

\begin{aligned}(1 − d(s)) B(s) & = & ∑_{n=0}^{N} (∏_{k=0}^{n−1} \frac{c(q^{k}s)}{1 − d(q^{k+1}s)}) (a(q^{n}s) + b(q^{n}s)B(1)) \\ & & + ( ∏_{k=0}^{N−1} \frac{c(q^{k}s)}{1 − d(q^{k+1}s)}) c(q^{N}s)B(q^{N+1}s). \end{aligned}  (6)

Since c(s)/(1 − d(qs)) is a formal power series in t that can be written

\frac{c(s)}{1 − d(qs)} = ust + st^{2}T (q, s, t),

where T (q, s, t) is a series in t whose coefficient are series in s and B(q^{N}s) is a formal power series in t, we have

(∏_{k=0}^{N} \frac{c(q^{k}s)}{1 − d(q^{k+1}s)}) B(q^{N}s) = (∏_{k=0}^{N}(q^{k+1}s + O(t^{k+2}))) O(1) = q^{\binom{N}{2}}s^{N} + O(t^{\binom{N}{2}}).

Thus, as formal power series in t, (6) converges towards

(1 − d(s)) B(s) = ∑_{n=0}^{∞} (∏_{k=0}^{n−1} \frac{c(q^{k}s)}{1 − d(q^{k+1}s)}) (a(q^{n}s) + b(q^{n}s)B(1)) ,  (7)

where B(qs) no longer appears.

• The kernel method consists of replacing s by a series σ in t and u such that the two following conditions are satisfied:

(i) 1 − d(σ) = 0 (ii) the substitution of s by σ in the right-hand side of (7) yields a well defined series

in t. When these conditions are satisfied, the left-hand side of (7) vanishes and we obtain

0 = ∑_{n=0}^{∞} (∏_{k=0}^{n−1} \frac{c(q^{k}σ)}{1 − d(q^{k+1}σ)}) (a(q^{n}σ) + b(q^{n}σ)B(1)) .  (8)

Let σ be the unique power series in t that is a root of the kernel 1 − d(s):

σ ≡ σ(t, u) = \frac{1 + t − 2q − \sqrt{(1 − t)(1 − t − 4q + 4q^{2})}}{2t(1 − q)}.

The right-hand side of (7) is a power series in t where all coefficients are polynomials in s, except for the term \frac{q}{1 − q} \frac{s}{1 − s} that appears in b(q^{0}s) and may make the substitution

s = σ impossible. But, since 1 − d(σ) = 0,

\frac{q}{1 − q} \frac{σ}{1 − σ} = \frac{q}{1 − q} \frac{tσ}{1 − tσ} − 1  (9)

where the right-hand side is a power series in t, so the left-hand side is also a power series in t. Thus the substitution s = σ leads to (8), where all terms are power series in t (with coefficients that are polynomials in u).

• The numerator of 1 − d(s) is

K(s) = (1 − q) + (2q − t − 1)s + (1 − q)ts^{2}.  (10)

Since K(s) = t(1 − q)(s − σ)(s − σ′), where σ′ is the second root of K(s), we have the equality of the two coefficients of degree 0 with respect to s:

t(1 − q)σσ′ = (1 − q),

thus

σ′ = 1/(tσ).

Then we deduce, for k ≥ 1,

1 − d(q^{k}σ) = \frac{(1 − q^{k})(1 − q^{k}tσ^{2})}{(1 − q^{k}σ)(1 − q^{k}tσ)}.

The products that appear during the iteration of the equation become

∏_{k=0}^{n−1} \frac{c(q^{k}σ)}{1 − d(q^{k+1}σ)} = (\frac{(q − t)σ}{1 − q} )^{n} \frac{q^{\binom{n+1}{2}}}{(q)_{n}(qtσ^{2})_{n}} \frac{1 − q^{n}tσ}{1 − tσ} .

• From (8) a division leads to (3). □

Some comments are in order on this result. For u = 1, the term (q − t) = (u − 1)t vanishes and (3) becomes

A(t, 1) = −\frac{t}{t\frac{1 − tσ(t, 1)}{(1 − σ(t, 1))(1 − tσ(t, 1))}} = σ(t, 1) − 1.

Thus σ(t, 1) is the generating function for (possibly empty) Dyck paths according to their size.

Moreover, we remark that the power series σ(t, u) is also the generating function for (possibly empty) Dyck paths, according to their size and their number of lower interactions, as already computed by Denise and Simion [6].

3. Dyck paths with small valleys and a q-algebraic equation

To be able to write a q-algebraic equation for the series A(t, u) we consider a subset of Dyck paths, the paths with small valleys, and another catalytic parameter. First we show in Section 3.1 that for an ad hoc valuation of these paths, their generating function is also A(t, u). Then, in Section 3.2, we decompose these paths at the first return to the axis to obtain the q-algebraic equation (14). Finally in Section 3.3 we solve this equation using an Ansatz that will be discussed further in Section 4.

3.1. A slight change of combinatorial objects

Dyck paths with small valleys are Dyck paths that avoid the factor \overline{x}\overline{x}xx. We define an ad hoc valuation of such paths: there is a weight t on each rise and a weight

V (k) = \frac{q(1 − q^{k+1}y)}{t(1 − q)}  (11)

on each valley at height k. The generating function for weighted non-empty Dyck paths with small valleys is

C(y) ≡ C(t, u; y) = ∑_{w} t^{n} ∏_{k≥0} V (k)^{v_{k}},  (12)

where w runs over these Dyck paths, n is the size of w and v_{k} the number of valleys at height k in w.

Lemma 3. The generating function A(t, u) for Dyck paths, defined by (1), and the generating function C(t, u; y) for Dyck paths with small valleys satisfy

A(t, u) = C(t, u; 1).  (13)

Proof. We group Dyck paths into sets of paths with the same sequence of peak heights. In each set S there is a single path w_{S} of minimal size and we use it as the representative of the set. This path is also the unique path of S that has small valleys. All paths in S are obtained by ”digging” independently the valleys of w_{S}, that is, rewriting recursively factors \overline{x}x of w_{S} in \overline{x}\overline{x}xx as long as the path remains above the horizontal axis.

Figure 4 gives an example: for the sequence of heights 2, 3, 1, 3, 3 the path w_{S} is drawn in black and the other paths in S are drawn in grey. There are 2 possibilities around the valley A, only one around B and C and three around D. Moreover, these choices are independent, so there are 6 Dyck paths in S.

A  B  C  E D F

Figure 4. The path with small valleys w_{S} for the sequence of peak heights 2, 3, 1, 3, 3.

In w_{S} there are as many upper interactions as valleys. Moreover, each rewriting \overline{x}x ⟶ \overline{x}\overline{x}xx increases the size and the number of upper interactions by one. For a valley D in w_{S} at height k, let E and F be respectively the vertex preceding D and following D in w_{S}, see Figure 4. The generating function for all possible subwalks between E and F obtained by digging is

ut + (ut)^{2} + … + (ut)^{k+1} = \frac{q(1 − q^{k+1})}{(1 − q)} = tV (k)_{|y=1}

where V (k)_{|y=1} denotes the valuation of valleys in (11) where y = 1. The factor t on the right-hand side corresponds to the only rise just before F that belongs to w_{S}. Thus the generating function for paths of S according to their size and their number of upper interactions corresponds to the weight of w_{S}, where a valley at height k is weighted V (k)_{|y=1} and a rise t. The summation over all the sets S, that is, over the paths with small valleys, leads to (13). □

3.2. A q-algebraic equation

The variable y that occurs in the weight of valleys is another example of a catalytic variable since it allows us to write a q-algebraic equation for paths with small valleys:

Lemma 4. The generating function for non-empty paths with small valleys satisfies

C(y) = t + t (1 + q \frac{1 − qy}{1 − q} ) C(qy) + q \frac{1 − qy}{1 − q} C(y) + (q \frac{1 − qy}{1 − q} )^{2} C(qy)C(y). (14)

Proof. We split a path with small valleys at the first return to the axis, called A in Figure 5. There are five cases due to the avoidance of the factor \overline{x}\overline{x}xx around the vertex A.

A +  C(qy) A +  C(qy) A  +  A C(y) +  C(qy) A BC(y)

Figure 5. Decomposition of paths with small valleys

A non-empty Dyck path with small valleys w can be written as w = xu\overline{x}v where u and v are two Dyck paths with small valleys, possibly empty. We distinguish five cases according to the emptiness of u and v:

u and v are empty: The weight of the path x\overline{x} is t.

only v is empty: There is exactly one more rise in xu\overline{x} than u. Moreover all the valleys are one unit higher, thus a valley is weighted V (k + 1) in xu\overline{x} instead of V (k) in u. The relation between the two weights is taken into account by the substitution y ⟶ qy. This explains why we use the catalytic variable y in the weight of paths with small valleys. Finally the generating function for paths in this case is tC(qy).

only u is empty: There is exactly one more rise and one more valley at height 0

in x\overline{x}v than in v, thus the generating function in this case is tV (0)C(y). neither u nor v are empty: This case will be split into two cases because xx can not be a prefix of v without creating a factor \overline{x}\overline{x}xx in the path xu\overline{x}v. To avoid this case, v begins with x\overline{x}, so we factor the path in xu\overline{x}x\overline{x}v′ and we consider the emptiness of v′. v′ is empty: There are two more rises and one more valley at height 0 in xu\overline{x}x\overline{x} than in u. Moreover the valleys in u are one unit higher in xu\overline{x}x\overline{x}. Thus the generating function for paths in this case is t^{2}V (0)C(qy).

v′ is non-empty: There are two more rises and two more valleys at height 0 in xu\overline{x}x\overline{x}v′ than in u and v. Moreover the valleys in the factor u of w are one unit higher than in u. The generating function for paths of this case is (tV (0))^{2} C(y)C(qy).

These five cases lead to (14). □

3.3. Solution of the q-algebraic equation

The solution of the q-algebraic equation (14) begins with a change of unknown functions: we look for solutions of the form

C(y) = \frac{J(qy)}{αJ(y) + β(y)J(qy)},  (15)

where α is independent of y, β(y) a polynomial in y, and J(y) a formal power series in y such that J(0) = 1. A series H(y) = ∑_{n≥0} h_{n}y^{n} is a basic hypergeometric series if there is a rational function F (t, q, X) such that h_{n+1}/h_{n} = F (t, q, q^{n}) for all n ∈ ℕ.

Proposition 5. The unique formal power series in t that satisfies the q-algebraic equation (14) is

C(y) = \frac{tσ ∑_{n≥0} (\frac{(q − t)σ}{1 − q} )^{n} \frac{q^{\binom{n+2}{2}−1}}{(q)_{n}(qtσ^{2})_{n}} y^{n}}{∑_{n≥0} (\frac{(q − t)σ}{1 − q} )^{n} \frac{q^{\binom{n+1}{2}}(q^{n}tσ − q − q^{2n}t^{2}σ^{2})}{(q)_{n}(qtσ^{2})_{n}(t − q)}y^{n}} ,  (16)

where again q ≡ ut and σ is defined as in Proposition 2.

Proof. We consider (14) with C(y) replaced by its expression (15). This gives a single rational function R in y, J(y), J(qy) and J(q^{2}y). The numerator N of R is a linear com-

bination of J(y)J(qy), J(qy)^{2}, J(q^{2}y)J(qy) and J(q^{2}y)J(y). We choose β(y) = −\frac{1 − qy}{1 − q}

to remove the term J(q^{2}y)J(y), thus we can factor J(qy) in N. The other factor of N vanishes if and only if the following q-linear equation holds:

tα^{2}J(y) − (1 + \frac{(t − q)(1 − qy)}{1 − q}) αJ(qy) + J(q^{2}y) = 0.  (17)

The evaluation at y = 0 of (17) implies that α is one of the two roots of a polynomial that is the kernel (10) in the proof of Proposition 2. We define α = 1/(tσ). We will explain later why we choose this root rather than σ. The change of unknown functions defined by this analysis is

C(y) = \frac{tσJ(qy)}{J(y) − \frac{1 − qy}{1 − q} tσJ(qy)},  (18)

and leads to the q-linear equation (17) where α = 1/(tσ). Since (17) is of degree 1 in y and by definition J(y) = 1 + ∑_{n≥1} j_{n}y^{n}, the extraction of the coefficient of y^{n+1} in (17) gives a relation between j_{n} and j_{n+1}, namely

j_{n+1} = \frac{(q − t)σq^{n+1}}{(1 − q)(1 − q^{n+1})(1 − q^{n+1}tσ^{2})} · j_{n},

where we have again used the relation (10) between the roots of the kernel to rewrite the denominator. Thus J(y) is the following basic hypergeometric series

J(y) = ∑_{n≥0} (\frac{(q − t)σ}{1 − q} )^{n} \frac{q^{\binom{n+1}{2}}}{(q)_{n}(qtσ^{2})_{n}} y^{n}.

We plug this expression in (18) and we obtain (16). □

4. Comments

The two approaches used in Section 2 and Section 3 to solve the same enumerative problem share some common aspects that we want to underline in this section. First we will show in Section 4.1 that the additional catalytic parameter, counted by the variable y and required to write the q-algebraic equation, can also be taken into account by a solvable slice equation. Then we discuss in Section 4.2 the different kinds of “homographic” change of unknown functions that turn a q-algebraic equation into a q-linear one and we compare their efficiency in our example. The most efficient Ansatz for our example was guessed after considering the shape of the generating function (20) computed in Section 4.1.

4.1. A slice equation for paths with small valleys

To add the information on the length of the last descent of a path with small valleys we define the generating function

D(s) ≡ D(t, q, y; s) = ∑_{w} t^{n}s^{l} ∏_{k≥0} V (k)^{v_{k}},

where w runs over the non-empty Dyck paths with small valleys, n the size of w, l the height of the last peak in w and v_{k} the number of valleys at height k in w. (V (k) is defined by (11)) The same kind of slice functional equation as (2) holds for D(s). Moreover the additional variable y does not significantly modify the solution, which is very similar to the one proposed in Proposition 2.

Proposition 6. The generating function for Dyck paths with small valleys counted according to the size, the weight V (k) of valleys and the length of the last descent satisfies

\begin{aligned}D(s) & = & \frac{ts}{1 − ts} + \frac{ts}{1 − ts} \frac{q}{1 − q} (D(s) − yD(qs)) \\ & & +\frac{q}{1 − q} (\frac{s}{1 − s} (D(1) − D(s)) − y \frac{qs}{1 − qs} (D(1) − D(qs))) \end{aligned}  (19)

and the elimination of D(qs) and D(s) leads to the solution

D(1) = −\frac{∑_{n≥0} (\frac{(q − t)σ}{1 − q} )^{n} \frac{q^{\binom{n+1}{2}}}{(q)_{n}(qtσ^{2})_{n}} \frac{tq^{n}σ}{1 − tσ} y^{n}}{∑_{n≥0} (\frac{(q − t)σ}{1 − q} )^{n} \frac{q^{\binom{n+1}{2}}}{(q)_{n}(qtσ^{2})_{n}} \frac{(q^{n}tσ − q − (q^{n}tσ)^{2})}{(q − t)(1 − tσ)}y^{n}} = C(y).  (20)

Proof. Writing down the equation is similar to Lemma 1. We concentrate on the variations. We split Dyck paths with small valleys into the set T_{1} of paths with exactly one peak, the set T_{2} of paths where the last peak is higher than the previous one and the set T_{3} of paths where the last peak is not higher than the previous one. Let T_{i}(s) be the generating function defined by considering the paths of T_{i}. The former division leads to

D(s) = T_{1}(s) + T_{2}(s) + T_{3}(s).

Figure 6 gives examples of each set built by inserting a factor x^{k}\overline{x}^{k} at the end of a possibly empty Dyck path with small valleys. The avoidance of the factor xx\overline{x}\overline{x} implies that the vertex B is necessarily exactly one unit below the vertex A and that the vertex E is exactly one unit above the vertex F.

+  +  D F E A B  C T^{1}  T^{2}  T^{3}

Figure 6. The partition of Dyck paths with small valleys

In terms of generating functions, the case of T_{1} is equal to S_{1}:

T_{1}(s) = \frac{ts}{1 − ts}.

When building a path of T_{2}, it remains only to choose the difference j between the heights of A and C thus

T_{2}(s) = ∑_{l≥1} ∑_{w∈E_{l}} (t^{n}s^{l}V (l − 1) ∑_{j≥1}(ts)^{j}) = \frac{ts}{1 − ts} ∑_{l≥1} ∑_{E_{l}} t^{n}s^{l}V (l − 1)

where E_{l} is the set of Dyck paths with small valleys whose last peak is at height l.

The height i of the vertex E is the unique parameter that defines the addition of x\overline{x} creating a path of T_{3}, thus

T_{3}(s) = ∑_{l≥1} ∑_{w∈E_{l}} (t^{n} ∑_{i=1}^{l} ts^{i}V (i − 1)) .

Intuitively, the valuation of a small valley at height k is linked to the choice of the height of the valleys B or F, between 0 and k. This choice has disappeared in the building of paths with small valleys. In fact with this valuation we only anticipate the summation implied by this choice (and add the catalytic variable y). Using V (k) = q(1 − q^{k+1}y)/t/(1 − q), the two previous summations become

T_{2}(s) = \frac{ts}{1 − ts} \frac{q}{1 − q} (D(s) − yD(qs))

and

T_{3}(s) = \frac{q}{1 − q} (\frac{s}{1 − s} (D(1) − D(s)) − y \frac{qs}{1 − qs} (D(1) − D(qs))) .

The functional equation (19) can be written

D(s) = a_{y}(s) + b_{y}(s)D(1) + c_{y}(s)D(qs) + d_{y}(s)D(s)  (21)

where

\{ \begin{matrix}a_{y}(s) & = & \frac{ts}{1 − ts} & = & a(s) \\ b_{y}(s) & = & \frac{q}{1 − q} (\frac{s}{1 − s} − y \frac{qs}{1 − qs}) \\ c_{y}(s) & = & \frac{q}{1 − q} (y \frac{qs}{1 − qs} − y \frac{ts}{1 − ts}) & = & yc(s) \\ d_{y}(s) & = & \frac{q}{1 − q} (\frac{ts}{1 − ts} − \frac{s}{1 − s}) & = & d(s). \end{matrix}

The coefficients a(s), c(s) and d(s) already appeared in the proof of Proposition 2

To solve this equation which is similar to (2) we use the same method as in Proposition 2. Since

\frac{c_{y}(q^{k}s)}{1 − d_{y}(q^{k+1}s)} = y \frac{c(q^{k}s)}{1 − d(q^{k+1}s)},

there is an additional factor y^{n} in the terms of the summation due to the iteration. Moreover 1 − d_{y}(s) = 1 − d(s), thus the kernel method again leads to the substitution s = σ independent of y. We have

D(1) = −\frac{∑_{n≥0} (\frac{(q − t)σ}{1 − q} )^{n} \frac{q^{\binom{n+1}{2}}}{(q)_{n}(qtσ^{2})_{n}} \frac{tq^{n}σ}{1 − tσ} y^{n}}{∑_{n≥0} (\frac{(q − t)σ}{1 − q} )^{n} \frac{q^{\binom{n+1}{2}}}{(q)_{n}(qtσ^{2})_{n}} \frac{1 − q^{n}tσ}{1 − tσ} \frac{q}{1 − q} (\frac{q^{n}σ}{1 − q^{n}σ} − y \frac{q^{n+1}σ}{1 − q^{n+1}σ} ) y^{n}}

= \frac{P (y)}{Q(y)}.

To expand the denominator Q(y) according to powers of y we extract the coefficient of y^{n}. For n ≥ 1 we obtain directly the coefficient that we observe in (20) but for n = 0 we have

[y^{0}]Q(y) = \frac{q}{1 − q} \frac{σ}{1 − σ} = \frac{tσ − q − t^{2}σ^{2}}{(q − t)(1 − tσ)}

where the second equality uses the fact that σ satisfies (10). Then P (y) and Q(y) are two basic hypergeometric series. □

4.2. On solution of certain q-quadratic equations

The solution of the q-algebraic equation (14) requires two main steps: a Riccattilike Ansatz and the solution of the resulting q-linear equation. We discuss here the compatibility of these two methods in the general case of q-quadratic equations defined by

f_{1}(y)C(qy)C(y) + f_{2}(y)C(qy) + f_{3}(y)C(y) + f_{4}(y) = 0  (22)

where f_{i}(y) are polynomials in y. All the following remarks are motivated by the question which is open to the best of our knowledge: is it possible to check if there exists a solution of (22) that could be written

C(y) = \frac{α(y)H(qy) + β(y)H(y)}{γ(y)H(qy) + δ(y)H(y)}  (23)

where α(y), β(y), γ(y) and δ(y) are polynomials in y and H(y) is a basic hypergeometric series? In the case of a positive answer can we compute this solution?

This question, maybe too ambitious, asks for an extension, using the Riccatti-like Ansatz, of the algorithm proposed by Abramov, Paule and Petkovšek in [1] to find basic hypergeometric series solution of a q-linear equation. We use our enumeration of Dyck paths according to their size and their number of upper interactions to present some basic facts around this question.

4.2.1. On solution of q-linear equations. The aim of the Riccatti-like Ansatz is to turn the equation (22) into a solvable q-linear equation. To understand this goal, we discuss what we mean by the adjective “solvable” in this context.

A series H(y) = ∑_{n≥0} h_{n}y^{n} satisfies a q-linear equation if

∑_{k=0}^{N} c_{k}(y)H(q^{k}y) = 0.  (24)

where (c_{k}(y))_{k=1...N} are polynomials in y with rational functions of t and q as coefficients and without loss of generality y does not divide all the c_{k}(y). The extraction of coefficients of y^{K} in the equation (24) leads, for K large enough, to a linear recurrence (L) satisfied by the coefficients (h_{n})_{n≥0} with coefficients which are rational functions of t, q and q^{K}. Let D be the maximal degree with respect to y of the polynomials c_{k}(y). The recurrence (L) corresponding to the extraction of the coefficient y^{K} involves at least h_{K} and h_{K−D} and in general some terms h_{K+i}, where 1 ≤ i < D. The value of D appears as a good approximation of the difficulty of a q-linear equation.

If D = 1, we recognise a case that corresponds to the q-equation (17) that appears in our first solution of the q-algebraic equation (14). The same argument holds in this more general case, leading to a solution that is a sum of a polynomial and a basic hypergeometric series.

If D > 1, there is no systematic way to compute solutions of the q-linear equation without any assumption on them. If one looks for basic hypergeometric (and polynomial) solutions, Abramov, Paule and Petkovšek proposed in [1] an algorithm to find them or else to prove that there is no such solution.

Example 7. To solve the q-quadratic equation (14) we try the Riccatti-like Ansatz used successfully by Brak and Prellberg for their problems in [5]:

C(y) = \frac{(1 − q)^{2}tσ}{q^{2}} \frac{H(qy)}{H(y)} − \frac{t(1 − q)(1 − q^{2}y)}{q^{2}(1 − qy)^{2}}.  (25)

This leads to a q-linear equation where D = 6 and that does not have a basic hypergeometric series (or a polynomial) as solution.

4.2.2. Riccatti-like Ansätze. The two Riccatti-like Ansätze (18) and (25) linearise the same q-quadratic equation (14) but they lead to two different kinds of q-linear equations with regard to their solutions. This fact motivates the discussion about the variations of the Ansätze that we found in the literature [5], [8]. All these variations correspond to a particular “homographic” change of unknown functions that could be written, with gain of generality as (23) without assuming that H(y) is a basic hypergeometric series. With this change of unknown functions, (22) becomes the vanishing of a rational fraction then of its numerator. This numerator could be factorised in H(qy)L(y) where L(y) is a q-linear equation involving H(q^{2}y), H(qy) and H(y) provided the following linearision condition, corresponding to the coefficient of H(y)H(q^{2}y) of the numerator, is satisfied

f_{1}(y)α(qy)β(y) + f_{2}(y)α(qy)δ(y) + f_{3}(y)β(y)γ(qy) + f_{4}(y)γ(qy)δ(y) = 0.  (26)

The aim of the change of unknown is to obtain a solvable q-linear equation L(y) that depends on the choice of α(y), β(y), γ(y) and δ(y).

A possible way to prolong the general study of these Ansätze is to deduce from the linearision condition (26) an expression of δ(y) in function of α(y), β(y) and γ(y). We obtain a q-linear equation where α(y), β(y) and γ(y) are parameters. Applying the algorithm of Abramov, Paule and Petkovšek to this equation may lead to additional relations between these parameters to guarantee the existence of a basic hypergeometric solution or to prove its nonexistence.

Here, we only discuss assumptions made in the literature on the values α(y), β(y), γ(y) and δ(y) with which these polynomials are almost unambiguously defined by the coefficients of the given q-quadratic equation (22), and that sometimes lead to a q-linear equation with basic hypergeometric solutions.

• In [5] Brak and Prellberg suggested assuming that γ(y) = 0, and α(y)/δ(y) is independent of y. The values of β(y) and δ(y) are chosen to satisfy the linearision condition (26) and α(y)/δ(y) is fixed by the evaluation at y = 0 of the q-linear equation. For our equation (14) for the enumeration of Dyck paths, it has already been pointed out in Example 7 that the resulting q-linear equation does not have a basic hypergeometric series as solution.

• In [8] Janse Van Rensburg used a change of unknown functions where again γ(y) = 0, but now α(y) is independent of y. In our example of (14) this assumption leads to the third Ansatz

C(y) = \frac{(1 − q)^{2}tσ}{q^{2}(1 − qy)^{2}} \frac{H(qy)}{H(y)} − \frac{t(1 − q)(1 − q^{2}y)}{q^{2}(1 − qy)^{2}}.  (27)

In the resulting q-linear equation, the maximal degree D of the coefficients is 3 and we were able to find a basic hypergeometric solution using the algorithm of Abramov, Paule and Petkovšek.

• With a bit of reverse-engineering on the solution derived in Section 4.1, we discovered that the assumption α(y) = 1, β(y) = 0 and δ(y) independent of y leads to the most efficient Riccatti-like Ansatz (18) for our example. (The maximal degree D of the coefficients is 1 in the q-linear equation (17) )

Acknowledgements. I thank Mireille Bousquet-Mélou and Volker Strehl for valuable comments on this work. I am grateful to Mike Robson who also helped improving the English.

References

[1] S. A. Abramov, P. Paule, and M. Petkovšek. q-Hypergeometric solutions of q-difference equations. Discrete Math., 180(1-3):3–22, 1998.

[2] M. Bousquet-Mélou and M. Petkovšek. Linear recurrences with constant coefficients: the multivariate case. Discrete Math., 225:51–75, 2000.

[3] M. Bousquet-Mélou and A. Rechnitzer. The site-perimeter of bargraphs. Adv. in Appl. Math., 31(1):86–112, 2003.

[4] M. Bousquet-Mélou and X. G. Viennot. Empilements de segments et q-énumération de polyominos convexes dirigés. J. Combin. Theory Ser. A, 60(2):196–224, 1992.

[5] R. Brak and T. Prellberg. Critical exponents from nonlinear functional equations for partially directed cluster models. J. of Stat. Phys., 78(3-4):701–730, 1995.

[6] A. Denise and R. Simion. Two combinatorial statistics on Dyck paths. Discrete Math., 137(1-3):155– 176, 1995.

[7] D.P. Foster and J. Yeomans. Competition between self-attraction and adsorption in directed selfavoiding polymers. Physica A, 177:443–452, 1991.

[8] E. J. Janse van Rensburg. Interacting columns: generating functions and scaling exponents. J. Phys. A, 33(42):7541–7554, 2000.

[9] J. A. Klarner. Cell growth problems. Can. J. Math., 19(4):851–863, 1967.

[10] Y. Le Borgne. Variation combinatoires sur des classes d’objets comptées par la suite de Catalan. PhD thesis, Université Bordeaux I, December 2004. (French).

[11] Y. Le Borgne. Counting upper interactions in Dyck paths. In Proceedings FPSAC05, June 2005.

[12] Delest M.-P. and Fédou J.-M. Enumeration of skew Ferrers diagrams. Discrete Math, 112:65–79, 1993.

[13] R. Rajesh, D. Dhar, D. Giri, S. Kumar, and Y. Singh. Adsorption and collapse transitions in a linear polymer chain near an attractive wall. Physical Review E, 65:056124, 2002.

[14] G. X. Viennot. Heaps of pieces. I. Basic definitions and combinatorial lemmas. In Combinatoire énumérative, volume 1234 of Lecture Notes in Math., pages 321–350. Springer, Berlin, 1986.

[15] D. Zeilberger. The umbral transfer-matrix method. I. Foundations. J. Combin. Theory Ser. A, 91(1-2):451–463, 2000.

LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France

E-mail address: borgne@labri.fr