The Irrational Chess Knight

Marko Petkovšek

Department of Mathematics University of Ljubljana Jadranska 19, 1000 Ljubljana, Slovenia E-mail: Marko.Petkovsek@fmf.uni-lj.si Fax: +386 61 217-281 Phone: +386 61 1766-680

Summary

While in the univariate case solutions of linear recurrences with constant coefficients have rational generating functions, in the multivariate case the situation is much more interesting: even though initial conditions have rational generating functions, the corresponding solutions can have generating functions which are algebraic but not rational, and perhaps even non-algebraic.

We start by an existence and uniqueness theorem for partial recurrences of the 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 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. This condition on H which ensures existence and uniqueness of solution is assumed to be satisfied in the sequel.

For linear partial 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. Next we consider the algebraic nature of the generating function of the solution of such recurrences, and 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 is 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 can be found by solving an algebraic equation and a system of linear equations. We give several applications of this procedure to enumeration of various lattice paths with algebraic generating functions such as generalized Dyck paths and paths consisting of nonnegative steps and staying below a certain line.

Finally, 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 rational, which we demonstrate on the problem of the chess knight with restricted moves. We also conjecture that in this case the generating function is not even algebraic.

Résumé

Alors que dans le cas d’une seule variable les séries génératrices des solutions des équations de récurrences linéaires à coefficients constants sont rationnelles, dans le cas de plusieurs variables ces séries peuvent être algébriques non-rationnelles, ou pas même algébriques.

Nous commençons par donner un théorème d’existence et d’unicité pour des récurrences partielles ayant la forme

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

où les valeurs a_{n} pour n ≱ s sont connues. Nous montrons qu’il existe une énumération des points entiers naturels, telle que pour tout n les points n + h_{i} précèdent n dans cette énumération si et seulement si l’intersection de l’enveloppe convexe de H = {h_{1}, h_{2}, …, h_{k}} avec le premier orthant est vide. Nous supposons que cette condition pour H qu’implique l’existence et l’unicité de la solution est satisfaite par toutes les récurrences que nous considérons.

Pour des récurrences partielles linéaires à coefficients constants nous montrons que la solution est analytique dans un voisinage de l’origine si les conditions initiales sont bornées par une fonction exponentielle de n. Nous appelons l’apex de H le maximum des points de H ∪ {0} calculé par coordonnées. Si les séries génératrices des conditions initiales sont rationnelles et l’apex de H est 0, la série génératrice de la solution est rationnelle et peut être calculée par une formule explicite. Si les séries génératrices des conditions initiales sont algébriques et l’apex de H a une coordonnée positive au plus, la série génératrice de la solution est algébrique. Pour la trouver on doit résoudre une équation algébrique et un système d’équations linéaires.

Enfin, si l’apex de H a plus d’une coordonnée positive et les séries génératrices des conditions initiales sont rationnelles, la série génératrice de la solution n’est pas necéssairement rationnelle. Nous présentons un exemple de ce type provenant du “problème de cavalier”. Nous conjecturons que dans ce cas-là, la série génératrice n’est pas même algébrique.

1 An existence and uniqueness theorem

Throughout the paper, we use IN to denote the set of nonnegative integers. We write u = (u_{1}, u_{2}, …, u_{d}) for d-tuples of numbers or indeterminates, and u ≥ v when u_{i} ≥ v_{i} for 1 ≤ i ≤ d.

Let A be a nonempty set. We consider d-dimensional partial 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 : IN^{d} → A is the unknown d-dimensional sequence (d-sequence for short) of elements of A, Φ : A^{k} → A is a given function, H = {h_{1}, h_{2}, …, h_{k}} ⊆ ZZ^{d} is the set of shifts, and s ∈ IN^{d} is the starting point satisfying s + H ⊆ IN^{d}. We assume that the initial conditions are of the form

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

where φ : {n ∈ IN^{d}; n ≱ s} → A is a given function.

