Séminaire Lotharingien de Combinatoire 44 (2000), Article B44h

On a class of combinatorial diophantine equations

Peter Kirschenhofer^{∗} and Oliver Pfeiffer^{†}

Department of Mathematics and Statistics, University of Leoben, Austria

Abstract. We give a combinatorial proof for a second order recurrence for the polynomials p_{n}(x), where p_{n}(k) counts the number of integer-coordinate lattice points \underline{x} = (x_{1}, …, x_{n}) with ∥\underline{x}∥ = ∑_{i=1}^{n}|x_{i}| ≤ k. This is the main step to get finiteness results on the number of solutions of the diophantine equation p_{n}(x) = p_{m}(y) if n and m have different parity. The combinatorial approach also allows to extend the original diophantine result to more general combinatorial situations.

1 Introduction

In [7] P. Kirschenhofer, A. Pethő and R. F. Tichy have studied the polynomials p_{n}(x) which are achieved by continuation of p_{n}(k) counting the number of integer-coordinate lattice points \underline{x} = (x_{1}, …, x_{n}) in a domain ∥\underline{x}∥ = ∑_{i=1}^{n}|x_{i}| ≤ k of the n-dimensional space. Using an analytical approach it was shown that the p_{n}(x) obey the second order recurrence

np_{n}(x) = (2x + 1)p_{n−1}(x) + (n − 1)p_{n−2}(x), n ≥ 1; p_{−1}(x) = 0, p_{0}(x) = 1 (1.1)

This recurrence allows to identify the polynomials

q_{n}(x) = i^{n}n!p_{n}(−\frac{1}{2} − \frac{ix}{2})  (1.2)

∗kirsch@unileoben.ac.at

†pfeiffer@unileoben.ac.at, research supported by the Austrian Science Foundation (FWF) Project Nr. P14200-MAT

as a set of real orthogonal polynomials (via a theorem that is usually attributed to Favard [5], but in fact is much older, compare e.g. the comments in [1] or[2]). More precisely, the (q_{n}(x))_{n≥0} turn out to belong to the classes of orthogonal Sheffer sets (compare [7]) identified by Meixner in his classical paper [9], namely

q_{n}(x) = n!P_{n}^{( \frac{1}{2} )}(\frac{x}{2}, \frac{π}{2} ),  (1.3)

where P_{n}^{(λ)}(x, ϕ) denotes the Meixner-Pollaczek polynomials

P_{n}^{(λ)}(x, ϕ) = \frac{(2λ)_{n}}{n!} e^{inϕ} _{2}F_{1}[ \begin{matrix}−n, λ + ix \\ 2λ \end{matrix} ; 1 − e^{−2iϕ}]  (1.4)

(compare [8, Section 1.7]).

In [7] the interest is focussed on finiteness results on the diophantine equation

p_{n}(x) = p_{m}(y).  (1.5)

For several small values of n, bounds on the number of integer solutions of (1.5) can be established using a famous result by Baker [3]. Furthermore, using a method due to Davenport, Lewis and Schinzel [6] it is proved in [7] that equation (1.5) has only finitely many solutions if n and m have different parity. A key step in order to apply the technique by Davenport, Lewis and Schinzel is to have information about the location of the zeroes of the polynomials in question (resp. of their derivatives), and this information may be drawn from the orthogonality of the q_{n}(x). Therefore the existence of a second order recurrence of type (1.1) for the p_{n}(x) plays a central role for this diophantine problem as well as possible generalizations.

At the 42nd session of the Seminaire in Maratea the question was posed, whether there is a purely combinatorial proof for (1.1). In the following we present such a type of proof, starting from the original interpretation of p_{n}(k) as a number of lattice points.

A different combinatorial approach would be the following: The p_{n}(k) have the double generating function

∑_{n,k≥0} p_{n}(k)z^{n}u^{k} = \frac{1}{1 − z − u − zu}  (1.6)

