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

ON PARTITIONS AVOIDING 3-CROSSINGS

MIREILLE BOUSQUET-MÉLOU AND GUOCE XIN

To Xavier Viennot, on the occasion of his 60th birthday

Abstract. A partition on [n] has a crossing if there exists i_{1} < i_{2} < j_{1} < j_{2} such that i_{1} and j_{1} are in the same block, i_{2} and j_{2} are in the same block, but i_{1} and i_{2} are not in the same block. Recently, Chen et al. refined this classical notion by introducing k-crossings, for any integer k. In this new terminology, a classical crossing is a 2-crossing. The number of partitions of [n] avoiding 2-crossings is well-known to be the nth Catalan number C_{n} = \binom{2n}{n}/(n + 1). This raises the question of counting k-noncrossing partitions for k ≥ 3. We prove that the sequence counting 3-noncrossing partitions is P-recursive, that is, satisfies a linear recurrence relation with polynomial coefficients. We give explicitly such a recursion. However, we conjecture that k-noncrossing partitions are not P-recursive, for k ≥ 4. We obtain similar results for partitions avoiding enhanced 3-crossings.

1. Introduction

A partition of [n] := {1, 2, …, n} is a collection of nonempty and mutually disjoint subsets of [n], called blocks, whose union is [n]. The number of partitions of [n] is the Bell number B_{n}. A well-known refinement of B_{n} is given by the Stirling number (of the second kind) S(n, k). It counts partitions of [n] having exactly k blocks.

Recently another refinement of the Bell numbers by crossings and nestings has attracted some interest [8, 15, 13]. This refinement is based on the standard representation of a partition P of [n] by a graph, whose vertex set [n] is identified with the points i ≡ (i, 0) on the plane, for 1 ≤ i ≤ n, and whose edge set consists of arcs connecting the elements that occur consecutively in the same block (when each block is totally ordered). For example, the standard representation of 1478 − 236 − 5 is given by the following graph.

Then crossings and nestings have a natural definition. A k-crossing of P is a collection of k edges (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{k}, j_{k}) such that i_{1} < i_{2} < ⋯ < i_{k} < j_{1} < j_{2} < ⋯ < j_{k}. This means a subgraph of P as drawn as follows.

Key words and phrases. Partitions, Crossings, D-finite series.

i^{1} i^{2}  i^{k}  j^{1} j^{2}  j^{k}

A different notion of k-crossing is obtained by representing each block by a complete graph [14, p. 85]. A k-nesting of P is a collection of k edges (i_{1}, j_{1}), (i_{2}, j_{2}), …, (i_{k}, j_{k}) such that i_{1} < i_{2} < ⋯ < i_{k} < j_{k} < j_{k−1} < ⋯ < j_{1}, as represented below.

i^{1} i^{2}  i^{k}  j^{k}  j^{2} j^{1}

A partition is k-noncrossing if it has no k-crossings, and k-nonnesting if it has no k-nestings.

A variation of k-crossings (nestings), called enhanced k-crossings (nestings), was also studied in [8]. One first adds a loop to every isolated point in the standard representation of partitions. Then by allowing i_{k} = j_{1} in a k-crossing, we get an enhanced k-crossing; in particular, a partition avoiding enhanced 2crossings has parts of size 1 and 2 only. Similarly, by allowing i_{k} = j_{k} in the definition of a k-nesting, we get an enhanced k-nesting.

Chen et al. gave in [8] a bijection between partitions of [n] and certain “vacillating” tableaux of length 2n. Through this bijection, a partition is knoncrossing if and only if the corresponding tableau has height less than k, and k-nonnesting if the tableau has width less than k. A simple symmetry on tableaux then entails that k-noncrossing partitions of [n] are equinumerous with k-nonnesting partitions of [n], for all values of k and n. A second bijection relates partitions to certain “hesitating” tableaux, in such a way the size of the largest enhanced crossing (nesting) becomes the height (width) of the tableau. This implies that partitions of [n] avoiding enhanced k-crossings are equinumerous with partitions of [n] avoiding enhanced k-nestings.

The number C_{2}(n) of 2-noncrossing partitions of [n] (usually called noncrossing partitions [16, 22]) is well-known to be the Catalan number C_{n} = \frac{1}{n+1} \binom{2n}{n}. For k > 2, the number of k-noncrossing partitions of [n] is not known, to the extent of our knowledge. However, for any k, the number of k-noncrossing matchings of [n] (that is, partitions in which all blocks have size 2) is known to form a P-recursive sequence, that is, to satisfy a linear recurrence relation with polynomial coefficients [11, 8]. In this paper, we enumerate 3-noncrossing partitions of [n] (equivalently, 3-nonnesting partitions of [n]). We obtain for C_{3}(n) a (not so simple) closed form expression (Proposition 7) and a linear recurrence relation with polynomial coefficients.

Proposition 1. The number C_{3}(n) of 3-noncrossing partitions is given by C_{3} (0) = C_{3} (1) = 1, and for n ≥ 0,

9n (n + 3) C_{3} (n) − 2 (5n^{2} + 32n + 42) C_{3} (n + 1) + (n + 7) (n + 6) C_{3} (n + 2) = 0. (1)

Equivalently, the associated generating function C(t) = ∑_{n≥0} C_{3}(n)t^{n} satisfies

t^{2}(1−9t)(1−t)\frac{d^{2}}{dt^{2}} C(t)+2t (5 − 27t + 18t^{2}) \frac{d}{dt}C(t)+10 (2 − 3t) C(t) = 20. (2)

Finally, as n tends to infinity,

C_{3}(n) ∼ \frac{3^{9} · 5}{2^{5}} \frac{\sqrt{3}}{π} \frac{9^{n}}{n^{7}} .

The first few values of the sequence C_{3}(n), for n ≥ 0, are

1, 1, 2, 5, 15, 52, 202, 859, 3930, 19095, 97566, ….

A standard study [12, 24] of the above differential equation, which can be done automatically using the Maple package DEtools, suggests that C_{3}(n) ∼ κ 9^{n}/n^{7} for some positive constant κ. However, one needs the explicit expression of C_{3}(n) given in Section 2.5 to prove this statement and find the value of κ. The above asymptotic behaviour is confirmed experimentally by the computation of the first values of C_{3}(n) (a few thousand values can be computed rapidly using the package Gfun of Maple [21]). For instance, when n = 50000, then n^{7}C_{3}(n)/9^{n} ≃ 1694.9, while κ ≃ 1695.6.

As discussed in the last section of the paper, the above result might remain isolated, as there is no (numerical) evidence that the generating function of 4-noncrossing partitions should be P-recursive.

We obtain a similar result for partitions avoiding enhanced 3-crossings (or enhanced 3-nestings). The number of partitions of [n] avoiding enhanced 2crossings is easily seen to be the nth Motzkin number [23, Exercise 6.38].

Proposition 2. The number E_{3}(n) of partitions of [n] having no enhanced 3-noncrossing is given by E_{3} (0) = E_{3} (1) = 1, and for n ≥ 0,

8 (n + 3) (n + 1) E_{3} (n) + (7n^{2} + 53n + 88) E_{3} (n + 1) − (n + 8) (n + 7) E_{3} (n + 2) = 0.

Equivalently, the associated generating function E(t) = ∑_{n≥0} E_{3}(n)t^{n} satisfies