We think of the h_{i} as having mostly 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 a well-ordering of IN^{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 a_{n} of (1), (2), and for any n ∈ IN^{d} it is possible to compute the value of a_{n} directly from (1), (2) in a finite number of steps.

Definition 1 For H ⊆ ZZ^{d} and p, q ∈ IN^{d}, let

p ≺_{H} q iff p ∈ q + H ⊆ IN^{d} .  (3)

The transitive closure ≺_{H}^{+} of ≺_{H} in IN^{d} is the dependency relation corresponding to H. When p ≺_{H}^{+} q we say that q depends on p. □

For a set H ⊆ IR^{d} we denote by conv H its convex hull, and by i-cone H its integer cone:

i-cone H = {x ∈ IR^{d}; x = ∑_{i=0}^{k} λ_{i} h_{i}, λ_{i} ∈ IN, h_{i} ∈ H} .

The following theorem is proved in [7, Sec. 3.3, Cor. 2]:

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

(i) ≺_{H}^{+} is asymmetric and has no infinite descending chain in IN^{d},

(ii) {x ∈ IR^{d}; x ≥ 0} ∩ i-cone H = ∅,

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

(iv) there exists an a ∈ IR^{d}, a > 0, such that a · h < 0 for all h ∈ H,

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

(vi) ≺_{H}^{+} can be extended to a well-ordering of IN^{d} of order type ω. □

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

Theorem 2 Let H ⊆ ZZ^{d} \ {0} be a nonempty set such that {x ∈ IR^{d}; x ≥ 0} ∩ conv H = ∅. Then there exists a unique d-sequence a : IN^{d} → A which satisfies (1), (2).

Proof: Write H = {h_{1}, h_{2}, …, h_{k}}. To prove existence, note that by Theorem 1 there exists a wellordering <_{H} of IN^{d} of order type ω which extends ≺_{H}^{+}. Let p : IN → IN^{d} be a bijection which satisfies i < j ⇔ p_{i} <_{H} p_{j}. Such a bijection exists because <_{H} has order type ω. Define a function f : IN → A recursively by f(0) = φ(p_{0}) and

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}) , & otherwise, \end{matrix}

for i > 0. As H is nonempty and 0 ∉ H, we have p_{0} ≱ s. Because p_{i} + h_{j} ≺_{H}^{+} p_{i} it follows that p^{−1}(p_{i} + h_{j}) < i so that f(i) is defined in terms of values of f at smaller arguments when p_{i} ≥ s. We conclude that f is well defined. Obviously a_{n} = f(p^{−1}(n)) satisfies (1) and (2). Uniqueness of this solution follows easily by induction on the well-founded set (IN^{d}, ≺_{H}^{+}). □

This theorem generalizes the result of [10].

2 Partial recurrences with constant coefficients

In the rest of the paper, we limit our attention to recurrences of the form

a_{n} = ∑_{h∈H} c_{h}a_{n+h} , for n ≥ s ,  (4)

where the set of values A is a field of characteristic zero, and c_{h} are given nonzero constants from A.

Theorem 3 Take A = C^{|}, and let H ⊆ ZZ^{d} be a finite set such that {x ∈ IR^{d}; x ≥ 0} ∩ conv H = ∅. Let a be the unique solution of (2), (4). If there are constants m > 0 and u ∈ IR^{d} such that |φ(n)| ≤ m^{u·n} for all n ≱ s, then the generating function of a

F (x_{1}, x_{2}, …, x_{d}) = ∑_{n∈IN^{d}} a_{n}x_{1}^{n_{1}}x_{2}^{n_{2}} ⋯ x_{d}^{n_{d}}

is analytic in a neighborhood of the origin.