(compare [7]). Therefore the p_{n}(k) also count the number of minimal lattice paths with diagonal steps from (0, 0) to (n, k), where a single step leads either one unit to the right or one unit to the top or is a diagonal step from (i, j) to (i + 1, j + 1). (It is not difficult to find a bijection between the lattice points from the original definition and these lattice paths, too.) Using the lattice path interpretation the p_{n}(k) are known in the literature as Delannoy numbers D(n, k) (compare [4, p.80]). Starting from this kind of interpretation combinatorical proofs for recurrence (1.1) may be gained, too.

From (1.6) it follows immediately that

∑_{n≥0} n!p_{n}(k)\frac{z^{n}}{n!} = exp \{k log (1 + z) − (k + 1) log (1 − z)\},  (1.7)

so that n!p_{n}(k) may be interpretated in an “exponential model” (compare e.g. [11]) as a set of labelled objects whose “components” have the exponential generating function

k log (1 + z) − (k + 1) log (1 − z) = ∑_{n≥1}(n − 1)!a_{n} \frac{z^{n}}{n!} ,

where

a_{n} = \begin{cases}2k + 1 & for n odd \\ 1 & for n even \end{cases} .  (1.8)

In the final section we formulate a slightly more general situation of permutations with coloured cycles. The corresponding second order linear recurrence allows to extend the original diophantine result from [7] to this situation, too.

2 A combinatorial proof for (1.1)

Let n, k be positive integers and F_{n,k} denote the set of lattice points described in the previous section. Then np_{n}(k), i.e. the left hand side of (1.1), counts the number of sequences in F_{n,k}^{∗} where F_{n,k}^{∗} originates from F_{n,k} by labeling one of the elements:

\underline{x} = (x_{1}, …, x_{i}_{∗}, …, x_{n}) ∈ F_{n,k}^{∗}.  (2.1)

In order to find the right hand side of (1.1) we split up F_{n,k}^{∗} in the following way:

• Case 1: \underline{x} = \underline{x}_{A}0_{∗}0\underline{x}_{B} (with possibly empty strings \underline{x}_{A} and \underline{x}_{B}).

In this instance we map \underline{x} to \underline{y} = \underline{x}_{A}\underline{x}_{B} ∈ F_{n−2,k}. Obviously, any fixed sequence \underline{y} = (y_{1}, …, y_{n−2}) has exactly n − 1 representations \underline{y} = \underline{x}_{A}\underline{x}_{B}, so that each element of F_{n−2,k} will occur (n − 1)-times in this way. Altogether we have produced (n−1)p_{n−2}(k) sequences, which corresponds to the last term in (1.1).

• Case 2: \underline{x} = \underline{x}_{A}0_{∗}.

We map \underline{x} to \underline{y} = \underline{x}_{A} ∈ F_{n−1,k}. This can be done in exactly one way, thus we obtain p_{n−1}(k) sequences in this case.

• Case 3: \underline{x} = \underline{x}_{A}0_{∗}x_{i+1}\underline{x}_{B} with x_{i+1} ≠ 0.

We map \underline{x} to \underline{y} = \underline{x}_{A}(−|x_{i+1}|)\underline{x}_{B} ∈ F_{n−1,k}. For any negative entry in \underline{y} there is a representation of \underline{y} as \underline{x}_{A}(−|x_{i+1}|)\underline{x}_{B}. Denoting the number of all negative entries in \underline{y} by N^{−}(\underline{y}) we therefore obtain 2N^{−}(\underline{y}) copies of any string \underline{y} in F_{n−1,k} by this mapping. The factor 2 here arises from the fact that the absolute value of x_{i+1} is taken in the mapping.

• Case 4: \underline{x} = \underline{x}_{A}j_{∗} with j ≠ 0.

