Linear recurrences with constant coefficients: the multivariate case

Mireille Bousquet-Mélou^{∗}

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

      bousquet@labri.u-bordeaux.fr

Marko Petkovšek^{†}

Dept. Mathematics and Mechanics University of Ljubljana Jadranska 19, 1111 Ljubljana, Slovenia

                                         Marko.Petkovsek@fmf.uni-lj.si

Abstract While in the univariate case solutions of linear recurrences with constant coefficients have rational generating functions, we show that the multivariate case is much richer: even though initial conditions have rational generating functions, the corresponding solutions can have generating functions which are algebraic but not rational, D-finite but not algebraic, and even non D-finite.

1 Introduction

The aim of this paper is to study the nature of multivariate generating functions

F (x_{1}, …, x_{d}) = ∑_{n_{1},...,n_{d}≥0} a_{n_{1},...,n_{d}}x_{1}^{n_{1}} ⋯ x_{d}^{n_{d}} = ∑_{n≥0} a_{n}x^{n}

whose coefficients satisfy a linear recurrence relation with constant coefficients

a_{n} = c_{h_{1}}a_{n+h_{1}} + c_{h_{2}}a_{n+h_{2}} + ⋯ + c_{h_{k}}a_{n+h_{k}} for n ≥ s ,

with adequate initial conditions. The univariate case (d = 1) is well-known to give rise to rational generating functions. We shall show that the multivariate case is much richer.

We start by an existence and uniqueness theorem that actually applies to recurrences of a more general form

a_{n} = Φ(a_{n+h_{1}}, a_{n+h_{2}}, …, a_{n+h_{k}}) for n ≥ s ,

where the values of a_{n} for n ≱ s are given explicitly. In particular, we show that the lattice points in the first orthant (i.e., n ≥ 0) can be enumerated in such a way that for all n the points n + h_{i} precede n in this enumeration, if and only if the convex hull of the set H = {h_{1}, h_{2}, …, h_{k}} does not intersect the first orthant (Section 2). This condition on H, which ensures existence and uniqueness of the solution, is assumed to be satisfied in the sequel.

∗Partially supported by the Conseil Régional d’Aquitaine.

†Partially supported by MZT RS under grant J2-8549.

For linear recurrences with constant coefficients, we show that when initial conditions grow at most exponentially, the same is true of the solution, which is consequently analytic in a neighbourhood of the origin (Section 3).

Next, we study the algebraic nature of the generating function of the solution of such recurrences (Section 4). We define the apex of H as the componentwise maximum of the points in H ∪ {0}. When the initial conditions have rational generating functions and the apex of H is 0, the generating function of the solution is rational and given by an explicit formula. When the initial conditions have algebraic generating functions and the apex of H has at most one positive coordinate, the generating function of the solution is algebraic and is given explicitly in terms of the solutions of an algebraic equation. We give various applications to the enumeration of lattice paths that generalize Dyck paths.

When the apex has more than one positive coordinate, and the initial conditions have rational generating functions, the generating function of the solution need not be algebraic, which we demonstrate on the problem of Young tableaux of bounded height. However, the solution here remains D-finite. We conclude the paper with a simple example showing that non-D-finite solutions (and even, hypertranscendental solutions) might also occur.

The main tool that we use is the so-called kernel method which permits to solve certain systems of linear functional equations that seem to contain too many “unknowns”. It works by restricting the equations to algebraic varieties on which some of the unknown terms vanish, thus providing the “missing” equations (see Section 4 for more detail).

Notations. We use ℕ to denote the set of nonnegative integers. We write u = (u_{1}, u_{2}, …, u_{d}) for d-tuples of numbers or indeterminates, 0 = (0, 0, …, 0), 1 = (1, 1, …, 1), u ≥ v when u_{i} ≥ v_{i} for 1 ≤ i ≤ d, and u > v when u_{i} > v_{i} for 1 ≤ i ≤ d. The monomial x_{1}^{u_{1}} ⋯ x_{d}^{u_{d}} is denoted x^{u}. For u, v ∈ ℤ^{d}, the scalar product u_{1}v_{1} + ⋯ + u_{d}v_{d} is denoted u · v. The convex hull of a set H ⊆ ℝ^{d} is denoted conv H.

2 An existence and uniqueness theorem

Let A be a nonempty set. We consider d-dimensional recurrence equations of the form

a_{n} = Φ(a_{n+h_{1}}, a_{n+h_{2}}, …, a_{n+h_{k}}) for n ≥ s,  (1)

where a : ℕ^{d} → A is the unknown d-dimensional sequence of elements of A, Φ : A^{k} → A is a given function, H = {h_{1}, h_{2}, …, h_{k}} ⊆ ℤ^{d} is the set of shifts, and s ∈ ℕ^{d} is the starting point satisfying s + H ⊆ ℕ^{d}. A given function φ specifies the initial conditions:

a_{n} = φ(n) for n ≥ 0, n ≱ s .  (2)

We think of the h_{i} as having mostly (but not necessarily only) negative coordinates, and of the point n as depending on the points n + h_{1}, n + h_{2}, …, n + h_{k} as far as the value of a_{n} is concerned.

The objective of this section is to characterize the sets H for which there is an ordering of ℕ^{d} of order type ω such that the points n + h_{1}, n + h_{2}, …, n + h_{k} precede n in this ordering. Then there exists a unique solution of (1) – (2), and for any n ∈ ℕ^{d} it is possible to compute the value of a_{n} directly from (1) – (2) in a finite number of steps.

We first define a dependency relation on the points of ℕ^{d}, induced by the set H.

Definition 1 For H ⊆ ℤ^{d} and p, q ∈ ℕ^{d}, let

p ≺_{H} q if and only if p ∈ q + H ⊆ ℕ^{d} .

The transitive closure ≺_{H}^{+} of ≺_{H} in ℕ^{d} is the dependency relation corresponding to H.

Lemma 2 Let p, q, u, v ∈ ℕ^{d}. Then

p ≺_{H}^{+} q, u ≺_{H}^{+} v implies p + u ≺_{H}^{+} q + v .

Proof: Clearly ≺_{H} is translation-invariant: if p ≺_{H} q, then p + r ≺_{H} q + r. Therefore ≺_{H}^{+} is translation-invariant as well, so p ≺_{H}^{+} q implies p + u ≺_{H}^{+} q + u and u ≺_{H}^{+} v implies q + u ≺_{H}^{+} q + v. By transitivity, p + u ≺_{H}^{+} q + v.

Recall that a binary relation R ⊆ A × A is well-founded if it is transitive and has no infinite descending chains in A (there exists no sequence (a_{n})_{n≥1} of elements of A such that a_{n+1} R a_{n} for all n). Note that a well-founded relation is irreflexive and asymmetric.

Theorem 3 Let H ⊆ ℤ^{d} be a finite set, and ≺_{H}^{+} the corresponding dependency relation. Then the following are equivalent:

(i) ≺_{H}^{+} is well-founded in ℕ^{d},

(ii) {x ∈ ℝ^{d}; x ≥ 0} ∩ conv H = ∅,

(iii) there exists v ∈ ℕ^{d}, v > 0, such that v · h < 0 for all h ∈ H,

(iv) ≺_{H}^{+} can be extended to an ordering of ℕ^{d} of order type ω.

First we establish a lemma about rational points in convex subsets of ℝ^{d} (a point is rational if it belongs to ℚ^{d}).

Lemma 4 Let X ⊆ ℝ^{d} be a finite set of rational points, and p ∈ conv X. Then p is rational if and only if it can be expressed as a rational convex combination of points from X.

Proof: If p is a rational convex combination of rational points then clearly p is rational.

Conversely, let p ∈ conv X be rational. Let S ⊆ X be a minimal subset with the property that p ∈ conv S. Let e be the affine dimension of S. By Carathéodory’s theorem (cf. [21, Thm. 17.1]) and by minimality of S, we have |S| ≤ e + 1. But e + 1 equals the maximum number of affinely independent points in S, by definition of e. So |S| = e+1 and S is affinely independent. Therefore conv S is an e-simplex containing p.