Proof: Existence and uniqueness of a follow from Theorem 2. By Theorem 1(iv), there is v ∈ IR^{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 now prove that |a_{n}| ≤ M^{v·n} for all n ∈ IN^{d}, using induction on the well-founded set (IN^{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}}. □

In the case of constant coefficients any term a_{n+h} with a non-zero coefficient c_{h} can be expressed explicitly from (4). As it turns out, there is always at least one “good” term.

Theorem 4 Let G ⊆ ZZ^{d} be a nonempty finite set. Then there exists a point g_{0} ∈ G such that the set H = {g − g_{0}; g ∈ G, g ≠ g_{0}} satisfies the equivalent conditions of Theorem 1.

Proof: Let g_{0} be the last point in G with respect to the lexicographic ordering of ZZ^{d}. Then it can be shown that ≺_{H}^{+} is asymmetric and has no infinite descending chains. □

3 Recurrences with algebraic generating functions

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

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

In dimension d = 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}.

Theorem 5 Let H ⊆ ZZ^{d} be a finite set such that {x ∈ IR^{d}; x ≥ 0} ∩ conv H = ∅. Let a be the unique solution of (2), (4), and F (x) = ∑_{n∈IN^{d}} a_{n}x^{n} its generating function.

(i) If the apex of H is 0 and all the initial sections

f_{j_{1},...,j_{m}}^{(i_{1},...,i_{m})}(x) = ∑_{{n∈IN^{d} \atop n_{i_{1}} =j_{1},...,n_{im} =jm}} a_{n}x^{n}

(1 ≤ m < d, 1 ≤ i_{1} < ⋯ < i_{m} ≤ d, 0 ≤ j_{r} < s_{i_{r}} for 1 ≤ r ≤ m)  (5)

are rational power series, then the generating function F (x) is rational.

(ii) If the apex of H has one positive coordinate and all the initial sections (5) are algebraic power series, then the generating function F (x) is algebraic.

Proof: From (4) we obtain

∑_{n≥s} a_{n}x^{n} = ∑_{h∈H} c_{h} ∑_{n≥s} a_{n+h}x^{n}

which can be rewritten as

(1 − ∑_{h∈H} c_{h}x^{−h}) F (x) = ∑_{n≱s} a_{n}x^{n} − ∑_{h∈H} c_{h}x^{−h} ∑_{n≱s+h} a_{n}x^{n}.  (6)

(i) If the apex of H is 0 then h ≤ 0 for all h ∈ H. Therefore the terms ∑_{n≱s} a_{n}x^{n} and ∑_{n≱s+h} a_{n}x^{n} are finite sums of initial sections and hence rational by assumption. Then

F (x) = \frac{∑_{n≱s} a_{n}x^{n} − ∑_{h∈H} c_{h}x^{−h} ∑_{n≱s+h} a_{n}x^{n}}{1 − ∑_{h∈H} c_{h}x^{−h}}  (7)

is rational, too.

(ii) Let p be the apex of H. Wlg. assume that p_{1} > 0 while the remaining coordinates of p are zero. Then h_{i} ≤ 0 for all i ≥ 2 and h ∈ H, so the right side of (6) is an affine combination, with coefficients which are algebraic power series in x_{1}, x_{2}, …, x_{d}, of the p_{1} sections f_{s_{1}}^{(1)}, f_{s_{1}+1}^{(1)}, …, f_{s_{1}+p_{1}−1}^{(1)}. Note that these sections are not given by the initial conditions (2). From the definition of sections it follows that we can write

f_{t}^{(1)}(x_{1}, x_{2}, …, x_{d}) = x_{1}^{t} g_{t−s_{1}+1}(x_{2}, …, x_{d}) (s_{1} ≤ t ≤ s_{1} + p_{1} − 1)

where g_{1}, g_{2}, …, g_{p_{1}} are unknown power series. Denote

P (x_{1}, x_{2}, …, x_{d}) = (1 − ∑_{h∈H} c_{h}x^{−h}) x^{p}.

From the definition of apex it follows that p ≥ 0 and p ≥ h for all h ∈ H, hence P (x_{1}, x_{2}, …, x_{d}) is a polynomial. Now (6) can be rewritten as