We map \underline{x} to \underline{y} = \underline{x}_{A} ∈ F_{n−1,k}. Since ∥\underline{x}∥ has to be less or equal to k, we have to ensure that ∥\underline{x}_{A}∥ + |j| ≤ k from which we obtain 1 ≤ |j| ≤ k −∥\underline{y}∥. Thus any string \underline{y} ∈ F_{n−1,k} appears 2(k −∥\underline{y}∥) times as an image. The factor 2 again arises since the absolute value of j is taken in this mapping.

• Case 5a: \underline{x} = \underline{x}_{A}j_{∗}x_{i+1}\underline{x}_{B} with j ≠ 0 and x_{i+1} ≥ 0.

We map \underline{x} to \underline{y} = \underline{x}_{A}(\underbrace{|j| + x_{i+1}}_{=y_{i}})\underline{x}_{B} ∈ F_{n−1,k}. Now is |j| ≥ 1 and

y_{i} − |j| = x_{i+1} has to be greater or equal to 0. Together this means that 1 ≤ |j| ≤ y_{i} such that there are y_{i} possibilities to select |j| for any positive y_{i}. Denoting the sum over all positive (resp. negative) entries of \underline{y} by ∥\underline{y}∥_{+} (resp. ∥\underline{y}∥_{−}) we have altogether 2 ∑_{y_{i}>0} y_{i} = 2∥\underline{y}∥_{+} possibilities in this case.

• Case 5b: \underline{x} = \underline{x}_{A}j_{∗}x_{i+1}\underline{x}_{B} with j ≠ 0 and x_{i+1} < 0.

We map \underline{x} to \underline{y} = \underline{x}_{A}(\underbrace{−|j| + x_{i+1}}_{=y_{i}})\underline{x}_{B} ∈ F_{n−1,k}. In the same manner as

in case 5a we find 1 ≤ |j| ≤ (−y_{i}) − 1. Therefore we obtain (−y_{i}) − 1 possibilities for |j|, so that in total the frequency of \underline{y} ∈ F_{n−1,k} is

2( ∑_{−y_{i}≥2}(−y_{i}) − 1) = 2( ∑_{−y_{i}≥1}(−y_{i}) − 1) = 2 ∑_{−y_{i}>0}(−y_{i}) − 2 ∑_{−y_{i}>0} 1 =

= 2∥\underline{y}∥_{−} − 2N^{−}(\underline{y}).

Summing up cases 2 to 5b, each sequence in F_{n−1,k} occurs with the frequency

1 + 2N^{−}(\underline{y}) + 2(k − ∥\underline{y}∥) + 2∥\underline{y}∥_{+} + 2∥\underline{y}∥_{−} − 2N^{−}(\underline{y}) = 2k + 1,

which means that the number of sequences produced in these cases corresponds to (2k + 1)p_{n}(k).

Together with case 1 this proves the recurrence (1.1).

3 Permutations with coloured cycles

The exponential generating function (1.7) for the numbers n!p_{n}(k) immediately yields a combinatorial interpretation of these quantities in an exponential model, compare the comments in the Introduction. In the following we present a slight extension of this model: whereas numerous combinatorial models of this type are known from literature (compare e.g. [10]), our main point of observation is, that proceeding in this way the diophantine result from [7] can be extended to a whole class of combinatorial counting polynomials.

Let us consider the set P_{n;a,b} of coloured permutations of {1, 2, …, n}, where each cycle in the canonical cycle representation is associated a colour, and there are a colours for the cycles of odd length and b colours for the cycles of even length. Let c_{n}(a, b) be the number of elements in P_{n;a,b}. Then the following recurrence holds:

c_{n}(a, b) = ac_{n−1}(a, b) + (n − 1)(n − 2 + b)c_{n−2}(a, b), n ≥ 1; c_{−1}(a, b) = 0, c_{0}(a, b) = 1. (3.1)

To prove (3.1) let us consider a permutation π ∈ P_{n;a,b} and have a look at the position of the element n in the canonical cycle decomposition.

If (n) forms a 1-cycle of π, then there are a colours for (n), and there are c_{n−1}(a, b) possibilities for the remaining part of π, which may be interpreted as an element of P_{n−1;a,b}.