t^{2} (1 + t) (1 − 8t) \frac{d^{2}}{dt^{2}} E(t) + 2t (6 − 23t − 20t^{2}) \frac{d}{dt}E(t)

+ 6 (5 − 7t − 4t^{2}) E(t) = 30.

Finally, as n tends to infinity,

E_{3}(n) ∼ \frac{2^{16} · 5}{3^{3}} \frac{\sqrt{3}}{π} \frac{8^{n}}{n^{7}} .

The first few values of the sequence E_{3}(n), for n ≥ 0, are

1, 1, 2, 5, 15, 51, 191, 772, 3320, 15032, 71084, ….

Observe that C_{3}(5) and E_{3}(5) differ by 1: this difference comes from the partition 135−24 which has an enhanced 3-crossing but no 3-crossing (equivalently, from the partition 15−24−3 which has an enhanced 3-nesting but no 3-nesting). Again, the study of the differential equation suggests that E_{3}(n) ∼ κ\frac{8^{n}}{n^{7}} , for some positive constant κ, but we need the explicit expression (33) of E_{3}(n) to prove this statement and find the value of κ. Numerically, we have found that for n = 50000, n^{7}E_{3}(n)/8^{n} ≃ 6687.3, while κ ≃ 6691.1.

The starting point of our proof of Proposition 1 is the above mentioned bijection between partitions avoiding k + 1-crossings and vacillating tableaux of height at most k. As described in [8], these tableaux can be easily encoded by certain k-dimensional lattice walks. Let D be a subset of ℤ^{k}. A D-vacillating lattice walk of length n is a sequence of lattice points p_{0}, p_{1}, …, p_{n} in D such that for all i,

(i) p_{2i+1} = p_{2i} or p_{2i+1} = p_{2i} − e_{j} for some coordinate vector e_{j} = (0, …, 0, 1, 0, …, 0),

(ii) p_{2i} = p_{2i−1} or p_{2i} = p_{2i−1} + e_{j} for some e_{j}.

We will be interested in two different domains D of ℤ^{k}: the domain Q_{k} = ℕ^{k} of points with non-negative integer coordinates and the Weyl chamber of type C_{k} (with a slight change of coordinates) W_{k} = { (a_{1}, a_{2}, …, a_{k}) ∈ ℤ^{k} : a_{1} > a_{2} > ⋯ > a_{k} ≥ 0 }. Vacillating walks in W_{k} are related to k + 1-noncrossing partitions as follows.

Theorem 3 (Chen et al. [8]). Let C_{k}(n) denote the number of k-noncrossing partitions of [n]. Then C_{k+1}(n) equals the number of W_{k}-vacillating lattice walks of length 2n starting and ending at (k − 1, k − 2, …, 0).

The proof of Proposition 1 goes as follows: using the reflection principle, we first reduce the enumeration of vacillating walks in the Weyl chamber W_{k} to that of vacillating walks in the non-negative domain Q_{k}. This reduction is valid for any k. We then focus on the case k = 2. We write a functional equation satisfied by a 3-variable series that counts vacillating walks in Q_{2}. This equation is based on a simple recursive construction of the walks. It is solved using a 2-dimensional version of the so-called kernel method. This gives the generating function C(t) = ∑ C_{3}(n)t^{n} as the constant term in a certain algebraic series. We then use the Lagrange inversion formula to find an explicit expression of C_{3}(n), and apply the creative telescoping of [20] to obtain the recurrence relation. We finally derive from the expression of C_{3}(n) the asymptotic behaviour of these numbers. The proof of Proposition 2, given in Section 3, is similar.

2. Partitions with no 3-crossing

2.1. The reflection principle

Let δ = (k − 1, k − 2, …, 0) and let λ and μ be two lattice points in W_{k}. Denote by w_{k}(λ, μ, n) (respectively q_{k}(λ, μ, n)) the number of W_{k}-vacillating (respectively Q_{k}-vacillating) lattice walks of length n starting at λ and ending at μ. Thus Theorem 3 states that C_{k+1}(n) equals w_{k}(δ, δ, 2n). The reflection principle, in the vein of [10, 25], gives the following:

Proposition 4. For any starting and ending points λ and μ in W_{k}, the number of W_{k}-vacillating walks going from λ to μ can be expressed in terms of the number of Q_{k}-vacillating walks as follows:

w_{k}(λ, μ, n) = ∑_{π∈𝔖_{k}}(−1)^{π}q_{k}(λ, π(μ), n),  (3)

where (−1)^{π} is the sign of π and π(μ_{1}, μ_{2}, …, μ_{k}) = (μ_{π(1)}, μ_{π(2)}, …, μ_{π(k)}).

Proof. Consider the set of hyperplanes H = { x_{i} = x_{j} : 1 ≤ i < j ≤ k }. The reflection of the point (a_{1}, …, a_{k}) with respect to the hyperplane x_{i} = x_{j} is simply obtained by exchanging the coordinates a_{i} and a_{j}. In particular, the set of (positive) steps taken by vacillating walks, being {e_{1}, …, e_{k}}, is invariant under such reflections. The same holds for the negative steps, and of course for the “stay” step, 0. This implies that reflecting a Q_{k}-vacillating walk with respect to x_{i} = x_{j} gives another Q_{k}-vacillating walk. Note that this is not true when reflecting with respect to x_{i} = 0 (since e_{i} is transformed into −e_{i}).

Define a total ordering on H. Take a Q_{k}-vacillating walk w of length n going from λ to π(μ), and assume it touches at least one hyperplane in H. Let m be the first time it touches a hyperplane. Let x_{i} = x_{j} be the smallest hyperplane it touches at time m. Reflect all steps of w after time m across x_{i} = x_{j}; the resulting walk w′ is a Q_{k}-vacillating walk going from λ to (i, j)(π(μ)), where (i, j) denotes the transposition that exchanges i and j. Moreover, w′ also (first) touches H at time m, and the smallest hyperplane it touches at this time is x_{i} = x_{j}.

The above transformation is a sign-reversing involution on the set of Q_{k}- vacillating paths that go from λ to π(μ), for some permutation π, and hit one of the hyperplanes of H. In the right-hand side of (3), the contributions of these walks cancel out. One is left with the walks that stay within the Weyl chamber, and this happens only when π is the identity. The proposition follows.

This proposition, combined with Theorem 3, gives the number of (k + 1)-noncrossing partitions of n as a linear combination of the numbers q_{k}(δ, π(δ), 2n). Hence, in order to count (k + 1)-noncrossing partitions, it suffices to find a formula for q_{k}(δ, μ, 2n), for certain ending points μ. This is what we do below for k = 2.

2.2. A functional equation

Let us specialize Theorem 3 and Proposition 4 to k = 2. This gives

C_{3}(n) = w_{2}((1, 0), (1, 0), 2n)
= q_{2}((1, 0), (1, 0), 2n) − q_{2}((1, 0), (0, 1), 2n).  (4)

From now on, a lattice walk always means a Q_{2}-vacillating lattice walk starting at (1, 0), unless specified otherwise.

Let a_{i,j}(n) := q_{2}((1, 0), (i, j), n) be the number of lattice walks of length n ending at (i, j). Let

F_{e}(x, y; t) = ∑_{i,j,n≥0} a_{i,j}(2n)x^{i}y^{j}t^{2n}

and

F_{o}(x, y; t) = ∑_{i,j,n≥0} a_{i,j}(2n + 1)x^{i}y^{j}t^{2n+1}