P (x_{1}, x_{2}, …, x_{d})F (x) = r_{0}(x_{1}, x_{2}, …, x_{d}) + ∑_{i=1}^{p_{1}} r_{i}(x_{1}, x_{2}, …, x_{d})g_{i}(x_{2}, …, x_{d})  (8)

where r_{i} are algebraic series. By setting x_{2}, …, x_{d} to zero, we find that

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

Because {x ∈ IR^{d}; x ≥ 0} ∩ conv H = ∅, we have h_{1} < 0 for all h ∈ H which have h_{2} = ⋯ = h_{d} = 0. Therefore p_{1} − h_{1} > p_{1} for all such h, which means that x_{1} = 0 is a root of P (x_{1}, 0, …, 0) of multiplicity p_{1}. Hence there exist p_{1} Puiseux series ξ_{1}(x_{2}, …, x_{d}), …, ξ_{p_{1}}(x_{2}, …, x_{d}) which satisfy

P (ξ_{j}(x_{2}, …, x_{d}), x_{2}, …, x_{d}) = 0 (1 ≤ j ≤ p_{1})

and which pass through the origin (i.e., ξ_{j}(0, …, 0) = 0 for 1 ≤ j ≤ p_{1}). If all ξ_{j} are different, substituting ξ_{1}, ξ_{2}, …, ξ_{p_{1}} for x_{1} in (8) gives a linear system of p_{1} linear equations with algebraic coefficients

∑_{i=1}^{p_{1}} r_{i}(ξ_{j}(x_{2}, …, x_{d}), x_{2}, …, x_{d})g_{i}(x_{2}, …, x_{d}) + r_{0}(ξ_{j}(x_{2}, …, x_{d}), x_{2}, …, x_{d}) = 0 (1 ≤ j ≤ p_{1})

satisfied by the p_{1} unknown series g_{1}, …, g_{p_{1}}. If P (x_{1}, x_{2}, …, x_{x}) considered as a polynomial of x_{1} has multiple roots, the number of equations will be less than p_{1}, but the missing equations can be obtained by differentiating (8) wrt. x_{1} an appropriate number of times before substitution. The resulting system is in both cases equivalent to the original recurrence relation (4) and initial conditions (2) satisfied by the coefficients of F (x) and is therefore uniquely solvable. It follows that g_{1}, …, g_{p_{1}} are algebraic, and hence so is

F (x) = \frac{r_{0}(x_{1}, x_{2}, …, x_{d}) + ∑_{i=1}^{p_{1}} r_{i}(x_{1}, x_{2}, …, x_{d})g_{i}(x_{2}, …, x_{d})}{P (x_{1}, x_{2}, …, x_{d})},

as claimed. □

Example 1 In the problem of generalized Dyck paths [3, 4] we are given a finite set of steps S = {(r_{1}, s_{1}), …, (r_{m}, s_{m})} where r_{i}, s_{i} ∈ ZZ and r_{i} > 0. We are interested in the number d_{n} of paths from (0, 0) to (n, 0) using only steps from S and staying within the first quadrant.

Denote by d_{i,k} the number of such paths ending at (i, k) (rather than at (n, 0)), and let r = max_{1≤i≤m} r_{i}, s = max_{1≤i≤m} s_{i}. Attach r − 1 columns of zeros to the left of the array d, and s rows of zeros below the array d. Call the resulting array a. Then d_{i,k} = a_{i+r−1,k+s} for i, k ≥ 0, and a satisfies

a_{i,k} = a_{i−r_{1},k−s_{1}} + ⋯ + a_{i−r_{m},k−s_{m}} (i ≥ r, k ≥ s),  (9)
a_{i,k} = δ_{i,r−1}δ_{k,s} (i < r or k < s).  (10)