If n belongs to a cycle of length ≥ 2, we consider the element m following n in this cycle. There are n−1 possibilities for m. If we consider all c_{n−2}(a, b) coloured permutations σ of {1, 2, …, n − 1}\{m}, there are n − 2 different possibilities to insert the block nm in an existing block of σ (without altering its colour) to obtain all coloured permutations of {1, …, n}, where n is in a block of length ≥ 3. If we adjoin (nm) as a cycle of length 2 to σ, there are b possible colours for that cycle and we obtain the remaining coloured permutations of P_{n;a,b}.

Thus the proof of (3.1) is complete.

An immediate consequence of (3.1) is

c_{n}(2k + 1, 1) = n!p_{n}(k)  (3.2)

where p_{n}(k) is defined as in the previous sections. This coincides also with the information gained from (1.8). Furthermore, we find that

i^{n}c_{n}(−ix, b) = n!P_{n}^{( \frac{b}{2} )}(\frac{x}{2}, \frac{π}{2} )

resp.

c_{n}(x, b) = i^{n}n!P_{n}^{( \frac{b}{2} )}(−\frac{ix}{2}, \frac{π}{2} ),

where P_{n}^{(λ)}(x, ϕ) are the Meixner-Pollaczek polynomials from (1.4). As a consequence the diophantine result from [7, Theorem 4.4] on (1.5) can be generalized as follows:

The diophantine equation

\overline{c}_{n}(x; b) = \overline{c}_{m}(y; b), b ∈ ℕ  (3.3)

where \overline{c}_{k}(x; b) = \frac{1}{k!}c_{k}(x; b) is the average number of colourings of a permutation in P_{k;a,b}, has for n, m ≥ 3, n ≢ m (mod 2) only a finite number of integer solutions.

References

[1] G. E. Andrews, R. Askey. Classical orthogonal polynomials. Polynomes orthogonaux et applications, Proc. Laguerre Symp., Bar-le-Duc/France 1984, Lect. Notes Math. 1171, 36-62 (1985).

[2] W. Van Assche. Orthogonal polynomials in the complex plane and on the real line. Ismail, Mourad E. H. (ed.) et al., Special functions, q-series and related topics. Providence, RI: American Mathematical Society. Fields Inst. Commun. 14, 211-245 (1997).

[3] A. Baker. Bounds for the solutions of the hyperelliptic equation. Proc. Camb. Philos. Soc. 65, 439-444 (1969).

[4] L. Comtet. Advanced combinatorics : the art of finite and infinite expansions. Revised and enlarged edition. Dordrecht, Holland - Boston, U.S.A.: D. Reidel Publishing Company. X, 343 S. (1974).

[5] J. A. Favard Sur les polynomes de Tchebicheff. C. R. Acad. Sci., Paris 200, 2052-2053 (1935).

[6] H. Davenport, D. J. Lewis, A. Schinzel. Equations of the form f(x) = g(y). Q. J. Math., Oxf. II. Ser. 12, 304-312 (1961).

[7] P. Kirschenhofer, A. Pethő, R. F. Tichy. On analytical and diophantine properties of a family of counting polynomials. Acta Sci. Math. 65, 47-59 (1999).

[8] R. Koekoek, R. F. Swarttouw. The Askey-scheme of hypergeometric orthogonal polynomials and its q-analogue. http://aw.twi.tudelft.nl/˜ koekoek/askey/index.html

[9] J. Meixner. Orthogonale Polynomsysteme mit einer besonderen Gestalt der erzeugenden Funktion. J. London Math. Soc. 9 6-13 (1934).

[10] V. Strehl. Zykel-Enumeration bei lokal-strukturierten Funktionen. Habilitationsschrift. Universität Erlangen-Nürnberg. 307 S. (1990).

[11] H. S. Wilf. generatingfunctionology. Boston [u.a.]: Academic Press. VIII, 184 S. (1990).