be respectively the generating functions of lattice walks of even and odd length. These series are power series in t with coefficients in ℚ[x, y]. We will often work in a slightly larger ring, namely the ring ℚ[x, 1/x, y, 1/y][[t]] of power series in t whose coefficients are Laurent polynomials in x and y.

Now we find functional equations for F_{e}(x, y; t) and F_{o}(x, y; t). By appending to an even length walk a west step (−1, 0), or a south step (0, −1), or a stay step (0, 0), we obtain either an odd length walk (in Q_{2}), or an even length walk ending on the x-axis followed by a south step, or an even length walk ending on the y-axis followed by a west step. This correspondence is easily seen to be a bijection, and gives the following functional equation:

F_{e}(x, y; t)(1 + x̄ + ȳ)t = F_{o}(x, y; t) + ȳtH_{e}(x; t) + x̄tV_{e}(y; t),  (5)

where x̄ = 1/x, ȳ = 1/y, and H_{e}(x; t) (respectively V_{e}(y; t)) is the generating function of even lattice walks ending on the x-axis (respectively on the y-axis).

Similarly, by adding to an odd length walk an east step (1, 0), or a north step (0, 1), or a stay step, we obtain an even length walk of positive length. The above correspondence is a bijection and gives another functional equation:

F_{o}(x, y; t)(1 + x + y)t = F_{e}(x, y; t) − x.  (6)

Solving equations (5) and (6) for F_{e}(x, y; t) and F_{o}(x, y; t) gives

F_{e}(x, y; t) = \frac{x − t^{2}ȳ(1 + x + y)H_{e}(x; t) − t^{2}x̄(1 + x + y)V_{e}(y; t)}{1 − t^{2}(1 + x + y)(1 + x̄ + ȳ)},
F_{o}(x, y; t) = t \frac{x(1 + x̄ + ȳ) − x̄V_{e}(y; t) − ȳH_{e}(x; t)}{1 − t^{2}(1 + x + y)(1 + x̄ + ȳ)}.

Since we are mostly interested in even length walks ending at (1, 0) and at (0, 1), it suffices to determine the series H_{e}(x; t) and V_{e}(y; t), and hence to solve one of the above two functional equations. We choose the one for F_{o}(x, y; t), which is simpler.

Proposition 5. The generating function F_{o}(x, y; t) of Q_{2}-vacillating lattice walks of odd length starting from (1, 0) is related to the generating functions of even lattice walks of the same type ending on the x- or y-axis by

K(x, y; t)F (x, y; t) = xy + x^{2}y + x^{2} − xH(x; t) − yV (y; t),  (7)

where F_{o}(x, y; t) = tF (x, y; t^{2}), V (y; t) = V_{e}(y; t^{2}), H(x; t) = H_{e}(x; t^{2}), and K(x, y; t) is the kernel of the equation:

K(x, y; t) = xy − t(1 + x + y)(x + y + xy).  (8)

From now on, we will very often omit the variable t in our notation. For instance, we will write H(x) instead of H(x; t). Observe that (7) defines F (x, y) uniquely as a series in t with coefficients in ℚ[x, y]. Indeed, setting y = 0 shows that H(x) = x+t(1+x)F (x, 0) while setting x = 0 gives V (y) = t(1+y)F (0, y).

2.3. The kernel method

We are going to apply to (7) the obstinate kernel method that has already been used in [4, 5] to solve similar equations. The classical kernel method consists in coupling the variables x and y so as to cancel the kernel K(x, y). This gives some “missing” information about the series V (y) and H(x) (see for instance [6, 1]). In its obstinate version, the kernel method is combined with a procedure that constructs and exploits several (related) couplings (x, y). This procedure is essentially borrowed from [9], where similar functional equations occur in a probabilistic context.

Let us start with the standard kernel method. First fix x, and consider the kernel (8) as a quadratic polynomial in y. Only one of its roots, denoted Y_{0} below, is a power series in t:

Y_{0} = \frac{1 − (x̄ + 3 + x)t − \sqrt{(1 − (1 + x + x̄)t)^{2} − 4t}}{2 (1 + x̄) t}

= (1 + x)t + \frac{(1 + x)(1 + 3x + x^{2})}{x}t^{2} + ⋯

The coefficients of this series are Laurent polynomials in x, as is easily seen from the equation

Y_{0} = t(1 + x + Y_{0}) (1 + (1 + x̄)Y_{0}) .  (9)

Setting y = Y_{0} in (7) gives a valid identity between series of ℚ[x, x̄][[t]], namely

xH(x) + Y_{0}V (Y_{0}) = xY_{0} + x^{2}Y_{0} + x^{2}.

The second root of the kernel is Y_{1} = x/Y_{0} = O(t^{−1}), so that the expression F (x, Y_{1}) is not well-defined.

Now let (X, Y) ≠ (0, 0) be a pair of Laurent series in t with coefficients in a field 𝕂 such that K(X, Y) = 0. Recall that K is quadratic in x and y. In particular, the equation K(x, Y) = 0 admits a second solution X′. Define Φ(X, Y) = (X′, Y). Similarly, define Ψ(X, Y) = (X, Y′), where Y′ is the second solution of K(X, y) = 0. Note that Φ and Ψ are involutions. Moreover, with the kernel given by (8), one has Y′ = X/Y and X′ = Y/X. Let us examine the action of Φ and Ψ on the pair (x, Y_{0}): we obtain an orbit of cardinality 6 (Figure 1).

(x, Y_{0}) Φ  Φ Ψ  Ψ Φ  Ψ (x̄Y_{0}, Y_{0}) (x̄Y_{0}, x̄)  (x, Y_{1}) (x̄Y_{1}, Y_{1}) (x̄Y_{1}, x̄)

Figure 1. The orbit of (x, Y_{0}) under the action of Φ and Ψ.

The 6 pairs of power series given in Figure 1 cancel the kernel, and we have framed the ones that can be legally substituted for (x, y) in the main functional equation (7). Denoting Y ≡ Y_{0}, we thus obtain three equations relating the unknown series H(x) and V (y):

xH(x) + Y V (Y) = xY + x^{2}Y + x^{2},  (10)
x̄Y H(x̄Y) + Y V (Y) = x̄Y^{2} + x̄^{2}Y^{3} + x̄^{2}Y^{2},  (11)
x̄Y H(x̄Y) + x̄V (x̄) = x̄^{2}Y + x̄^{3}Y^{2} + x̄^{2}Y^{2}.  (12)

2.4. Positive and negative parts of power series

A simple linear combination of the above three equations (namely, (10)−(11)+(12)) allows us to eliminate the terms V (Y) and H(x̄Y). We are left with:

xH(x) + x̄V (x̄) = x^{2} + (x̄^{2} + x + x^{2})Y + (x̄^{3} − x̄)Y^{2} − x̄^{2}Y^{3}.

Since xH(x) contains only positive powers of x and x̄V (x̄) contains only negative powers of x, we have characterized the series H(x) and V (y).

Proposition 6. The series H(x) and V (y) counting Q_{2}-vacillating walks of even length starting at (1, 0) and ending on the x-axis and on the y-axis satisfy

xH(x) = PT_{x} (x^{2} + (x̄^{2} + x + x^{2})Y + (x̄^{3} − x̄)Y^{2} − x̄^{2}Y^{3}) ,