This is a problem of the type (2), (4) where s = (r, s), H = {(−r_{1}, −s_{1}), …, (−r_{m}, −s_{m})}, and c_{h} = 1 for all h ∈ H. As all r_{i} are positive, {x ∈ IR^{d}; x ≥ 0} ∩ conv H = ∅, hence there exists a unique solution of (9), (10). Let t = − min{s_{1}, …, s_{m}}. We distinguish two cases.

a) If t ≤ 0 then the apex of H is (0, 0), so we can use formula (7) to obtain the rational generating functions

F (x, y) = ∑_{i,k=0}^{∞} a_{i,k}x^{i}y^{k} = \frac{x^{r−1}y^{s}}{1 − x^{r_{1}}y^{s_{1}} − ⋯ − x^{r_{m}}y^{s_{m}}} ,

G(x, y) = ∑_{i,k=0}^{∞} d_{i,k}x^{i}y^{k} = \frac{F (x, y)}{x^{r−1}y^{s}} = \frac{1}{1 − x^{r_{1}}y^{s_{1}} − ⋯ − x^{r_{m}}y^{s_{m}}} ,

g(x) = ∑_{n=0}^{∞} d_{n}x^{n} = G(x, 0) = (1 − ∑_{{1≤i≤m \atop s_{i}=0}} x^{r_{i}} )^{−1} .

b) If t > 0 then the apex of H is (0, t) and the corresponding generating functions are algebraic. Here

P (x, y) = y^{t} − x^{r_{1}}y^{s_{1}+t} − ⋯ − x^{r_{m}}y^{s_{m}+t}

and Eqn. (6) multiplied by y^{t−s} yields

\frac{P (x, y)}{y^{s}}F (x, y) = x^{r−1}y^{t} − ∑_{{1≤i≤m \atop s_{i}<0}} x^{r_{i}}y^{s_{i}+t} ∑_{k=s}^{s−1−s_{i}} y^{k−s}f_{k}(x)  (11)

where f_{k}(x) = ∑_{i=0}^{∞} a_{i,k}x^{i}. Let y = ξ_{1}(x), …, ξ_{t}(x) be those Puiseux series solutions of P (x, y) = 0 which pass through the origin. According to the procedure described in the proof of Theorem 5 (ii), we should now substitute ξ_{1}(x), …, ξ_{t}(x) for y in (11) and solve the resulting linear system for the unknown f_{s}(x), …, f_{s+t−1}(x). However, in this particular case we can immediately see what F (x, y) is. This is because the right-hand side of (11) is a polynomial in y of degree t with leading coefficient x^{r−1}, and we know all its zeros: they are ξ_{1}(x), …, ξ_{t}(x) (counted with their respective multiplicities), because they are zeros of the left-hand side. Therefore the right-hand side of (11) is x^{r−1}(y − ξ_{1}(x)) ⋯ (y − ξ_{t}(x)) and we have finally

F (x, y) = ∑_{i,k=0}^{∞} a_{i,k}x^{i}y^{k} = \frac{x^{r−1}y^{s}(y − ξ_{1}(x)) ⋯ (y − ξ_{t}(x))}{P (x, y)},

G(x, y) = ∑_{i,k=0}^{∞} d_{i,k}x^{i}y^{k} = \frac{F (x, y)}{x^{r−1}y^{s}} = \frac{(y − ξ_{1}(x)) ⋯ (y − ξ_{t}(x))}{P (x, y)},

g(x) = ∑_{n=0}^{∞} d_{n}x^{n} = G(x, 0) = \frac{(−1)^{t+1}ξ_{1}(x) ⋯ ξ_{t}(x)}{P (x, 0)} = (−1)^{t+1}ξ_{1}(x) ⋯ ξ_{t}(x) ( ∑_{{1≤i≤m \atop s_{i}=−t}} x^{r_{i}} )^{−1} .

In the special case S = {(s, r), (r, s), (s, −r), (r, −s)} where r > s > 0 we have

g(x) = \frac{(−1)^{r+1}ξ_{1}(x) ⋯ ξ_{r}(x)}{x^{s}}