Let S = {q_{0}, q_{1}, …, q_{e}} and S_{i} = S ∪ {p} \ {q_{i}}, for i = 0, 1, …, e. Then p = ∑_{i=0}^{e} λ_{i} q_{i} where

λ_{i} = \frac{e-vol(conv S_{i})}{e-vol(conv S)} , for i = 0, 1, …, e

(see, e.g., [11]). Since the volume of a simplex is a fraction of a determinant whose nonunit entries are the coordinates of its vertices, any simplex with rational vertices has rational volume. It follows that all the λ_{i} are rational.

Proof of Theorem 3: If H is empty then ≺_{H}^{+} is the empty relation and all four assertions are trivially true. Now assume that H is nonempty.

(i) ⇒ (ii) Let K = {x ∈ ℝ^{d}; x ≥ 0} ∩ conv H. Assume that K is nonempty. Then K is a convex polytope with rational vertices. Let q ∈ K ∩ ℚ^{d}. By Lemma 4, q is a rational convex combination of points from H. Let N be the least common denominator of the coefficients in this combination, and z = Nq. Then z ≥ 0 and z = ∑_{h∈H} μ_{h}h where μ_{h} ∈ ℕ are not all zero. Let s ∈ ℕ^{d} be such that s + H ⊆ ℕ^{d}. Then s + h ≺_{H} s for all h ∈ H. Let M = ∑_{h∈H} μ_{h}. By repeated application of Lemma 2, μ_{h}s + μ_{h}h ≺_{H}^{+} μ_{h}s for all h ∈ H, and Ms + z ≺_{H}^{+} Ms. Let z_{k} = Ms + k z. Note that z_{k} ∈ ℕ^{d} for all k ∈ ℕ. Using Lemma 2 it follows by induction on k that z_{k+1} ≺_{H}^{+} z_{k} for all k ∈ ℕ. Thus the z_{k} form an infinite descending chain in ℕ^{d}, contradicting the well-foundedness of ≺_{H}^{+}. Hence K = ∅.

(ii) ⇒ (iii) As {x ∈ ℝ^{d}; x ≥ 0} and conv H are disjoint convex polyhedra they can be separated by a hyperplane which meets neither of them. Therefore there are u ∈ ℝ^{d} \ {0} and b ∈ ℝ such that u · x < b for all x ∈ conv H and u · x > b for all x ≥ 0. In particular, u · h < b < 0 for all h ∈ H. If u_{i} < 0 for some i then x = (0, …, 0, b/u_{i}, 0, …, 0) ≥ 0 but u · x = b ≯ b. It follows that u ≥ 0.

As H is finite, and {w ∈ ℚ^{d} : w > 0} is dense in {u ∈ ℝ^{d} : u ≥ 0}, we can change u slightly into a vector w > 0 with rational coordinates, still satisfying w · h < 0 for all h ∈ H. Multiplying w by a suitable integer gives a vector v with positive integer coordinates satisfying v · h < 0 for all h ∈ H.

(iii) ⇒ (iv) Let v ∈ ℕ^{d}, v > 0, be such that v · h < 0 for all h ∈ H. Let L be any linear ordering of ℕ^{d} (e.g., the lexicographic one). Define a new linear ordering L_{v} of ℕ^{d} by

p L_{v} q ⟺ v · p < v · q or (v · p = v · q and p L q).

Note that the equation v · x = k has only finitely many solutions x ∈ ℕ^{d} for any k ∈ ℕ, because it implies that 0 ≤ x_{i} ≤ k/v_{i} for all i. Therefore L_{v} is of order type ω, and since p ≺_{H}^{+} q implies v · p < v · q, the dependency relation ≺_{H}^{+} can be embedded into L_{v}.

(iv) ⇒ (i) Any ordering of type ω is a well-ordering, therefore any transitive relation embeddable into it is well-founded.

Additional assertions equivalent to those in Theorem 3 are given in [19, Sec. 3.3, Cor. 2].

Now it is easy to state and prove an existence and uniqueness theorem for recurrences of the form (1) – (2).

Theorem 5 Let H ⊆ ℤ^{d} be a nonempty set which satisfies any of the equivalent conditions of Theorem 3. Then there exists a unique d-dimensional sequence a : ℕ^{d} → A which satisfies (1) – (2).

Proof: Write H = {h_{1}, h_{2}, …, h_{k}}. Theorem 3 implies the existence of a well-ordering <_{H} of ℕ^{d} of order type ω which extends the dependency relation ≺_{H}^{+}. Let p : ℕ → ℕ^{d} be a bijection satisfying

i < j ⟺ p_{i} <_{H} p_{j}.  (3)

The sequence (a_{n}) satisfies (1) and (2) if and only if the sequence f : ℕ → A defined by f(i) = a_{p_{i}} satisfies