x̄V (x̄) = NT_{x} (x^{2} + (x̄^{2} + x + x^{2})Y + (x̄^{3} − x̄)Y^{2} − x̄^{2}Y^{3}) ,

where the operator PT_{x} (respectively NT_{x}) extracts positive (respectively negative) powers of x in series of ℚ[x, x̄][[t]].

One may then go back to (5–6) to obtain expressions of the series F_{e}(x, y; t) and F_{o}(x, y; t). However, our main concern in this note is the number C_{3}(n) of 3-noncrossing partitions of [n]. Going back to (4), we find that C_{3}(n) is determined by the following three equations:

C_{3}(n) = q_{2}((1, 0), (1, 0), 2n) − q_{2}((1, 0), (0, 1), 2n),
q_{2}((1, 0), (1, 0), 2n) = [xt^{n}] H(x) = [x^{2}t^{n}] xH(x),
q_{2}((1, 0), (0, 1), 2n) = [yt^{n}] V (y) = [x̄^{2}t^{n}] x̄V (x̄).

Using Proposition 6, we obtain the generating function C(t) of 3-noncrossing partitions:

C(t) = CT_{x} (x̄^{2} − x^{2}) (x^{2} + (x̄^{2} + x + x^{2})Y + (x̄^{3} − x̄)Y^{2} − x̄^{2}Y^{3}) , (13)

where the operator CT_{x} extracts the constant term in x of series in ℚ[x, x̄][[t]]. Observe that Y (x) = xY (x̄). This implies that for all k ∈ ℕ and ℓ ∈ ℤ,

[x^{ℓ}]Y (x)^{k} = [x^{ℓ−k}]Y (x̄)^{k} = [x^{k−ℓ}]Y (x)^{k}, that is, CT_{x}(x^{−ℓ}Y^{k}) = CT_{x}(x^{ℓ−k}Y^{k}).

This allows us to rewrite (13) using “only” six terms:

C(t) = 1 + CT_{x} ((x̄^{1} − x^{4})Y + (x̄^{5} − x̄)Y^{2} − (x̄^{4} − x^{0})Y^{3}) .

The above equation says that C(t) is the constant term of an algebraic function. By a very general theory [17], C(t) is D-finite. That is, it satisfies a linear differential equation with polynomial coefficients. In the next section, we show that C(t) satisfies the equation (2) (or, equivalently, the P-recurrence (1)). Note that this recurrence can be easily guessed using the Maple package Gfun: indeed, the first 15 values of C_{3}(n) already yield the correct recursion.

2.5. The Lagrange inversion formula and creative telescoping

From now on, several routes lead to the recurrence relation of Proposition 1, depending on how much software one is willing to use. We present here the one that we believe to be the shortest. Starting from (9), the Lagrange inversion formula gives [23, Thm. 5.4.2]:

[t^{n}] CT_{x} (x^{ℓ}Y^{k}) = ∑_{j∈ℤ} a_{n}(ℓ, k, j) with a_{n}(ℓ, k, j) = \frac{k}{n}\binom{n}{j}\binom{n}{j + k}\binom{2j + k}{j − ℓ}.

(14)

By convention, the binomial coefficient \binom{a}{b} is zero unless 0 ≤ b ≤ a. Hence for n ≥ 1,

C_{3}(n) = ∑_{j∈ℤ} (a_{n}(−1, 1, j) − a_{n}(4, 1, j) + a_{n}(−5, 2, j − 1) − a_{n}(−1, 2, j − 1)

−a_{n}(−4, 3, j − 1) + a_{n}(0, 3, j − 1)) . (15)

Of course, we could replace all occurrences of j−1 by j in the above expression, but this results in a bigger final formula.

Proposition 7. For n ≥ 1, the number of 3-noncrossing partitions of [n] is

C_{3}(n) = ∑_{j=1}^{n} \frac{4(n − 1)! n! (2j)!}{(j − 1)! j! (j + 1)! (j + 4)! (n − j)! (n − j + 2)!}P (j, n)

with

P (j, n) = 24 + 18 n + (5 − 13 n) j + (11 n + 20) j^{2}

+ (10 n − 2) j^{3} + (4 n − 11) j^{4} − 6 j^{5}.