where y = ξ_{1}(x), …, ξ_{r}(x) are those solutions of y^{r} − x^{s}y^{2r} − x^{r}y^{r+s} − x^{s} − x^{r}y^{r−s} = 0 which pass through the origin.

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 allowed for this step.

This approach generalizes without significant change to higher-dimensional paths, provided that the steps have positive coordinates in all but perhaps one (fixed) dimension. In all these cases, the generating functions are algebraic.

Example 2 Consider the problem of counting lattice paths with steps (1, 0) and (0, 1) which start at the origin and stay on or below the line y = (m − 1)x. Using the linear transformation (i, k) ↦ ((m − 1)i − k, k) we obtain the equivalent problem of counting lattice paths with steps (m − 1, 0) and (−1, 1) which start at the origin and stay within the first quadrant. Let d_{i,k} denote the number of such paths which end at (i, k). Attaching m − 1 columns of zeros to the left of the array d and one row of zeros below the array d, and changing the element at (0, 1) to 1, we obtain a new array a which satisfies a_{i,k} = d_{i−m+1,k−1} and

a_{i,k} = a_{i−m+1,k} + a_{i+1,k−1} (i ≥ m − 1, k ≥ 1) ,  (12)
a_{i,k} = δ_{i,0}δ_{k,1} (i < m − 1 or k < 1).  (13)

Here s = (m − 1, 1), H = {(−(m − 1), 0), (1, −1)}, the apex is at (1, 0), and P (x, y) = x − x^{m} − y. From (6) we obtain

P (x, y)F (x, y) = xy − y^{2} − yx^{m−1}f(y)  (14)

where f(y) = ∑_{k=0}^{∞} a_{m−1,k} is unknown. Let x = ξ(y) be that solution of P (x, y) = 0 which passes through the origin. Then, by substituting ξ(y) for x in (14), we find

f(y) = \frac{ξ(y) − y}{ξ(y)^{m−1}} = ξ(y)

and

F (x, y) = ∑_{i,k=0}^{∞} a_{i,k}x^{i}y^{k} = y \frac{x − y − x^{m−1}ξ(y)}{x − y − x^{m}},

G(x, y) = ∑_{i,k=0}^{∞} d_{i,k}x^{i}y^{k} = \frac{F (x, y) − y}{x^{m−1}y} = \frac{x − ξ(y)}{x − y − x^{m}} ,

g(y) = ∑_{k=0}^{∞} d_{0,k}y^{k} = G(0, y) = \frac{ξ(y)}{y}.

The algebraic equation satisfied by g(y) is easily obtained from P (ξ(y), y) = 0, and is g − y^{m−1}g − 1 = 0. Only every (m − 1)-st coefficient of g is nonzero. Omitting the zero coefficients we have

h(y) = ∑_{k=0}^{∞} d_{0,(m−1)k}y^{k} = g(y^{1/(m−1)})

which satisfies h − yh^{m} − 1 = 0.

In a similar way, we could count the paths which start at the origin and stay below the line y = (m − 1)x (cf. [1]). 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. Generalization to higher dimensions is also possible.

Additional examples of this kind can be found in [2, Exer. 2.2.1.–4, 11] (the ballot numbers) and in [6] (the number of elements of the free modular lattice generated by the poset 1 + 1 + n).

\begin{matrix}i \ k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 1 & 2 & 2 & 3 & 3 & 5 & 6 & 8 & 12 & 18 \\ 3 & 1 & 1 & 2 & 2 & 4 & 5 & 7 & 11 & 17 & 23 & 40 \\ 4 & 1 & 1 & 3 & 4 & 6 & 10 & 16 & 22 & 39 & 62 & 91 \\ 5 & 1 & 1 & 3 & 5 & 10 & 14 & 27 & 44 & 67 & 123 & 208 \\ 6 & 1 & 1 & 5 & 7 & 16 & 27 & 44 & 83 & 145 & 225 & 432 \\ 7 & 1 & 1 & 6 & 11 & 22 & 44 & 83 & 134 & 268 & 476 & 767 \\ 8 & 1 & 1 & 8 & 17 & 39 & 67 & 145 & 268 & 450 & 908 & 1656 \\ 9 & 1 & 1 & 12 & 23 & 62 & 123 & 225 & 476 & 908 & 1534 & 3161 \\ 10 & 1 & 1 & 18 & 40 & 91 & 208 & 432 & 767 & 1656 & 3161 & 5422 \end{matrix}