f(i) = \{ \begin{matrix}Φ(f ∘ p^{−1}(p_{i} + h_{1}), f ∘ p^{−1}(p_{i} + h_{2}), …, f ∘ p^{−1}(p_{i} + h_{k})) & if p_{i} ≥ s, \\ φ(p_{i}) & if p_{i} ≱ s. \end{matrix}  (4)

We are going to prove, by induction on i, that (4) defines a unique sequence f(i). The unique solution of (1) – (2) can then be recovered from f using a_{n} = f ∘ p^{−1}(n).

Step 0. Let us show that Eqn. (4) completely defines f(0), by proving ab absurdo that p_{0} ≱ s. If p_{0} ≥ s, then p_{0} + H ⊆ ℕ^{d} (because s + H ⊆ ℕ^{d} by assumption). In other words, p_{0} + h_{j} ≺_{H} p_{0} and hence p_{0} + h_{j} <_{H} p_{0} for 1 ≤ j ≤ k. As H is nonempty and 0 ∉ H, this contradicts Property (3). Thus p_{0} ≱ s and Eqn. (4) determines f(0) = φ(p_{0}).

Step i, i > 0. Assume f(0), …, f(i−1) are determined uniquely by (4). If p_{i} ≱ s, then (4) forces f(i) = φ(p_{i}). Otherwise, for 1 ≤ j ≤ k, we have p_{i} + h_{j} ≺_{H} p_{i}, hence p_{i} + h_{j} <_{H} p_{i} and by (3), p^{−1}(p_{i} + h_{j}) < i. This means that the values of f ∘ p^{−1}(p_{i} + h_{j}) have already been computed, and f(i) is then uniquely determined by the first equation of (4).

This theorem generalizes the result of [23] where d = 2 and it is assumed that all h ∈ H satisfy h_{2} < 0, or h_{2} = 0 and h_{1} < 0.

Example 1 : The knight’s walk We study walks on the lattice ℕ^{2} that start anywhere on the lines x = 0, x = 1, y = 0, or y = 1, take only two kinds of steps: (−1, 2) and (2, −1), and remain in the region x ≥ 2, y ≥ 2 once they have left their starting point. For m, n ≥ 0, let a_{m,n} denote the number of such walks ending at (m, n). We have

a_{m,n} = \{ \begin{matrix}a_{m+1,n−2} + a_{m−2,n+1} & if m, n ≥ 2, \\ 1 & otherwise. \end{matrix}  (5)

This recurrence is of the form (1) – (2), with H = {(1, −2), (−2, 1)} and s = (2, 2). The conditions of Theorem 3 are satisfied: for example, if we take v = (1, 1) we have v · h < 0 for both h ∈ H. Hence the recurrence has a unique solution whose terms can be computed inductively, for instance diagonal by diagonal. The first few values are given in the following array.

n
↑
1 1 5 7 ⋯
1 1 3 5 10 14 ·
1 1 3 4 6 10 ·
1 1 2 2 4 5 7
1 1 2 2 3 3 5
1 1 1 1 1 1 1
1 1 1 1 1 1 1 → m
□

Our restriction to sequences defined in the first orthant might seem a serious limitation of applicability of our results. However, other wedge-like domains can be easily mapped onto the first orthant by a linear transformation, after which our approach applies. For example, if v_{1}, …, v_{d} ∈ ℤ^{d} are linearly independent vectors and C is the convex cone spanned by these vectors then an appropriate transformation could be multiplication by the integer matrix

M = det V · V^{−1}

where V = [v_{1}, …, v_{d}] is the matrix whose columns are the v_{i}’s. This transforms a recurrence equation in C, with the set of shifts {h_{1}, …, h_{k}}, into one in the first orthant, with the set of shifts {Mh_{1}, …, Mh_{k}}. A transformation of this type is used in Example 5 below. A similar (but slightly different) linear transformation is used in Example 4.

3 Linear recurrences with constant coefficients

In the rest of the paper, we focus our attention on multivariate linear recurrences. Let A be a field of characteristic zero. Let H be a finite nonempty subset of ℤ^{d} satisfying the condition

{x ∈ ℝ^{d}, x ≥ 0} ∩ conv H = ∅.  (6)

We study the recurrence relation

a_{n} = \{ \begin{matrix}∑_{h∈H} c_{h}a_{n+h} & for n ≥ s , \\ φ(n) & for n ≥ 0 and n ≱ s \end{matrix}  (7)

where (c_{h})_{h∈H} are given nonzero constants from A. The function φ provides the initial conditions, and we assume that

s ∈ ℕ^{d} and s + H ⊆ ℕ^{d}.  (8)

It is natural to ask how restrictive Condition (6) is. The following discussion suggests that the correct answer is: “not at all”. Let G be a finite nonempty subset of ℤ^{d}, and let us consider the linear relation

∑_{g∈G} b_{g}a_{n+g} = 0,

where the b_{g} are given nonzero constants from A. This relation can be written in |G| different ways in a form reminiscent of (7): For each g ∈ G,

a_{n} = − ∑_{g′∈G\\{g\}} \frac{b_{g}′}{b_{g}} a_{n+g′−g} = ∑_{h∈Hg} c_{h}a_{n+h}

with c_{h} = −b_{g}′/b_{g} and H_{g} = {g′ − g; g′ ∈ G, g′ ≠ g}. The following proposition implies that at least one of these relations will allow us to compute inductively the numbers a_{n}, starting from suitable initial conditions.

Proposition 6 Let G ⊆ ℤ^{d} be a nonempty finite set. There exists a point g ∈ G such that the set H_{g} = {g′ − g; g′ ∈ G, g′ ≠ g} satisfies the equivalent conditions of Theorem 3.

Proof: Let g be the largest point in G with respect to the lexicographic ordering of ℤ^{d}. That is, for all g′ ≠ g, there exists i ∈ {1, …, d} such that

g′_{1} = g_{1}, …, g′_{i−1} = g_{i−1}, and g′_{i} < g_{i}.  (9)

Then H_{g} satisfies the equivalent conditions of Theorem 3. Let us prove for instance the third one. Let

M = max_{{1≤j≤d \atop g′∈G}} |g′_{j} − g_{j}| .

Let v be the vector ((1 + M)^{d}, …, (1 + M)^{2}, (1 + M)). Let g′ ≠ g, and assume (9) holds. Then

v · (g′ − g) = ∑_{j=i}^{d} v_{j}(g′_{j} − g_{j}) ≤ −v_{i} + M ∑_{j=i+1}^{d} v_{j} = −(1 + M).

Observe that there can be several “good” choices of g. Take for instance the linear equation

a_{m,n} = a_{m,n+1} + a_{m+1,n}

where H = {(0, 1), (1, 0)} and the conditions of Theorem 3 are not satisfied. Both equivalent relations

a_{m,n} = a_{m,n−1} − a_{m+1,n−1} and a_{m,n} = a_{m−1,n} − a_{m−1,n+1}

do satisfy these conditions and hence allow an inductive evaluation of the sequence a_{m,n}. Note however that by (8), we need s ≥ (0, 1) in the former case and s ≥ (1, 0) in the latter. This means that different sets of initial values are required by these two relations: (a_{m,0})_{m≥0} by the former, and (a_{0,n})_{n≥0} by the latter.

We now prove an analyticity result.

Theorem 7 Take A = ℂ. Let (a_{n}) be the unique solution of (7). If there are constants m > 0 and u ∈ ℝ^{d} such that |φ(n)| ≤ m^{u·n} for all n ≱ s, then the generating function of (a_{n})

F (x) = ∑_{n≥0} a_{n}x^{n}

is analytic in a neighborhood of the origin.

Proof: By Theorem 3(iii), there exists v ∈ ℕ^{d} such that v > 0, and v · h < 0 for all h ∈ H. Since H is finite there exists an ε > 0 such that v · h ≤ −ε for all h ∈ H. Let

M = max \{1, ( ∑_{h∈H} |c_{h}|)^{\frac{1}{ε}} , max_{1≤i≤d} m^{\frac{u_{i}}{v_{i}}} \} .

We are going to prove that |a_{n}| ≤ M^{v·n} for all n ∈ ℕ^{d}, using induction on the well-founded set (ℕ^{d}, ≺_{H}^{+}).

If n ≱ s then

|a_{n}| = |φ(n)| ≤ m^{u·n} = m^{u_{1}n_{1}}m^{u_{2}n_{2}} ⋯ m^{u_{d}n_{d}}
= (m^{\frac{u_{1}}{v_{1}}} )^{v_{1}n_{1}} (m^{\frac{u_{2}}{v_{2}}} )^{v_{2}n_{2}} ⋯ (m^{\frac{u_{d}}{v_{d}}} )^{v_{d}n_{d}} ≤ M^{v·n}.

Otherwise we assume inductively that |a_{n+h}| ≤ M^{v·(n+h)} for all h ∈ H. Then

| ∑_{h∈H} c_{h}a_{n+h}| ≤ ∑_{h∈H} |c_{h}|M^{v·(n+h)} ≤ ∑_{h∈H} |c_{h}|M^{v·n−ε}
= M^{v·n−ε} ∑_{h∈H} |c_{h}| ≤ M^{v·n},

proving the claim. It follows that F (x_{1}, x_{2}, …, x_{d}) converges when |x_{i}| < 1/M^{v_{i}}.

4 The nature of the solution

Let a be the unique solution of the recursion (7). In this section we investigate the nature of the generating function

F_{s}(x) = ∑_{n≥s}a_{n}x^{n−s}.

Let us first recall a few definitions.

Definition 8 Let A be a field of characteristic zero. Let F (x) = ∑_{n≥0} a_{n}x^{n} be a formal power series in the variables x_{1}, x_{2}, …, x_{d} with coefficients in A. The series F is said to be

• rational if there exist polynomials P and Q in A[x_{1}, …, x_{d}] such that

F (x) = \frac{P (x)}{Q(x)};

• algebraic if there exists a nontrivial polynomial P in d + 1 variables, with coefficients

in A, such that

P (x_{1}, …, x_{d}, F (x)) = 0.

• D-finite if the partial derivatives ∂^{α}F/∂x^{α} of F, for α ∈ ℕ^{d}, span a finite-dimensional vector space over the field A(x_{1}, …, x_{d}); or, equivalently, if for 1 ≤ i ≤ d, a nontrivial linear differential equation of the form

P_{k}(x)\frac{∂^{k}F}{∂x_{i}^{k}} + ⋯ + P_{1}(x)\frac{∂F}{∂x_{i}} + P_{0}(x)F = 0

holds, where the polynomials P_{ℓ} have their coefficients in A.

The series F is transcendental if it is not algebraic. The coefficients of a D-finite series are said to be P-recursive.

For properties of D-finite series, see [22] for univariate series and [15] for the multivariate case. We shall clarify below the connection between our linearly recurrent sequences and P-recursiveness.

4.1 From the recurrence relation to a functional equation

Let us now transform our recurrence relation into a functional equation satisfied by the generating function F_{s}(x). Multiplying (7) by x^{n−s} and summing over all n ≥ s we obtain

F_{s}(x) = ∑_{h∈H} c_{h} ∑_{n≥s}a_{n+h}x^{n−s} = ∑_{h∈H} c_{h}x^{−h} ∑_{n≥s+h}a_{n}x^{n−s}
= ∑_{h∈H} c_{h}x^{−h}[F_{s}(x) + P_{h}(x) − M_{h}(x)]  (10)

where

P_{h}(x) = ∑_{{n≱s \atop n≥s+h}} a_{n}x^{n−s} = ∑_{{n≱s \atop n≥s+h}} φ(n)x^{n−s} and M_{h}(x) = ∑_{{n≥s \atop n≱s+h}} a_{n}x^{n−s}.  (11)

Note the simple relationship between F_{s}(x) and the full generating function F (x):

F (x) = ∑_{n≥0} a_{n}x^{n} = x^{s} ( ∑_{n≥s}a_{n}x^{n−s} + ∑_{{n≱s \atop n≥0}} a_{n}x^{n−s}) = x^{s}(F_{s}(x) + P_{−s}(x)).

Now rewrite (10) in the form

(1 − ∑_{h∈H} c_{h}x^{−h}) F_{s}(x) = ∑_{h∈H} c_{h}x^{−h}[P_{h}(x) − M_{h}(x)] .  (12)

To clear denominators on the left side of (12) we introduce the notion of apex which, as we will show shortly, is related to the nature of the generating function.

Definition 9 Let H ⊆ ℤ^{d} be a finite set. The apex of H is the point p = (p_{1}, p_{2}, …, p_{d}) ∈ ℕ^{d} defined by

p_{i} = max{h_{i} : h ∈ H ∪ {0}} (i = 1, 2, …, d).

In dimension 2, the apex of H is the upper right corner of the smallest rectangle (with its sides parallel to the axes) enclosing the set H ∪ {0}.

Multiplying (12) by x^{p} where p is the apex of H we obtain

Q(x)F_{s}(x) = K(x) − U(x)  (13)

where

Q(x) = x^{p} − ∑_{h∈H} c_{h}x^{p−h},  (14)
K(x) = ∑_{h∈H} c_{h}x^{p−h}P_{h}(x),  (15)
U(x) = ∑_{h∈H} c_{h}x^{p−h}M_{h}(x),  (16)

the series P_{h} and M_{h} being given by (11).

From the definition of the apex it follows that Q(x) is a polynomial in x called the characteristic polynomial or the kernel of the recursion. Note that the coefficients of Q(x) and K(x) are given directly by the coefficients of the recurrence relation and by the initial conditions, respectively. The coefficients of U(x) can of course be computed from (7) but are not given explicitly. Therefore we call K(x) the known initial function and U(x) the unknown initial function.

The functional equation (13) has a striking feature: on one hand, it is completely equivalent to our recurrence relation, and thus defines uniquely the numbers a_{n} for n ≥ s, and hence F_{s}(x). On the other hand, there seem to be not one, but two unknown functions in it: F_{s} and U. We shall show below on examples how to work with such apparently ambiguous functional equations. If U(x) can be found explicitly then the generating function of the unique solution to (7) is given by

F_{s}(x) = \frac{K(x) − U(x)}{Q(x)}.  (17)

Example 1 (continued): The knight’s walk Let us go back to the recurrence (5). We have s = (2, 2), H = {(1, −2), (−2, 1)} and the apex is p = (1, 1). Using (11) – (17) we find

F_{s}(x, y) = ∑_{m,n≥2} a_{m,n}x^{m−2}y^{n−2} = \frac{K(x, y) − U(x, y)}{Q(x, y)}

where

Q(x, y) = xy − x^{3} − y^{3},

the initial functions being

K(x, y) = y^{3} ∑_{m≥3} (a_{m,0}x^{m−2}y^{−2} + a_{m,1}x^{m−2}y^{−1}) + x^{3} ∑_{n≥3} (a_{0,n}x^{−2}y^{n−2} + a_{1,n}x^{−1}y^{n−2})

= xy (\frac{1 + y}{1 − x} + \frac{1 + x}{1 − y}) ,

U(x, y) = ∑_{n≥2} a_{2,n}y^{n+1} + ∑_{m≥2} a_{m,2}x^{m+1}.
□

The above example shows a strong connection between the nature of the series F_{s} and the nature of the unknown initial function U. We are now going to discuss this connection in full generality. We first need to define the sections of a formal power series.

Definition 10 Let F (x_{1}, …, x_{d}) = ∑_{n≥0} a_{n_{1},...,n_{d}}x^{n} be a formal power series in d variables. A section of F is any “sub-series” of F obtained by fixing some of the indices n_{i}. For instance,

∑_{n_{2},...,n_{d}≥0} a_{1998,n_{2},...,n_{d}}x_{2}^{n_{2}} ⋯ x_{d}^{n_{d}},

∑_{n_{2},n_{4},...,n_{d}≥0} a_{14,n_{2},4,n_{4},...,n_{d}}x_{2}^{n_{2}}x_{4}^{n_{4}} ⋯ x_{d}^{n_{d}},

are sections of F, as well as F itself and a_{2,4,6,...,2d}.

This terminology is due to Lipshitz. It is not difficult to prove that all sections of a rational (resp. algebraic, D-finite) series are also rational (resp. algebraic, D-finite). We refer to [15] for a proof in the D-finite case.

Proposition 11 Let F_{s}(x) be the generating function of the unique solution of (7). Then the series F_{s}(x) is rational (resp. algebraic, D-finite) if and only if both its known and unknown initial functions K(x) and U(x) are rational (resp. algebraic, D-finite).

Proof: If K and U are rational (resp. algebraic, D-finite), then (17) shows that F_{s} is also rational (resp. algebraic, D-finite): the three families of power series under consideration are closed under the sum and the product, and contain rational functions.

Conversely, observe that, for h ∈ H, the series M_{h}, defined by (11), and consequently the series U, are finite linear combinations of sections of F_{s}. Hence if F_{s} is rational (resp. algebraic, D-finite), then so is U(x). Eqn. (17) implies that the same holds for K(x).

Note. The series K(x) is a linear combination of sections of the full generating function F (x) = ∑_{n≥0} a_{n}x^{n}, but not of sections of F_{s}.

The above proposition tells us that determining the nature of F_{s} boils down to determining the nature of U (the nature of K is perfectly controlled because K is explicitly given). We give below examples of recurrence relations leading to rational, algebraic irrational, D-finite transcendental, and finally non-D-finite generating functions.

4.2 Rational solutions

Theorem 12 Assume the apex p of H is 0. Then the generating function F_{s}(x) of the unique solution of (7) is rational if and only if the known initial function K(x) itself is rational.

Proof: For each h ∈ H we have h ≤ 0, hence s+h ≤ s and M_{h}(x) = 0. Therefore U(x) = 0 and by (17),

F_{s}(x) = \frac{K(x)}{Q(x)}.  (18)

As Q(x) is a polynomial in x, it follows that F_{s}(x) is a rational function of x if and only if K(x) is.

Observe that when d = 1, we always have rational initial conditions and p = 0.

Note that any recurrence with constant coefficients – no matter what the apex – yields a rational generating function under special initial conditions. Assume A is algebraically closed, and take any u ∈ A^{d} such that ∑_{h∈H} c_{h}u^{h} = 1. Such a u always exists because H contains a nonzero point. Then a_{n} = u^{n} satisfies a_{n} = ∑_{h∈H} c_{h}a_{n+h} and the generating function F (x) = ∑_{n≥0} u^{n}x^{n} = ∏_{i=1}^{d}(1 − u_{i}x_{i})^{−1} is rational, as well as F_{s}.

4.3 Algebraic solutions

Theorem 13 Take A = ℂ and assume that the apex p of H has at most one positive coordinate. Then the generating function F_{s}(x) of the unique solution of (7) is algebraic if and only if the known initial function K(x) itself is algebraic.

Before we prove this theorem, let us first study a particular recurrence, which will illustrate the main ideas of the proof.

Example 2 : Dyck paths

For m, n ≥ 0, let a_{m,n} denote the number of paths on ℕ^{2} that start from the origin (0, 0), take only two kinds of steps: (1, 1) and (1, −1), and never touch the horizontal axis once they have left the origin. We are especially interested in paths that end on the line y = 1: we call them Dyck paths. We have

a_{m,n} = \{ \begin{matrix}a_{m−1,n−1} + a_{m−1,n+1} & if m, n ≥ 1, \\ δ_{(m,n),(0,0)} & if m = 0 or n = 0. \end{matrix}

This is a linear recurrence with constant coefficients, with H = {(−1, −1), (−1, 1)} and s = (1, 1). The apex is p = (0, 1). The first values of a_{m,n} are given below.

n
↑
0 0 0 0 0 0 1 0 6 0
0 0 0 0 0 1 0 5 0 20
0 0 0 0 1 0 4 0 14 0
0 0 0 1 0 3 0 9 0 28
0 0 1 0 2 0 5 0 14 0
0 1 0 1 0 2 0 5 0 14
1 0 0 0 0 0 0 0 0 0 → m

Using (11) – (17) we obtain:

F_{s}(x, y) = ∑_{m,n≥1} a_{m,n}x^{m−1}y^{n−1} = \frac{K(x, y) − U(x, y)}{Q(x, y)},

with

Q(x, y) = y − x − xy^{2},

the initial functions being

K(x, y) = y and U(x, y) = ∑_{m≥1} a_{m,1}x^{m} ≡ U(x).

In other words,

(y − x − xy^{2}) F_{s}(x, y) = y − U(x).  (19)

Observe that U(x) is the length generating function for Dyck paths. We are now going to use an idea that occurs in various places (e.g., [12, Ex. 2.2.1.4 and 2.2.1.11], [4], [17], [7], [2]) and is sometimes called the kernel method [1]: let ξ(x) be the formal power series in x defined by

Q(x, ξ(x)) = ξ(x) − x − xξ(x)^{2} = 0.

Replacing y by ξ(x) in (19) shows that

U(x) = ξ(x) = \frac{1 − \sqrt{1 − 4x^{2}}}{2x} ,

from which we can express F_{s}(x, y), which is also an algebraic function. □

We are now going to generalize the kernel method into a proof of Theorem 13.

Proof of Theorem 13: According to Proposition 11, if F_{s} is algebraic, then so is K. Let us prove that the converse is also true.

If p = 0, then the proof is similar to that of the previous theorem. Assume now that exactly one coordinate of p is positive. Without loss of generality, assume that p_{1} = ⋯ = p_{d−1} = 0 and p_{d} > 0. Then

\begin{aligned}U(x) & = & ∑_{h∈H} c_{h}x^{p−h} ∑_{{n≥s \atop n≱s+h}} a_{n}x^{n−s} \\ & = & ∑_{{h∈H \atop h_{d}>0}} c_{h}x^{p−h} ∑_{n_{d}=s_{d}}^{s_{d}+h_{d}−1} ∑_{{(n_{1},...,n_{d−1}) ≥ \atop (s_{1},...,s_{d−1})}} a_{n}x^{n−s}. \end{aligned}

This shows that U(x) is a polynomial in x_{d} of degree at most p_{d} −1. Our functional equation (13) reads

U(x) = K(x) − Q(x)F_{s}(x),  (20)

where

Q(x) = x_{d}^{p_{d}} − ∑_{h∈H} c_{h}x^{p−h}

is a polynomial whose degree in x_{d} is at least p_{d}. We shall prove that Q(x) regarded as a polynomial in x_{d} admits (at least) p_{d} roots ξ_{i}(x_{1}, …, x_{d−1}), counted with multiplicities, such that

ξ_{i}(0, …, 0) = 0.  (21)

Assuming for the moment that this is true, replacing x_{d} by ξ_{i}(x_{1}, …, x_{d−1}) in (20) tells us that^{1}, if ξ_{i} is a root of Q of multiplicity m, then

U(ξ_{i}) = K(ξ_{i}), U′(ξ_{i}) = K′(ξ_{i}), …, U^{(m−1)}(ξ_{i}) = K^{(m−1)}(ξ_{i}),

the derivatives being taken with respect to x_{d}. The p_{d} roots of Q thus provide a total of p_{d} equations for the polynomial U, of degree at most p_{d} − 1. We can then reconstruct U by means of the Hermite interpolation formula (see, e.g., [10, Sec. 6.1, Problem 10]), or, when Q has no double roots, by means of the well-known Lagrange interpolation formula. Because the ξ_{i}’s are algebraic functions of x_{1}, …, x_{d−1}, this shows that U(x) is algebraic provided K(x) is. The same holds for F_{s}(x).

1Condition (21) is required to make the substitution of ξ_{i} for x_{d} legitimate because as an equation between convergent power series, (20) is valid only in some neighbourhood of the origin.

To prove the existence of the roots ξ_{i}, let us observe that

Q(0, …, 0, x_{d}) = x_{d}^{p_{d}} − ∑_{{h∈H \atop h_{1}=···=h_{d−1}=0}} c_{h}x_{d}^{p_{d}−h_{d}}.

Because {x ∈ ℝ^{d}; x ≥ 0} ∩ H = ∅, we have h_{d} < 0 for all h ∈ H such that h_{1} = ⋯ = h_{d−1} = 0. Therefore p_{d} − h_{d} > p_{d} for all such h, which implies that x_{d} = 0 is a root of Q(0, …, 0, x_{d}) of multiplicity p_{d}. It follows that at least p_{d} of the roots of Q satisfy (21).

Remarks

1. The proof of Theorem 13 not only shows that under the stated conditions the generating functions of the solution are algebraic, but also provides an algorithm to compute them. They are given as rational expressions in the roots of the algebraic equation Q(x) = 0 and hence belong to an algebraic extension of ℂ(x). If the algebraic equations satisfied by the generating functions themselves are desired, they can be obtained by some routine resultant computations. However, in general the degree of these equations will be higher than the degree of Q in x_{d}.

2. It happens quite often, in recurrence relations coming from enumerative combinatorics, that the known initial function K(x) itself is a polynomial in x_{d}. In this case, the polynomial K − U has at least p_{d} roots (namely, ξ_{1}, …, ξ_{p_{d}}). The polynomial U having degree at most p_{d} − 1 (in x_{d}), this implies that K has degree at least p_{d}. If K has exactly degree p_{d}, then

K(x) − U(x) = lc (K) ∏_{i=1}^{p_{d}} (x_{d} − ξ_{i})

where lc (K) denotes the leading coefficient of K with respect to x_{d}, and Eqn. (20) implies that

F_{s}(x) = \frac{lc (K)}{Q(x)} ∏_{i=1}^{p_{d}} (x_{d} − ξ_{i}).  (22)

The degree of Q in x_{d} is p_{d} + r, where r = max{−h_{d}, h ∈ H ∪ {0}}. Assume Q factors as

Q(x) = lc (Q) ∏_{i=1}^{p_{d}} (x_{d} − ξ_{i}) ∏_{i=1}^{r} (x_{d} − μ_{i}).

Then we can rewrite the series F_{s} as

F_{s}(x) = \frac{lc (K)}{lc (Q)} ∏_{i=1}^{r} \frac{1}{x_{d} − μ_{i}} .  (23)

Eqns. (22) and (23) show that the two cases p_{d} = 1 and r = 1, corresponding respectively to max h_{d} = 1 and min h_{d} = −1, are especially favourable. In both cases, the series F_{s}(x) is, up to an explicit rational-function factor, equal to (x_{d} − χ)^{±1}, where χ is a solution of Q(x_{1}, …, x_{d−1}, χ) = 0. In this case, we can write immediately the algebraic equation satisfied by F_{s}(x). Examples will be given below.

Example 3 : Generalized Dyck paths

In the problem of generalized Dyck paths [14, 13, 5], we are given a finite set of steps S = {(r_{1}, s_{1}), …, (r_{k}, s_{k})} where r_{i}, s_{i} ∈ ℤ and r_{i} > 0. Let b_{m,n} denote the number of paths going from (0, 0) to (m, n), using only steps from S and staying within the first quadrant. We are mainly interested in the numbers b_{m,0} ≡ b_{m}. Obviously, the numbers b_{m,n} satisfy

b_{m,n} = \{ \begin{matrix}∑_{i: (r_{i},s_{i})≤(m,n)} b_{m−r_{i},n−s_{i}} & if m, n ≥ 0 and (m, n) ≠ (0, 0), \\ 1 & if m = n = 0. \end{matrix}

This does not fit (7), but can be easily brought into the desired form. Let r = max_{1≤i≤k} r_{i} and s = max_{1≤i≤k} s_{i}. Attach r columns of zeros to the left of the array b, and s rows of zeros below. Call the resulting array a and number its rows and columns starting with 0. Then

b_{m,n} = a_{m+r,n+s} for m, n ≥ 0.

Let (ρ, σ) be any step in S which is maximal with respect to the partial order ≤ (e.g., the lexicographically largest step). If a_{r−ρ,s−σ} is reset to 1 then a satisfies

a_{m,n} = \{ \begin{matrix}a_{m−r_{1},n−s_{1}} + ⋯ + a_{m−r_{k},n−s_{k}} & if m ≥ r and n ≥ s, \\ δ_{(m,n),(r−ρ,s−σ)} & if m < r or n < s. \end{matrix}

This clearly fits (7) with H = {(−r_{1}, −s_{1}), …, (−r_{k}, −s_{k})}, s = (r, s), and c_{h} = 1 for all h ∈ H. From the fact that r_{i} > 0, it follows that {x ∈ ℝ^{d}; x ≥ 0} ∩ conv H = ∅. Hence the conditions of Theorem 3 are satisfied. The apex of H is p = (0, max{0, t}) with t = − min{s_{1}, …, s_{k}}. We distinguish two cases.

• If s_{i} ≥ 0 for all i, then the apex is (0, 0). We can use formula (18) with Q(x, y) = 1 − x^{r_{1}}y^{s_{1}} − ⋯ − x^{r_{k}}y^{s_{k}} and K(x, y) = 1. We obtain the rational (and expected!) generating function

G(x, y) = ∑_{m,n≥0} b_{m,n}x^{m}y^{n} = ∑_{{m≥r \atop n≥s}} a_{m,n}x^{m−r}y^{n−s} = F_{s}(x, y) = \frac{1}{1 − x^{r_{1}}y^{s_{1}} − ⋯ − x^{r_{k}}y^{s_{k}}} .

The generating function for paths ending on the horizontal axis is

g(x) = ∑_{m≥0} b_{m}x^{m} = G(x, 0) = \frac{1}{1 − ∑_{{1≤i≤k \atop s_{i}=0}} x^{r_{i}}} .

• If there exists i such that s_{i} < 0, then the apex of H is (0, t) with t > 0, and the corresponding generating functions are algebraic. Using (11) – (15) we find

Q(x, y) = y^{t} − x^{r_{1}}y^{s_{1}+t} − ⋯ − x^{r_{k}}y^{s_{k}+t}, K(x, y) = y^{t}.

We are now in the framework described in the second remark that follows the proof of Theorem 13. The polynomial Q has degree t + s in y, with leading coefficient − ∑_{i: s_{i}=s} x^{r_{i}}.

(We assume s > 0 to avoid trivial cases.) Let ξ_{1}(x), …, ξ_{t}(x) be t solutions of Q(x, ξ(x)) = 0 satisfying ξ(0) = 0. Let μ_{1}(x), …, μ_{s}(x) be the s remaining solutions. We find explicit expressions for the desired series:

G(x, y) = ∑_{m,n≥0} b_{m,n}x^{m}y^{n} = F_{s}(x, y) = \frac{1}{Q(x, y)} ∏_{i=1}^{t} (y − ξ_{i}(x)) = −\frac{1}{∑_{i:s_{i}=s} x^{r_{i}}} ∏_{i=1}^{s} \frac{1}{y − μ_{i}(x)}

(24)

and

g(x) = ∑_{m≥0} b_{m}x^{m} = G(x, 0) = \frac{(−1)^{t}}{Q(x, 0)} ∏_{i=1}^{t} ξ_{i}(x) = \frac{(−1)^{s+1}}{∑_{i:s_{i}=s} x^{r_{i}}} ∏_{i=1}^{s} \frac{1}{μ_{i}(x)}.  (25)

An alternative solution to this problem is given in [5] in terms of a system of algebraic equations defining g(x).

As indicated in the remark above, two particular cases happen to be especially simple (and combinatorially equivalent, as far as g(x) is concerned). If t = 1, i.e., min s_{i} = −1, we find g(x) = −ξ_{1}(x)/Q(x, 0), so that the algebraic equation satisfied by g is

Q (x, g(x) ∑_{i: s_{i}=−1} x^{r_{i}}) = 0.

In other words, denoting = g(x) ∑_{i: s_{i}=−1} x^{r_{i}}:

ĝ − ∑_{i=1}^{k} x^{r_{i}}ĝ^{s_{i}+1} = 0.  (26)

If s = 1, i.e., max s_{i} = 1, we find g(x) = (μ_{1}(x) ∑_{i: s_{i}=1} x^{r_{i}})^{−1}, so that a similar algebraic equation holds:

Q (x, \frac{1}{g(x) ∑_{i: s_{i}=1} x^{r_{i}}} ) = 0.

In other words, denoting g̃(x) = g(x) ∑_{i: s_{i}=1} x^{r_{i}}, and after a multiplication by g̃^{t+1}:

g̃ − ∑_{i=1}^{k} x^{r_{i}}g̃^{1−s_{i}} = 0.  (27)

The transformation (r_{i}, s_{i}) ⟶ (r_{i}, −s_{i}), which boils down to reading the paths from right to left, shows the combinatorial equivalence between the two problems, reflected by Eqns.

(26) – (27).

As special cases, this example includes some well-known lattice-path enumeration problems. For instance, these paths are called:

• Dyck paths, if S = {(1, −1), (1, 1)}. In this case, Q(x, y) = y − xy^{2} − x, and from (25),

g(x) = \frac{1 − \sqrt{1 − 4x^{2}}}{2x^{2}} .

• Motzkin paths, if S = {(1, −1), (1, 1), (1, 0)}. In this case, Q(x, y) = y − xy^{2} − x − xy, and from (25),

g(x) = \frac{1 − x − \sqrt{1 − 2x − 3x^{2}}}{2x^{2}} .

• Schröder paths, if S = {(1, −1), (1, 1), (2, 0)}. In this case, Q(x, y) = y − xy^{2} − x − x^{2}y, and from (25),

g(x) = \frac{1 − x^{2} − \sqrt{1 − 6x^{2} + x^{4}}}{2x^{2}} .

In the same way we could count generalized Dyck paths with coloured steps – then the corresponding coefficient c_{h} would equal the number of colours available for step h. This approach generalizes without significant change to higher-dimensional paths if the steps have positive coordinates in all but perhaps one (fixed) dimension. In all these cases, the generating functions are algebraic. □

The next example is actually an application of the previous one.

Example 4 : Directed paths above a line of rational slope

Let p and q be positive integers. Consider the problem of counting lattice paths with steps (1, 0) and (0, 1) which start at the origin and stay on or above the line qy = px. Using the linear transformation L : (i, j) ↦ (i + j, qj − pi) we obtain the equivalent problem of counting lattice paths with steps (1, −p) and (1, q) which start at the origin and stay within the first quadrant. This is because L maps the “forbidden” region below the line qy = px into the region below the line y = 0. We are thus back to Example 3, with S = {(1, −p), (1, q)}. The apex is p = (0, p) and we are in the algebraic case, with t = p and s = q. We have Q(x, y) = y^{p} − xy^{p+q} − x and the relevant generating functions can be derived from (24) and (25):

G(x, y) = \frac{1}{y^{p} − xy^{p+q} − x} ∏_{i=1}^{p} (y − ξ_{i}(x)) = −\frac{1}{x} ∏_{i=1}^{q} \frac{1}{y − μ_{i}(x)},

g(x) = \frac{(−1)^{p+1}}{x} ∏_{i=1}^{p} ξ_{i}(x) = \frac{(−1)^{q+1}}{x} ∏_{i=1}^{q} \frac{1}{μ_{i}(x)}.

The series G and g can be understood in terms of the original paths (with unit steps) as follows: G(x, y) counts these paths according to their length (variable x) and an additional statistics that describes some kind of “distance” between the endpoint of the path and the line px = qy. The series g(x) is the length generating function for paths ending on that line.

The cases p = 1 and q = 1 are especially simple; moreover, they are equivalent, as far as the evaluation of g(x) is concerned. If, for instance, p = 1, then g(x) = ξ(x)/x where ξ(x) is the unique power-series solution of

ξ = x (1 + ξ^{q+1}) .

The Lagrange inversion formula gives then

g(x) = ∑_{n≥0} b_{n}x^{n} = ∑_{m≥0} \frac{x^{m(q+1)}}{1 + mq} \binom{m(q + 1)}{m}.

Note that b_{m(q+1)} equals the number of paths from the origin to the point (mq, m) in our original problem. We have thus recovered a classical result (e.g. [6, Thm. 2]).

By changing the initial conditions, we could count the paths that start at the origin and stay above the line px = qy (if q = 1, then this question is equivalent to the initial one; for the case p = 1, see [9, Theorem 5.5]). Instead of the steps (1, 0) and (0, 1) we could take any set of steps with nonnegative components, and still obtain algebraic generating functions. □

4.4 D-finite transcendental solutions

According to the two previous subsections, the solution of (7) can only be transcendental if the apex p has more than one positive coordinate (unless of course the known initial function K(x) is already transcendental).

Example 5 : Ballot problems, Young tableaux and involutions avoiding long increasing subsequences

In an election, d candidates C_{1}, …, C_{d} receive respectively m_{1}, …, m_{d} votes, with m_{1} ≥ ⋯ ≥ m_{d} ≥ 0. The problem is to determine the number b_{m} of ways one can count the votes so that at any stage, C_{i} has at least as many votes as C_{i+1}, for 1 ≤ i < d.

Clearly, such counting processes can be encoded by paths on the lattice ℕ^{d} that start from the origin 0, end at m, take unit steps in the d positive directions, and have all their vertices in the wedge x_{1} ≥ x_{2} ≥ ⋯ ≥ x_{d} ≥ 0.

These paths are known to encode Young tableaux of height at most d: a step of the path going in the ith direction means that an entry is added to the ith row of the tableau (Figure 1). Equivalently, via the Robinson-Schensted correspondence, these paths encode involutions of the symmetric group S_{n} that avoid the pattern 123 … (d + 1), i.e., have no increasing sub-sequence of length > d.

Figure 1: A Young tableau of height 4 and the word – or path – that encodes it (a letter i in the word indicates that the path takes a step in the ith direction).

The numbers b_{m}, for m ∈ ℤ^{d}, satisfy:

b_{m} = \{ \begin{matrix}∑_{i=1}^{d} b_{m−e_{i}} & if m_{1} ≥ ⋯ ≥ m_{d} ≥ 0 and m ≠ 0, \\ δ_{m,0} & otherwise \end{matrix}

where e_{i} denotes the unit vector (0, …, 0, 1, 0, …, 0) with the 1 in ith position. We can transform this recurrence into a recurrence of type (7) by setting

a_{n} = b_{n_{1}+n_{2}+···+n_{d}−d,...,n_{d−1}+n_{d}−2,n_{d}−1},

except for the value a_{0,1,...,1} which we find convenient to reset to 1. Then for n ≥ 0,

a_{n} = \{ \begin{matrix}∑_{h∈H} a_{n+h} & if n ≥ 1, \\ δ_{n,(0,1,...,1)} & otherwise \end{matrix}

where

H = {(−1, 0, …, 0), (1, −1, 0, …, 0), (0, 1, −1, 0, …, 0), …, (0, …, 0, 1, −1)}.

The set H satisfies Theorem 3(iii) with v = (1, 2, …, d), and thus the recurrence defines a unique sequence. The apex is (1, 1, …, 1, 0).

Proposition 14 The generating function F_{1}(x) = ∑_{n≥1} a_{n}x^{n−1} is D-finite for all d. It is rational if d = 1, algebraic of degree 2 (quadratic) if d = 2, and transcendental if d ≥ 3.

Proof: This ballot problem was solved by MacMahon [18, Sec.III, Chap.V, 103]:

b_{m} = ∏_{1≤i<j≤d}(m_{i} − m_{j} + j − i) \frac{(∑_{i=1}^{d} m_{i})!}{∏_{i=1}^{d} (m_{i} + d − i)!}.

This gives, for n ≥ 1,

a_{n} = ∏_{1≤i<j≤d}(n_{i} + ⋯ + n_{j−1}) \frac{(∑_{i=1}^{d} in_{i} − \binom{d+1}{2})!}{∏_{i=1}^{d} (n_{i} + ⋯ + n_{d} − 1)!}.

We prove that this d-dimensional sequence is P-recursive by combining the P-recursiveness of some elementary sequences with the fact that the class of P-recursive sequences is closed under the Hadamard product (see [15] for details). Hence F_{1} is D-finite.

Now, if F_{1}(x) is algebraic, then so is its section

f(z) = ∑_{n≥1} a_{1,...,1,n} z^{n} = ∑_{n≥1} b_{n−1,...,n−1} z^{n},

corresponding to Young tableaux of rectangular shape. But

a_{1,...,1,n+1} = ∏_{i=1}^{d−1} i^{d−i} \frac{(dn)!}{∏_{i=0}^{d−1}(n + i)!} ∼ ∏_{i=1}^{d−1} i^{d−i} \frac{\sqrt{d}}{(2π)^{(d−1)/2}} · \frac{d^{dn}}{n^{(d^{2}−1)/2}}

by Stirling’s formula. For f(z) to be algebraic, it is necessary (see [8, Thm. D]) that

\frac{d^{2} − 1}{2} ∉ \{1, 2, 3, …\},

which rules out all odd values of d, except d = 1, and that

∏_{i=1}^{d−1} i^{d−i} \frac{\sqrt{d}}{(2π)^{(d−1)/2}} · Γ (\frac{3 − d^{2}}{2} )

be an algebraic number. If d is even, then Γ (\frac{3−d^{2}}{2} ) is, up to a rational factor, equal to Γ(1/2) = \sqrt{π}. The above condition reads “π^{d/2−1} is algebraic”, and forces d = 2. Thus F_{1} is transcendental when d ≥ 3.

If d = 1, then a_{n_{1}} = 1 for n_{1} ≥ 1. Hence F_{1} = 1/(1 − x_{1}) is rational.

If d = 2, then the apex is (1, 0) and the known initial function is rational. We apply the technique of Section 4.3 to obtain

F_{1}(x_{1}, x_{2}) = \frac{1}{2} \frac{2x_{1} − 1 + \sqrt{1 − 4x_{2}}}{x_{1} − x_{1}^{2} − x_{2}} .

Note that this calculation is completely equivalent to that of Example 2, as ballot paths are merely left factors of Dyck paths.

4.5 Non-D-finite (hypertranscendental) solutions

Our last example is a variation on the knight’s walk (Example 1). It shows that the solution of (7) need not be D-finite, even though the initial conditions are rational.

Example 6 Let (a_{m,n})_{m,n≥0} be the sequence defined by:

a_{m,n} = \{ \begin{matrix}a_{m+1,n−2} + a_{m−2,n+1} − a_{m−1,n−1} & if m, n ≥ 2, \\ −δ_{(m,n),(1,1)} & if m ≤ 1 or n ≤ 1. \end{matrix}

The first few values of a_{m,n} are given below.

n
↑
0 0 0 0 ⋯
0 0 −1 0 0 1 ·
0 0 0 0 −1 0 ·
0 0 0 −1 0 0 0
0 0 1 0 0 −1 0
0 −1 0 0 0 0 0
0 0 0 0 0 0 0 → m

This is a problem of type (7) with H = {(1, −2), (−2, 1), (−1, −1)}, s = (2, 2), and p = (1, 1). We find, using (11) – (17)

Q(x, y) = (x − y^{2})(y − x^{2}), K(x, y) = xy, and U(x, y) = G(x) + G(y)

with

G(x) = ∑_{m≥2} a_{m,2}x^{m+1}.

We have used the symmetry of the problem in m and n. As usual, let F_{s}(x, y) = ∑_{m,n≥2} a_{m,n}x^{m−2}y^{n−2}. Then we have from (13)

[x − y^{2}] [y − x^{2}] F_{s}(x, y) = xy − G(x) − G(y).  (28)

Replacing y by x^{2} in (28), we obtain the following equation defining G:

x^{3} − G(x) − G (x^{2}) = 0,

Iterating this equation shows that, for n ≥ 1,

G(x) = ∑_{i=0}^{n−1}(−1)^{i}x^{3·2^{i}} + (−1)^{n}G (x^{2^{n}}) .

By definition, G(x) = O(x^{3}), and therefore

G(x) = ∑_{i≥0}(−1)^{i}x^{3·2^{i}}.

The series G is a lacunary series; in particular, its coefficients c_{n} do not satisfy any non-trivial recurrence relation of the type

P_{0}(n)c_{n} + P_{1}(n)c_{n−1} + ⋯ + P_{k}(n)c_{n−k} = 0,

where the P_{i}(n) are polynomials in n. Such recurrence relations characterize D-finite series: hence G(x) cannot be D-finite. Consequently, the series F_{s}(x, y) itself is not D-finite.

We can actually state a stronger result: according to [16, Thm. 4], the series G is hypertranscendental, meaning that it does not satisfy any algebraic differential equation of the form

P (x, G(x), G′(x), G′′(x), …, G^{(k)}(x)) = 0

where P is a polynomial with complex coefficients of k + 2 variables.

The numbers a_{m,n} actually belong to {0, −1, 1} and we could write down an explicit expression for them. But the following table, where the zero entries are replaced by dots and the nonzero entries are replaced by their signs, shows the underlying lozenge pattern and makes a long formula short.

n
↑
⋯ − · · − · · − · · · · · + · · +
· · · · · · − · · − · · − · · · · · + ·
· · · · · − · · − · · − · · − · · + · ·
· · · · · · · − · · − · · − · · − · · +
· · · · · · − · · − · · − · · − ⋯
· · · · · · · · − · · − · · − · · − · ·
· · · · · · · − · · − · · − · · − ⋯
· · · · · · · · · − · · − · · − · · − ·
· · + · · · · · − · · − · · − · · − · ·
⋯ + · · · · · − · · − · · − · · −
⋯ + · · + · · − · · − · · − · · − ·
· · · · · + · · + · · − · · − · · − · ·
⋯ + · · + · · · · · − · · − · · −
· · · · · · + · · + · · · · · − · · − ·
· · − · · + · · + · · · · · · · · − · ·
⋯ − · · + · · + · · · · · · · · −
⋯ − · · · · · + · · · · · · · · · ·
· · + · · − · · · · · + · · · · · · · ·
· − · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · → m
□

Example 1 (continued): what about the knight? Let us recall the functional equation we have obtained for this problem:

[xy − x^{3} − y^{3}]F_{s}(x, y) = K(x, y) − G(x) − G(y)  (29)

where

K(x, y) = xy (\frac{1 + y}{1 − x} + \frac{1 + x}{1 − y}) and G(x) = ∑_{m≥2} a_{m,2}x^{m+1}.

We have used the symmetry of the problem in m and n. We are going to show that the kernel method allows once again to solve completely this functional equation. Let ξ(x) = O(x^{2}) be the formal power series in x satisfying

xξ − x^{3} − ξ^{3} = 0.

The Lagrange inversion formula, applied to ξ(x)/x, provides an explicit expression:

ξ(x) = x^{2} ∑_{m≥0} \frac{x^{3m}}{2m + 1}\binom{3m}{m} = O(x^{2}).

Replacing y by ξ(x) in (29) gives a functional equation that defines G(x):

K(x, ξ(x)) − G(x) − G(ξ(x)) = 0.

As G(x) = O(x^{2}), we obtain, after iterating this equation infinitely many times

G(x) = ∑_{i≥0}(−1)^{i}K [ξ^{(i)}(x), ξ^{(i+1)}(x)]

where ξ^{(i)} = ξ ∘ ⋯ ∘ ξ is the ith iterate of ξ. Replacing G(x) by the above explicit value in (29) gives an expression for F_{s}. It has been proved that G is irrational [20]. It is in fact not D-finite [3]. □

Final remarks

1. The approach of this paper can be generalized without any significant alteration to recurrence relations involving an inhomogeneous term:

a_{n} = ∑_{h∈H} c_{h}a_{n+h} + b_{n},

where (b_{n})_{n≥s} is a given d-dimensional sequence in the field A. The inhomogeneous term only affects the known initial function K(x), which becomes

K(x) = ∑_{h∈H} c_{h}x^{p−h}P_{h}(x) + B(x), with B(x) = ∑_{n≥s}b_{n}x^{n−s}.

2. Some of the results and techniques presented in this paper do not require H to be a finite set. If H is infinite, the initial conditions have to include a_{n} = 0 for n ≱ 0.

3. We used the kernel method to prove Proposition 13 and solve Examples 6 and 1. More examples suggest that the roots of the kernel will always provide enough information on the unknown initial function U(x) to characterize it completely, thus yielding some kind of solution of the recursion; this could, at least in the two-dimensional case, allow for a complete classification of the recursions according to the nature of the associated generating function.

Acknowledgements. The authors wish to express their thanks to Ira Gessel for providing the basis of Example 5, as well as several useful references.

References

[1] C. Banderier, Combinatoire analytique : application aux marches aléatoires, Mémoire de DEA, INRIA Rocquencourt, June 1998.

[2] M. Bousquet-Mélou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1996) 1–25.

[3] M. Bousquet-Mélou and M. Petkovšek, in preparation.

[4] R. Cori and J. Richard, Énumération des graphes planaires à l’aide des séries formelles en variables non commutatives, Discrete Math. 2 No.2 (1972) 115–162.

[5] P. Duchon, On the enumeration and generation of generalized Dyck words, Discrete Math., this volume.

[6] A. Dvoretzky and Th. Motzkin, A problem of arrangements, Duke Math. J. 14 (1947) 305–313.

[7] S. Feretić and D. Svrtan, On the number of column-convex polyominoes with given perimeter and number of columns, in: Proceedings of the 5^{th} Conference “Formal Power Series and Algebraic Combinatorics”, Florence, June 1993, pp. 201–214.

[8] P. Flajolet, Analytic models and ambiguity of context-free languages, Theoret. Comput. Sci. 49 (1987) 283–309.

[9] I. M. Gessel, A factorization for formal Laurent series and lattice path enumeration, J. Combin. Theory. Ser. A 28 (1980) 321–337.

[10] E. Isaacson and H. B. Keller, Analysis of Numerical Methods, John Wiley and Sons, New York, 1966.

[11] M. G. Kendall, A Course in the Geometry of n Dimensions, Hafner Publ. Co., New York, 1961.

[12] D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading Mass., 1968.

[13] J. Labelle, Langages de Dyck généralisés, Ann. Sci. Math. Québec 17 (1993) 53–64.

[14] J. Labelle and Y.-N. Yeh, Generalized Dyck paths, Discrete Math. 82 (1990) 1–6.

[15] L. Lipshitz, D-finite power series, J. Algebra 122 (1989) 353–373.

[16] J. H. Loxton and A. J. van der Poorten, A class of hypertranscendental functions, Aequationes Math. 16 (1977) 93–106.

[17] P. Luksch and M. Petkovšek, An explicit formula for |F M(1 + 1 + n)|, Order 6 (1990) 319–324.

[18] P. A. MacMahon, Combinatory analysis, 2 vols., Cambridge University Press, Cambridge, 1915–1916 (Reprinted: Chelsea, New-York, 1960).

[19] M. Petkovšek, Finding closed-form solutions of difference equations by symbolic methods, Ph.D. Thesis, Carnegie Mellon University, Pittsburgh PA, 1991 (CMU-CS-91-103).

[20] M. Petkovšek, The irrational chess knight, in: Proceedings of the 10^{th} Conference “Formal Power Series and Algebraic Combinatorics”, pp. 513–522, Toronto, June 1998.

[21] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton NJ, 1970.

[22] R. P. Stanley, Differentiably finite power series, European J. Combin. 1 (1980) 175–188.

[23] R. Suarez, Difference equations and a principle of double induction, Math. Magazine 62 (1989) 334–339.