Proof of the recurrence relation of Proposition 1. We finally apply to the above expression Zeilberger’s algorithm for creative telescoping [20, Ch. 6] (we used the Maple package Ekhad, available from http://www.math.rutgers.edu/∼zeilberg/programsAB.html). This gives a recurrence relation for the sequence C_{3}(n): for n ≥ 2,

9n(n − 2)(n − 3) (4n^{2} + 15n + 17) C_{3}(n − 3)

− (n − 2) (76n^{4} + 373n^{3} + 572n^{2} + 203n − 144) C_{3}(n − 2)
+ (n + 3) (44n^{4} + 189n^{3} + 227n^{2} + 30n − 160) C_{3}(n − 1)

− (n + 5)(n + 4)(n + 3) (4n^{2} + 7n + 6) C_{3}(n) = 0.

The initial conditions are C_{3}(0) = C_{3}(1) = 1. (There is no need to define C_{3}(−1), because of the factor (n − 2) in the coefficient of C_{3}(n − 3).) It is then very simple to check that the sequence defined by these two initial conditions and the three term recursion of Proposition 1 satisfies also the above four term recursion. This can be rephrased by saying that (1) is a right factor of the four term recursion obtained via creative telescoping. More precisely, applying to (1) the operator

(n + 1) (4 n^{2} + 39 n + 98) − (n + 6) (4 n^{2} + 31 n + 63) N,

where N is the shift operator replacing n by n+1, gives the four term recursion (with n replaced by n + 3).

It is worth noting that though the sequence {C_{3}(n) : n ∈ ℕ} = {w_{2}((1, 0), (1, 0), 2n) : n ∈ ℕ} satisfies a simple recurrence of order 2 (given by (1)), experimenting with the package Gfun suggests that the sequences {q_{2}((1, 0), (1, 0), 2n) : n ∈ ℕ} and {q_{2}((1, 0), (0, 1), 2n) : n ∈ ℕ} satisfy more complicated recurrences of order 3.

2.6. Asymptotics

Finally, we will derive from the expression (15) of C_{3}(n) the asymptotic behaviour of this sequence, as stated in Proposition 1. For any fixed values of k and ℓ, with k ≥ 1, we consider the numbers a_{n}(ℓ, k, j) defined by (14). For the sake of simplicity, we denote them by a_{n}(j), and introduce the numbers

b_{n}(j) = \binom{n}{j}\binom{n}{j + k}\binom{2j + k}{j − ℓ},

so that a_{n}(j) = k b_{n}(j)/n. Let B_{n} = ∑_{j} b_{n}(j). The sum runs over j ∈ [ℓ_{+}, n − k], where ℓ_{+} = max(ℓ, 0). Below, we often consider j as a real variable running in that interval. The number b_{n}(j) is then defined in terms of the Gamma function rather than in terms of factorials. We will show that B_{n} admits, for any N, an expansion of the form

B_{n} = 9^{n} (∑_{i=1}^{N} \frac{c_{i}}{n^{i}} + O(n^{−N−1})) ,  (16)

where the coefficients c_{i} depend on k and ℓ, and explain how to obtain these coefficients. We follow the standards steps for estimating sums of positive terms that are described, for instance, in [2, Section 3]. We begin with a unimodality property of the numbers b_{n}(j).

Lemma 8 (Unimodality). For n large enough, the sequence b_{n}(j), for j ∈ [ℓ_{+}, n − k], is unimodal, and its maximum is reached in the interval [2n/3 − k/2 − 1/2, 2n/3 − k/2 − 1/3].

Proof. One has

q_{n}(j) := \frac{b_{n}(j)}{b_{n}(j + 1)}

= \frac{1}{(n − j)(n − j − k)} \frac{(j + 1)(j + k + 1)}{2j + k + 1} \frac{(j − ℓ + 1)(j + k + ℓ + 1)}{2j + k + 2}.

Each of these three factors is easily seen to be an increasing function of j on the relevant interval. Moreover, for n large enough, q_{n}(ℓ_{+}) < 1 while q_{n}(n−k−1) > 1. Let j_{0} be the smallest value of j such that q_{n}(j) ≥ 1. Then b_{n}(j) < b_{n}(j +1) for j < j_{0} and b_{n}(j) ≥ b_{n}(j + 1) for j ≥ j_{0}. We have thus proved unimodality. Solving q_{n}(x) = 1 for x helps to locate the mode:

x = \frac{2n}{3} − \frac{5 + 6k}{12} + O(1/n).

It is then easy to check that q_{n}(2n/3−k/2−1/2) < 1 and q_{n}(2n/3−k/2−1/3) > 1 for n large enough.

The second step of the proof reduces the range of summation.

Lemma 9 (A smaller range). Let ϵ ∈ (0, 1/6). Then for all m,

B_{n} = ∑_{|j−2n/3|≤n^{1/2+ϵ}} b_{n}(j) + o(9^{n}n^{−m}).

Proof. Let j = 2n/3 ± n^{1/2+ϵ}. The Stirling formula gives

b_{n}(j) = (\frac{3}{2})^{5/2} \frac{9^{n}}{(πn)^{3/2}} e^{−9n^{2ϵ}/2}(1 + o(1)) = o(9^{n}n^{−m})  (17)

for all m (the details of the calculation are given in greater detail below, in the proof of Lemma 10). Thus by Lemma 8,

∑_{|j−2n/3|>n^{1/2+ϵ}} b_{n}(j) ≤ n (b_{n}(2n/3 − n^{1/2+ϵ}) + b_{n}(2n/3 + n^{1/2+ϵ})) = o(9^{n}n^{−m}).

The result follows.

A first order estimate of b_{n}(j), generalizing (17), suffices to obtain, upon summing over j, an estimate of B_{n} of the form (16) with N = 1. However, numerous cancellations occur when summing the 6 terms a_{n}(ℓ, k, j) in the expression (15) of C_{3}(n). This explains why we have to work out a longer expansion of the numbers b_{j}(n) and B_{n}.

Lemma 10 (Expansion of b_{j}(n)). Let ϵ ∈ (0, 1/6). Write j = 2n/3 + r with r = s\sqrt{n} and |s| ≤ n^{ϵ}. Then for all N ≥ 1,

b_{n}(j) = \binom{n}{j}\binom{n}{j + k}\binom{2j + k}{j − ℓ}

= (\frac{3}{2})^{5/2} \frac{9^{n}}{(πn)^{3/2}} e^{−9r^{2}/(2n)} (∑_{i=0}^{N−1} \frac{c_{i}(s)}{n^{i/2}} + O(n^{N(3ϵ−1/2)}))

where c_{i}(s) is a polynomial in k, ℓ and s, of degree 3i in s. Moreover, c_{i} is an even [odd] function of s if i is even [odd]. In particular, c_{0}(s) = 1. This expansion is uniform in s.

Proof. Note that we simply want to prove the existence of an expansion of the above form. The coefficients can be obtained routinely using (preferably) a computer algebra system. In what follows, (c_{i})_{i≥0} stands for a sequence of real numbers such that c_{0} = 1. The actual value of c_{i} may change from one formula to another. Similarly, (c_{i}(s))_{i≥0} denotes a sequence of polynomials in s such that c_{0}(s) = 1, having the parity property stated in the lemma.

We start from the Stirling expansion of the Gamma function: for all N ≥ 1,

Γ(n + 1) = n^{n}\sqrt{2πn} e^{−n} (∑_{i=0}^{N−1} \frac{c_{i}}{n^{i}} + O(n^{−N})) .  (18)

This gives, for j = 2n/3 + r, with r = s\sqrt{n}, and for any N,

Γ(j + 1) = 2j^{j}\sqrt{\frac{πn}{3}}e^{−j} (∑_{i=0}^{N−1} \frac{c_{i}(s)}{n^{i/2}} + O(n^{N(ϵ−1/2)}))  (19)

for some polynomials c_{i}(s) of degree i in s. This estimate is uniform in s. Similarly,

Γ(n − j + 1) = (n − j)^{n−j}\sqrt{\frac{2πn}{3}} e^{j−n} (∑_{i=0}^{N−1} \frac{c_{i}(s)}{n^{i/2}} + O(n^{N(ϵ−1/2)})) , (20)

for some polynomials c_{i}(s) of degree i in s. Now

log \frac{n^{n}}{j^{j}(n − j)^{n−j}} = log \frac{3^{n}}{2^{j}} − \frac{9r^{2}}{4n} − ∑_{i≥2} \frac{3^{i} r^{i+1}}{i(i + 1)n^{i}} (1 − (−1/2)^{i})

= log \frac{3^{n}}{2^{j}} − \frac{9r^{2}}{4n} − ∑_{i=1}^{N−1} \frac{c_{i}(s)}{n^{i/2}} + O(n^{2ϵ+N(ϵ−1/2)}),

for some polynomials c_{i}(s) of degree i + 2 in s. Observe that (i + 2)/(i/2) ≤ 6 for i ≥ 1. Hence

\frac{n^{n}}{j^{j}(n − j)^{n−j}} = \frac{3^{n}}{2^{j}} e^{−9r^{2}/(4n)} exp (− ∑_{i=1}^{N−1} \frac{c_{i}(s)}{n^{i/2}} + O(n^{2ϵ+N(ϵ−1/2)}))

= \frac{3^{n}}{2^{j}} e^{−9r^{2}/(4n)} (∑_{i=0}^{N−1} \frac{c_{i}(s)}{n^{i/2}} + O(n^{N(3ϵ−1/2)})) ,  (21)

for polynomials c_{i}(s) of degree 3i in s. Putting together (18–21), one obtains, uniformly in s:

\binom{n}{j} = \frac{3}{2\sqrt{πn}} \frac{3^{n}}{2^{j}} e^{−9r^{2}/(4n)} (∑_{i=0}^{N−1} \frac{c_{i}(s)}{n^{i/2}} + O(n^{N(3ϵ−1/2)})) ,  (22)

for polynomials c_{i}(s) of degree 3i in s.

Similarly,

\binom{n}{j + k} = \frac{3}{2\sqrt{πn}} \frac{3^{n}}{2^{j+k}} e^{−9r^{2}/(4n)} (∑_{i=0}^{N−1} \frac{c_{i}(s)}{n^{i/2}} + O(n^{N(3ϵ−1/2)})) , (23)

with the same degree condition on the polynomials c_{i}(s). Finally,

\binom{2j + k}{j − l} = \sqrt{\frac{3}{2πn}}2^{2j+k} (∑_{i=0}^{N−1} \frac{c_{i}(s)}{n^{i/2}} + O(n^{N(ϵ−1/2)}))  (24)

for polynomials c_{i}(s) of degree i in s. Putting together (22–24), we obtain the estimate of b_{n}(j) given in the lemma.

It remains to sum our estimates of b_{n}(j) for values of j such that |j −2n/3| ≤ n^{1/2+ϵ}.

Proposition 11 (Expansion of B_{n}). For all N ≥ 1,

B_{n} = ∑_{j} \binom{n}{j}\binom{n}{j + k}\binom{2j + k}{j − ℓ}

= (\frac{3}{2})^{5/2} \frac{9^{n}}{π^{3/2}n} (∑_{i=0}^{N−1} \frac{1}{n^{i}} ∫_{ℝ} c_{2i}(s)e^{−9s^{2}/2}ds + O(n^{−N}))

where the polynomials c_{i}(s), depending on k and ℓ, are those of Lemma 10. In particular, as c_{0}(s) = 1,

B_{n}(j) = \frac{3^{3/2}}{4π} \frac{9^{n}}{n} (1 + O(1/n)) .

Proof. We start from Lemma 9, and combine it with the uniform expansion of Lemma 10. We need to estimate sums of the following type, for i ∈ ℕ:

∑_{|j−2n/3|≤n^{1/2+ϵ}} (\frac{j − 2n/3}{\sqrt{n}})^{i} e^{−9(j−2n/3)^{2}/(2n)}.

Using the Euler-MacLaurin summation formula [19, Eq. (5.62)], one obtains, for all m ≥ 1,

\frac{1}{\sqrt{n}} ∑_{|j−2n/3|≤n^{1/2+ϵ}} (\frac{j − 2n/3}{\sqrt{n}})^{i} e^{−9(j−2n/3)^{2}/(2n)} = ∫_{ℝ} s^{i}e^{−9s^{2}/2}ds + o(n^{−m}).

The above integral vanishes if i is odd, and can be expressed in terms of the Gamma function otherwise. This gives the estimate of Proposition 11, but with a rest of order n^{N(6ϵ−1)}. However, this expansion is valid for all N, and for all ϵ > 0. From this, the rest can be seen to be of order n^{−N}.

With the strategy described above (and Maple...), we have obtained the expansion of B_{n} to the order n^{−6}. Given that a_{n}(j) ≡ a_{n}(ℓ, k, j) = k b_{n}(j)/n, this gives the expansion of ∑_{j} a_{n}(ℓ, k, j) to the order n^{−7}:

∑_{j} a_{n}(ℓ, k, j) = \frac{3^{3/2}}{4π} \frac{9^{n}}{n^{2}} (∑_{i=0}^{5} \frac{c_{i}}{(4n)^{i}} + O(1/n^{6})) .

The coefficients of this expansion are too big to be reported here for generic values of k and ℓ (apart from c_{0} = k). We simply give the values of c_{i} for the 6 pairs (ℓ, k) that are involved in the expression (15) of C_{3}(n):

(ℓ, k) c_{0} c_{1}  c_{2}  c_{3}  c_{4}  c_{5}
(−1, 1) 1 −7  37  −184  871  −4087  +
(4, 1) 1 −127 8317 −381904 14034391 −444126847 −
(−5, 2) 2 −230 13682 −573416 19338062 −564941270 +
(−1, 2) 2 −38 434 −4136 36302 −305558 −
(−4, 3) 3 −237 9831 −293664 7227813 −157405197 −
(0, 3) 3 −165 4863 −106104 1959573 −32693205 +

Each pair (ℓ, k) contributes in the expression of C_{3}(n) with a weight ±1, depending on the sign indicated on the corresponding line of the above table. One observes that the first 5 terms cancel, which leaves

C_{3}(n) = \frac{3^{3/2}}{4π} \frac{9^{n}}{n^{2}} (\frac{4199040}{(4n)^{5}} + O(1/n^{6})) .

This completes the proof of Proposition 1.

2.7. Other starting points

So far, we have focused on the enumeration of Q_{2}-vacillating walks starting at (1, 0). However, our approach works just as well for other starting points, or for combinations of starting points. Let A(x, y) be the generating function of starting points. For instance, A(x, y) = x^{i}y^{j} corresponds to starting at (i, j), while A(x, y) = 1/(1 − x) corresponds to starting anywhere on the x-axis.

Then a calculation similar to that of Section 2.2 gives the following functional equation

K(x, y; t)F^{A}(x, y; t) = (x + y + xy)A(x, y) − xH^{A}(x; t) − yV^{A}(y; t),

where F^{A}, H^{A}, and V^{A} are the analogues of F, H and V. Specializing A(x, y) to x gives back (7). The kernel method of Section 2.3 now gives

xH^{A}(x) + x̄V^{A}(x̄) = (x + Y + xY) A (x, Y) − (x̄Y + Y + x̄Y^{2}) A (x̄Y, Y)

+ (x̄Y + x̄ + x̄^{2}Y ) A (x̄Y, x̄) .

Thus if A is a rational function (and in particular if A(x, y) = x^{i}y^{j}), then H^{A}(x), V^{A}(x), and F^{A}(x, y) are all D-finite.

3. Partitions with no enhanced 3-crossing

Our approach for counting 3-noncrossing partitions can be easily adapted to the enumeration of partitions avoiding enhanced 3-crossings. As discussed in [8], partitions of [n] avoiding enhanced k + 1-crossings are in bijection with hesitating tableaux of height at most k. In turn, these hesitating tableaux are in one-to-one correspondence with certain W_{k}-hesitating lattice walks. A hesitating lattice walk satisfies the following walking rules: when pairing every two steps from the beginning, each pair of steps has one of the following three types: i) a stay step followed by an e_{i} step, ii) a −e_{i} step followed by a stay step, iii) an e_{i} step followed by a −e_{j} step.