Figure 1: Solution of (15), (16) for i, k ≤ 10.

4 The problem of the knight

When the apex of the set of shifts H has more than one positive coordinate, we suspect that the generating function of the solution of (2), (4) need not be algebraic even though all the initial sections (5) are. In this section we present an example of this type and prove that the generating function is not rational.

Example 3 On an otherwise empty chessboard which is infinite upwards and to the right there is a knight occupying the square (i, k). If the knight is only allowed to move either 2 left and 1 up, or 2 down and 1 right, in how many different ways could it reach the border of the chessboard? The border consists of the first two rows and the first two columns, and once the knight reaches it, it is not allowed to move anymore.

Let a_{i,k} be the answer to this lattice-path problem. Then, obviously,

a_{i,k} = a_{i−2,k+1} + a_{i+1,k−2}  (i, k ≥ 2),  (15)
a_{i,0} = a_{i,1} = a_{0,k} = a_{1,k} = 1  (i, k ≥ 0).  (16)

Here H = {(−2, 1), (1, −2)} and {x ∈ IR^{d}; x ≥ 0} ∩ conv H = ∅, so there exists a unique solution a of (15), (16), part of which is shown in Fig. 1. The apex of H is (1, 1), so Theorem 5 does not apply. In fact, this is the simplest example in which the apex of H has two positive coordinates and H is symmetric w.r.t. the line i = k. By induction on i + k one can show that a_{i,k} = a_{k,i} and hence F (x, y) = F (y, x). One can also show that 1 ≤ a_{ik} ≤ 2^{i+k}, therefore the power series

F (x, y) = ∑_{i,k=0}^{∞} a_{i,k}x^{i}y^{k}

converges at least for |x|, |y| < 1/2. Let f_{k}(x) = ∑_{i=0}^{∞} a_{i,k}x^{i} denote the generating function for the k^{th} row of a. Then from (15) it follows that F (x, y) satisfies

(x^{3} + y^{3} − xy)F (x, y) = xy(a_{0,0} + a_{1,0}x + a_{0,1}y + a_{1,1}xy) + x(x^{2} − y) (f_{0}(x) + yf_{1}(x))
+ y(y^{2} − x) (f_{0}(y) + xf_{1}(y)) + x^{2}y^{2} (xf_{2}(x) + yf_{2}(y)) ,  (17)

while (16) implies that f_{0}(x) = f_{1}(x) = 1/(1 − x). Writing f(x) for xf_{2}(x), equation (17) thus turns into

(x^{3} + y^{3} − xy)F (x, y) = \frac{x^{3} + y^{3} − xy + x^{2}y^{2}(xy − x − y)}{(1 − x)(1 − y)} + x^{2}y^{2}(f(x) + f(y)).  (18)

By restricting (17) to the cubic curve

x^{3} + y^{3} − xy = 0  (19)

Figure 2: The leaf of Descartes (x^{3} + y^{3} = xy).

shown in Fig. 2, an additional functional equation satisfied by f is obtained:

f(x) + f(y) = \frac{1}{(1 − x)(1 − y)} − 1  (when x^{3} + y^{3} = xy).  (20)

This equation uniquely determines f(x) = x ∑_{k=0}^{∞} a_{2,k}x^{k}.

Theorem 6 The formal power series f defined by (20) is not rational.