Then partitions of [n] avoiding enhanced k +1-crossings are in bijection with W_{k}-hesitating walks of length 2n starting and ending at (k − 1, …, 2, 1, 0). As before, W_{k} denotes the Weyl chamber { (a_{1}, a_{2}, …, a_{k}) ∈ ℤ^{k} : a_{1} > a_{2} > ⋯ > a_{k} ≥ 0 }.

For convenience, all notations we used for vacillating walks will be recycled for hesitating walks. Thus δ = (k − 1, k − 2, …, 0), and for two lattice points λ and μ in W_{k}, we denote by w_{k}(λ, μ, n) (respectively q_{k}(λ, μ, n)) the number of W_{k}-hesitating (respectively Q_{k}-hesitating) lattice walks of length n starting at λ and ending at μ. A careful investigation shows that the reflection principle “works” for hesitating lattice walks.

Proposition 12. For any starting and ending points λ and μ in W_{k}, the number of W_{k}-hesitating walks going from λ to μ can be expressed in terms of the number of Q_{k}-hesitating walks as follows:

w_{k}(λ, μ, n) = ∑_{π∈𝔖_{k}}(−1)^{π}q_{k}(λ, π(μ), n),

where (−1)^{π} is the sign of π and π(μ_{1}, μ_{2}, …, μ_{k}) = (μ_{π(1)}, μ_{π(2)}, …, μ_{π(k)}).