Proof: Assume that f(x) is a rational function of x. Let x(t) = t/(1 + t^{3}), y(t) = t^{2}/(1 + t^{3}) be a rational parameterization of (19). Then

f(x(t)) + f(y(t)) = \frac{1}{(1 − x(t))(1 − y(t))} − 1  (21)

as an equality of rational functions of t.

Let t_{0} = 1/ ^{3} \sqrt{2}, x_{0} = x(t_{0}) = ^{3} \sqrt{4}/3, y_{0} = y(t_{0}) = ^{3} \sqrt{2}/3. We claim that f(x) is singular at x = x_{0}. Differentiating both sides of (21) w.r.t. t we find

f′(x) = \frac{1}{(1 − x)^{2}(1 − y)} + \frac{ẏ(t)}{ẋ(t)} (\frac{1}{(1 − x)(1 − y)^{2}} − f′(y))  (x = x(t), y = y(t)).  (22)

The derivative f′(y) is regular at y = y_{0}, because the series f(y) converges for |y| < 1/2 and y_{0} < 1/2. By using the rough upper bound a_{2,k} ≤ 2^{k+2} for k ≥ n, we can estimate

f′(y_{0}) = ∑_{k=0}^{∞}(k + 1)a_{2,k}y_{0}^{k}

≤ ∑_{k=0}^{n−1}(k + 1)a_{2,k}y_{0}^{k} + ∑_{k=n}^{∞}(k + 1)2^{k+2}y_{0}^{k}

= ∑_{k=0}^{n−1}(k + 1)a_{2,k}y_{0}^{k} + 8(n(1 − 2y_{0}) + 1)\frac{(2y_{0})^{n}}{(1 − 2y_{0})^{2}}

which, using a computer algebra system and taking n = 99, gives f′(y_{0}) < 4.726. On the other hand, 1/((1 − x_{0})(1 − y_{0})^{2}) > 6.312, proving that 1/((1 − x_{0})(1 − y_{0})^{2}) − f′(y_{0}) ≠ 0. Likewise ẏ(t_{0}) = ^{3} \sqrt{4}/3 ≠ 0 and (1 − x_{0})^{2}(1 − y_{0}) ≠ 0, while ẋ(t_{0}) = 0. From (22) it follows that the rational function f′(x(t)) is the sum of two terms, one of which is regular and the other singular at t = t_{0}. Therefore f′(x), and hence f(x), is singular at x = x_{0} as claimed.

On the other hand, from (21) it follows that f(x(t)) = 1/((1 − x(t))(1 − y(t))) − f(y(t)) − 1. All three terms on the right are regular at t = t_{0}, hence so is f(x(t)). Therefore f(x) should be regular at x = x_{0}. This contradiction shows that f(x) is not a rational power series. □

We conjecture that f(x) (and therefore F (x, y)) is not algebraic, and, moreover, not even D-finite [9, 5]. Note that by replacing the initial conditions (16) by

a_{i,0} = 2^{i}, a_{i,1} = 2^{i+1} (i ≥ 0),
a_{0,k} = 2^{k}, a_{1,k} = 2^{k+1} (k ≥ 0),

the solution of (15) changes to a_{i,k} = 2^{i+k} with rational generating function F (x, y) = \frac{1}{(1−2x)(1−2y)}.

Acknowledgement. The author wishes to express his thanks to Philippe Flajolet, Bruno Salvy and Ivan Vidav for helpful discussions of the problem of the knight. He is also indebted very much to an anonymous referee who pointed out applications to lattice path problems and provided further candidates for nonalgebraic generating function.

References

[1] I. Gessel, A factorization for formal Laurent series and lattice path enumeration, J. Comb. Th. A 28 (1980) 321–337.

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

[3] J. Labelle, Y.-N. Yeh, Dyck paths of knight moves, Discr. Appl. Math. 24 (1989) 213–221.

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

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

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

[7] 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).

[8] J. Riordan, Combinatorial Identities, John Wiley & Sons, New York, 1968.

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

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