Proof. The key property here is that the set of pairs of steps that are allowed for a hesitating walk is left invariant when reflecting either one, or both steps with respect to the hyperplane x_{i} = x_{j}. This is clearly seen by abbreviating the three types of step pairs as (0, +), (−, 0) and (+, −), and recalling that the above reflection exchanges the ith and jth coordinates (equivalently, the unit vectors e_{i} and e_{j}). The rest of the argument copies the proof of Proposition 4.

Let us now focus on the case k = 2. The connection between W_{2}-hesitating walks and partitions avoiding enhanced 3-crossings entails

E_{3}(n) = w_{2}((1, 0), (1, 0), 2n) = q_{2}((1, 0), (1, 0), 2n) − q_{2}((1, 0), (0, 1), 2n). (25)

Let us write a functional equation counting Q_{2}-hesitating walks that start from (1, 0). Let a_{i,j}(n) := q_{2}((1, 0), (i, j), 2n) be the number of such walks having length 2n and ending at (i, j). Let

F (x, y; t) = ∑_{i,j,n} a_{i,j}(2n)x^{i}y^{j}t^{n}

be the associated generating function. Then by appending to an (even length) walk an allowed pair of steps, we obtain the following functional equation:

(x + y + x̄ + ȳ + (x + y)(x̄ + ȳ)) tF (x, y; t)

= F (x, y; t) − x + H(x; t)(ȳ + xȳ)t + V (y; t)(x̄ + x̄y)t,

where H(x; t) (respectively V (y; t)) is the generating function of even lattice walks ending on the x-axis (respectively y-axis). This functional equation can be rewritten as

K(x, y; t)F (x, y; t) = x^{2}y − x(1 + x)tH(x; t) − y(1 + y)tV (y; t),  (26)

where K(x, y; t) is the kernel given by

K(x, y; t) = xy − t(1 + x)(1 + y)(x + y).

From now on, we will very often omit the variable t in our notation.

Let us now solve (26). First fix x, and consider the kernel as a quadratic polynomial in y. Only one of its roots, denoted Y below, is a formal series in t:

Y = \frac{1 − tx̄(1 + x)^{2} − \sqrt{(1 − tx̄(1 + x)^{2})^{2} − 4tx̄(1 + x)^{2}}}{2 (1 + x̄) t} = O(t).

The coefficients of this series are Laurent polynomials in x, as is easily seen from the equation

Y = t(1 + x̄)(1 + Y)(x + Y).  (27)

The second root of the kernel is Y_{1} = x/Y = O(t^{−1}), and the expression F (x, Y_{1}) is not well-defined.

Observe that the new kernel only differs from (8) by a term txy. Hence, as in the case of vacillating walks, the product of the roots is x, and the kernel is symmetric in x and y. This implies that the diagram of the roots, obtained by taking iteratively conjugates, is still given by Figure 1. Again, the 3 pairs of power series that are framed can be legally substituted for (x, y) in the functional equation (26). We thus obtain:

x(1 + x)tH(x) + Y (1 + Y)tV (Y) = x^{2}Y,  (28)
x̄Y (1 + x̄Y)tH(x̄Y) + Y (1 + Y)tV (Y) = x̄^{2}Y^{3},  (29)
x̄Y (1 + x̄Y)tH(x̄Y) + x̄(1 + x̄)tV (x̄) = x̄^{3}Y^{2}.  (30)

Now (28)−(29)+(30) gives

x(1 + x)tH (x) + x̄(1 + x̄)tV \binom{}{x̄} = x^{2}Y − x̄^{2}Y^{3} + x̄^{3}Y^{2}.

By (27), the series Y/t/(1+x) is a formal series in t with coefficients in ℚ[x, x̄]. Thus we can divide the above identity by t(1+x), and then extract the positive and negative parts.

Proposition 13. The series H(x) and V (y), which count Q_{2}-hesitating walks of even length ending on the x-axis and on the y-axis, satisfy

xH(x) = PT_{x} \frac{Y}{t(1 + x)}(x^{2} − x̄^{2}Y^{2} + x̄^{3}Y),

x̄^{2}V (x̄) = NT_{x} \frac{Y}{t(1 + x)}(x^{2} − x̄^{2}Y^{2} + x̄^{3}Y).

Let us now return to the number E_{3}(n) of partitions of [n] avoiding enhanced 3-crossings, given by (25). The generating function E(t) of these numbers is:

E(t) = CT_{x} \frac{Y (x̄^{2} − x^{3})}{t(1 + x)}(x^{2} − x̄^{2}Y^{2} + x̄^{3}Y).  (31)

Observe that, again, Y (x) = xY (x̄). Therefore, for all k ∈ ℕ and ℓ ∈ ℤ,

CT_{x} (\frac{x̄^{ℓ}Y^{k}}{t(1 + x)}) = CT_{x} (\frac{x^{ℓ−k+1}Y^{k}}{t(1 + x)} ) .

This allows us to rewrite (31) with only non-negative powers of x:

E(t) = CT_{x} \frac{Y}{t(1 + x)} (1 − x^{5} − (x^{2} − x)Y^{2} + (x^{4} − 1)Y ) .  (32)

The above equation shows that E(t) is the constant term of an algebraic function. It is thus D-finite. Let us now compute a linear differential equation it satisfies (equivalently, a P-recursion for its coefficients).

Starting from (27), the Lagrange inversion formula gives

[t^{n}] CT_{x} \frac{x^{ℓ}Y^{k}}{t(1 + x)} = ∑_{j∈ℤ} a_{n}(ℓ, k, j)

with

a_{n}(ℓ, k, j) = \frac{k}{n + 1}\binom{n + 1}{j}\binom{n + 1}{j + k}\binom{n}{j − ℓ}.

From (32), we obtain

E_{3}(n) = ∑_{j∈ℤ} (a_{n}(0, 1, j) − a_{n}(5, 1, j) − a_{n}(2, 3, j) + a_{n}(1, 3, j)

+a_{n}(4, 2, j) − a_{n}(0, 2, j)) . (33)

This gives an explicit (but not so simple) expression of E_{3}(n), to which we apply Zeilberger’s algorithm for creative telescoping. This proves that, for n ≥ 1,

8n (n − 1) (n − 2) E_{3}(n − 3) + 3 (5n^{2} + 17n + 8) (n − 1) E_{3}(n − 2)

+ 3 (n + 1) (2n + 5) (n + 4) E_{3}(n − 1) − (n + 6) (n + 5) (n + 4) E_{3}(n) = 0,

with initial condition E_{3}(0) = 1. It is then straightforward to check that the sequence defined in Proposition 2 also satisfies the above P-recursion. More precisely, applying the operator (n+2)+(n+7)N to the recursion of Proposition 2 gives the above four term recursion.

The study of the aymptotic behaviour of E_{3}(n) parallels what we did for C_{3}(n). The maximum of a_{n}(ℓ, k, j) is now reached for j ∼ n/2 rather than 2n/3. Using the same notations as in Section 2.6, we obtain

B_{n}(j) ∼ \frac{8^{n+1}}{\sqrt{3}πn},

but again, numerous cancellations occur when we sum the 6 required estimates, so as to obtain the estimate of Proposition 2.

4. Final comments

It is natural to ask whether for any k, the sequence C_{k}(n) that counts knoncrossing partitions of [n] is P-recursive. Our opinion is that this is unlikely, at least for k = 4. This is based on the following observations:

(1) We have written a functional equation for Q_{3}-vacillating walks, with kernel

K(x, y, z; t) = 1 − t(1 + x + y + z)(1 + x̄ + ȳ + z̄).

Using this equation, we have computed the first 100 numbers in the sequence C_{4}(n). This is sufficient for the Maple package Gfun to discover a P-recursion of order 8 with coefficients of degree 8, if it exists. But no such recursion has been found.

(2) Let us solve the above kernel in z. The two roots Z_{0} and Z_{1} are related by

Z_{0}Z_{1} = \frac{1 + x + y}{1 + x̄ + ȳ}.  (34)

Since the kernel is symmetric in x, y and z, the diagram of the roots, obtained by taking conjugates, is generated by the transformations Φ_{i} for i = 1, 2, 3, where

Φ_{3}(x, y, z) = (x, y, z̄ \frac{1 + x + y}{1 + x̄ + ȳ})

and Φ_{1} and Φ_{2} are defined similarly. But these transformations now generate an infinite diagram. There exist in the literature a few signs indicating that a finite (respectively infinite) diagram is related to a D-finite (respectively non-D-finite) generating function. First of all, a number of equations with a finite diagram have been solved, and shown to have a D-finite solution [3, 4, 5, 18]. Furthermore, the only problem with an infinite diagram that has been thoroughly studied has been proved to be non-D-finite [7]. Finally, the conjectural link between finite diagrams and D-finite series is confirmed by a systematic numerical study of walks in the quarter plane [18].

The above paragraphs can be copied verbatim for W_{3}-hesitating walks and partitions avoiding enhanced 4-crossings. The kernel is now

K(x, y, z) = 1 − t(x + y + z + x̄ + ȳ + z̄ + (x + y + z)(x̄ + ȳ + z̄)),

but the roots Z_{0} and Z_{1} are still related by (34).

As recalled in the introduction, the sequence M_{k}(n) that counts knoncrossing matchings of [n] (that is, partitions in which all blocks have size 2) is D-finite for all k. More precisely, the associated exponential generating function,

M_{k}(t) = ∑_{n} M_{k}(n)\frac{t^{2n}}{(2n)!}

is given by [11]:

M_{k}(t) = det (I_{i−j}(2t) − I_{i+j}(2t))_{1≤i,j≤k−1} ,

where

I_{n}(2t) = ∑_{j≥0} \frac{t^{n+2j}}{j!(n + j)!}

is the hyperbolic Bessel function of the first kind of order n. The existence of such a closed form implies that M_{k}(t) is D-finite [17]. The specialization to matchings of the bijection between partitions and vacillating walks results in a bijection between k + 1-noncrossing matchings and oscillating tableaux of height at most k, or, equivalently, W_{k}-oscillating walks. These walks can take any (positive or negative) unit step ±e_{i}, without any parity restriction. The kernel of the equation ruling the enumeration of such walks is simply

K(x_{1}, …, x_{k}) = 1 − t(x_{1} + ⋯ + x_{k} + x̄_{1} + ⋯ + x̄_{k}).

The diagram of the roots, generated by the Φ_{i}, for 1 ≤ i ≤ k, where Φ_{i}(x_{1}, …, x_{k}) = (x_{1}, …, x_{i−1}, x̄_{i}, x_{i+1}, …, x_{k}), is now finite (the group of transformations Φ_{i} being itself isomorphic to (ℤ/2ℤ)^{k}). This, again, confirms the possible connection between finite diagrams and D-finite series.

Acknowledgements: We are grateful to Anders Björner and Richard Stanley for inviting us to the “Algebraic Combinatorics” program at the Institut Mittag-Leffler in Spring 2005, during which this work was done. We also thank Christian Krattenthaler for explaining us how the asymptotics of our sequences could be worked out completely. MBM was partially supported by the European Commission’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe”. GX would like to thank Richard Stanley and Rosena Du for introducing him to this topic.

References

[1] C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps. Generating functions for generating trees. Discrete Math., 246(1-3):29–55, 2002.

[2] E. A. Bender. Asymptotic methods in enumeration. SIAM Rev., 16:485–515, 1974.

[3] M. Bousquet-Mélou. Counting walks in the quarter plane. In Mathematics and computer science 2, (Versailles, 2002), Trends Math., pages 49–67. Birkhäuser, Basel, 2002.

[4] M. Bousquet-Mélou. Four classes of pattern-avoiding permutations under one roof: generating trees with two labels. Electron. J. Combinatorics, 9(2):Research Paper 19, 2003.

[5] M. Bousquet-Mélou. Walks in the quarter plane: Kreweras’ algebraic model. Ann. Appl. Probab., 15(2):1451–1491, 2005.

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

[7] M. Bousquet-Mélou and M. Petkovšek. Walks confined in a quadrant are not always D-finite. Theoret. Comput. Sci., 307:257–276, 2003.

[8] W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan. Crossings and nestings of matchings and partitions. Trans. Amer. Math. Soc., to appear. Arχiv math.CO/0501230.

[9] G. Fayolle, R. Iasnogorodski, and V. Malyshev. Random walks in the quarter-plane: Algebraic methods, boundary value problems and applications, volume 40 of Applications of Mathematics. Springer-Verlag, Berlin, 1999.

[10] I. M. Gessel and D. Zeilberger. Random walk in a Weyl chamber. Proc. Amer. Math. Soc., 115(1):27–31, 1992.

[11] D. J. Grabiner and P. Magyar. Random walks in Weyl chambers and the decomposition of tensor powers. J. Algebraic Combin., 2(3):239–260, 1993.

[12] E. L. Ince. Ordinary Differential Equations. Dover Publications, New York, 1944.

[13] A. Kasraoui and J. Zeng. Distribution of crossings, nestings and alignments of two edges in matchings and partitions. Arχiv math.CO/0601081.

[14] M. Klazar. Bell numbers, their relatives, and algebraic differential equations. J. Combin. Theory Ser. A, 102(1):63–87, 2003.

[15] C. Krattenthaler. Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes. Adv. Appl. Math., to appear. Arχiv:math.CO/0510676.

[16] G. Kreweras. Sur les partitions non croisées d’un cycle. Discrete Math., 1(4):333–350, 1972.

[17] L. Lipshitz. D-finite power series. J. Algebra, 122:353–373, 1989.

[18] M. Mishna. Classifying lattice walks in the quarter plane. In preparation.

[19] A. M. Odlyzko. Asymptotic enumeration methods. In Handbook of combinatorics, Vol. 1, 2, pages 1063–1229. Elsevier, Amsterdam, 1995.

[20] M. Petkovšek, H. S. Wilf, and D. Zeilberger. A = B. A K Peters Ltd., Wellesley, MA, 1996.

[21] B. Salvy and P. Zimmermann. Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable. ACM Transactions on Mathematical Software, 20(2):163–177, 1994.

[22] R. Simion. Noncrossing partitions. Discrete Math., 217(1-3):367–409, 2000.

[23] R. P. Stanley. Enumerative combinatorics 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.

[24] J. Wimp and D. Zeilberger. Resurrecting the asymptotics of linear recurrences. J. Math. Anal. Appl., 111(1):162–176, 1985.

[25] D. Zeilberger. André’s reflection proof generalized to the many-candidate ballot problem. Discrete Math., 44(3):325–326, 1983.

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

  E-mail address: mireille.bousquet@labri.fr

941 Patterson Office Tower, Department of Mathematics, University of Kentucky, Lexington, KY 40506–0027, USA

  E-mail address: guoce.xin@gmail.com