\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}

\newcommand{\abs}[1]{\lvert#1\rvert}
\renewcommand{\vec}[1]{\underline{#1}}
\newcommand{\marked}[1]{\underset{*}{#1}}
\newcommand{\norm}[1]{\lVert#1\rVert}
\newcommand{\set}[1]{\{#1\}}
\newcommand{\without}{\backslash}
\newcommand{\N}{\mathbb{N}}
\DeclareMathOperator{\hypergeom}{\mathit{F}}

\numberwithin{equation}{section}

\begin{document}

\title{On a class of combinatorial diophantine equations}
\author{Peter Kirschenhofer\thanks{kirsch@unileoben.ac.at}\; and Oliver Pfeiffer\thanks{pfeiffer@unileoben.ac.at, research %%@
supported by the Austrian Science Foundation (FWF) Project Nr. P14200-MAT}\\\small Department of Mathematics and Statistics, %%@
University of Leoben, Austria}
\date{}
\maketitle

%First page headline in AmS-TeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 44 \rms (2000), Article~B44h\hfill}
\def\thepage{}

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 $\vec{x}=(x_1,\ldots,x_n)$ with $\norm{\vec{x}}=\sum_{i=1}^n\abs{x_i}\leq
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.

\section{Introduction}
In \cite{tichy} P. Kirschenhofer, A. Peth\H o 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 $\vec{x}=(x_1,\ldots,x_n)$ in a domain
$\norm{\vec{x}}=\sum_{i=1}^n\abs{x_i}\leq k$ of the $n$-dimensional space. Using an analytical approach it was shown that
the $p_n(x)$ obey the second order recurrence
\begin{multline}
\label{recurrence} np_n(x)=(2x+1)p_{n-1}(x)+(n-1)p_{n-2}(x),\ n\geq1;\\
p_{-1}(x)=0,\ p_0(x)=1
\end{multline}
This recurrence allows to identify the polynomials
\begin{equation}
q_n(x)=i^nn!p_n(-\frac{1}{2}-\frac{ix}{2})
\end{equation}
as a set of real orthogonal polynomials (via a theorem that is usually attributed to Favard \cite{favard}, but in fact is
much older, compare e.g. the comments in \cite{askey} or\cite{assche}). More precisely, the $(q_n(x))_{n\geq0}$ turn out to
belong to the classes of orthogonal Sheffer sets (compare \cite{tichy}) identified by Meixner in his classical paper
\cite{meixner}, namely
\begin{equation}
q_n(x)=n!P_n^{(\frac{1}{2})}(\frac{x}{2},\frac{\pi}{2}),
\end{equation}
where $P_n^{(\lambda)}(x,\phi)$ denotes the Meixner-Pollaczek polynomials
\begin{equation}
\label{meixner}
P_n^{(\lambda)}(x,\phi)=\frac{(2\lambda)_n}{n!}{e^{in\phi}}\sideset{_2}{_1}\hypergeom\Bigl[\begin{array}{c}-n,
\lambda+ix\\2\lambda\end{array};1-e^{-2i\phi}\Bigr]
\end{equation}
(compare \cite[Section 1.7]{koekoek}).

In \cite{tichy} the interest is focussed on finiteness results on the diophantine equation
\begin{equation}
\label{diophantine} p_n(x)=p_m(y).
\end{equation}
For several small values of $n$, bounds on the number of integer solutions of (\ref{diophantine}) can be established using a
famous result by Baker \cite{baker}. Furthermore, using a method due to Davenport, Lewis and Schinzel \cite{lewis} it is
proved in \cite{tichy} that equation (\ref{diophantine}) 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 (\ref{recurrence}) 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
(\ref{recurrence}). 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
\begin{equation}
\label{generating}
\sum_{n,k\geq0}p_n(k)z^nu^k=\frac{1}{1-z-u-zu}
\end{equation}
(compare \cite{tichy}). 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 \emph{Delannoy
numbers} $D(n,k)$ (compare \cite[p.80]{comtet}). Starting from this kind of interpretation combinatorical proofs for
recurrence (\ref{recurrence}) may be gained, too.

From (\ref{generating}) it follows immediately that
\begin{equation}
\label{exponential}
\sum_{n\geq0}n!p_n(k)\frac{z^n}{n!}=\exp{\Bigl\{k\log{(1+z)}-(k+1)\log{(1-z)}\Bigl\}},
\end{equation}
so that $n!p_n(k)$ may be interpretated in an ``exponential model'' (compare e.g. \cite{wilf}) as a set of labelled objects
whose ``components'' have the exponential generating function
\begin{equation*}
k\log{(1+z)}-(k+1)\log{(1-z)}=\sum_{n\geq1}(n-1)!a_n\frac{z^n}{n!},
\end{equation*}
where
\begin{equation}
\label{coefficient}
a_n=
\begin{cases}
2k+1 & \text{for $n$ odd}\\
1 & \text{for $n$ even}
\end{cases}.
\end{equation}
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 \cite{tichy} to this situation, too.
\section{A combinatorial proof for (\ref{recurrence})}
Let $n$, $k$ be positive integers and $\mathcal{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 (\ref{recurrence}), counts the number of sequences in
$\mathcal{F}_{n,k}^*$ where $\mathcal{F}_{n,k}^*$ originates from $\mathcal{F}_{n,k}$ by labeling one of the elements:
\begin{equation}
\vec{x}=(x_1,\ldots,\marked{x_i},\ldots,x_n)\in\mathcal{F}_{n,k}^*.
\end{equation}
In order to find the right hand side of (\ref{recurrence}) we split up $\mathcal{F}_{n,k}^\ast$ in the following way:
\begin{itemize}
\item Case 1: $\vec{x}=\vec{x}_A\marked{0}0\vec{x}_B$ (with possibly empty strings $\vec{x}_A$ and $\vec{x}_B$).

In this instance we map $\vec{x}$ to $\vec{y}=\vec{x}_A\vec{x}_B\in\mathcal{F}_{n-2,k}$. Obviously, any fixed sequence
$\vec{y}=(y_1,\ldots,y_{n-2})$ has exactly $n-1$ representations $\vec{y}=\vec{x}_A\vec{x}_B$, so that each element of
$\mathcal{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 (\ref{recurrence}).
\item Case 2: $\vec{x}=\vec{x}_A\marked{0}$.

We map $\vec{x}$ to $\vec{y}=\vec{x}_A\in\mathcal{F}_{n-1,k}$. This can be done in exactly one way, thus we obtain
$p_{n-1}(k)$ sequences in this case.
\item Case 3: $\vec{x}=\vec{x}_A\marked{0}x_{i+1}\vec{x}_B$ with $x_{i+1}\neq0$.

We map $\vec{x}$ to $\vec{y}=\vec{x}_A(-\abs{x_{i+1}})\vec{x}_B\in\mathcal{F}_{n-1,k}$. For any negative entry in $\vec{y}$
there is a representation of $\vec{y}$ as $\vec{x}_A(-\abs{x_{i+1}})\vec{x}_B$. Denoting the number of all negative entries
in $\vec{y}$ by $N^-(\vec{y})$ we therefore obtain $2N^-(\vec{y})$ copies of any string $\vec{y}$ in $\mathcal{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.
\item Case 4: $\vec{x}=\vec{x}_A\marked{j}$ with $j\neq0$.

We map $\vec{x}$ to $\vec{y}=\vec{x}_A\in\mathcal{F}_{n-1,k}$. Since $\norm{\vec{x}}$ has to be less or equal to $k$, we
have to ensure that $\norm{\vec{x}_A}+\abs{j}\leq k$ from which we obtain $1\leq\abs{j}\leq k-\norm{\vec{y}}$. Thus any
string $\vec{y}\in\mathcal{F}_{n-1,k}$ appears $2(k-\norm{\vec{y}})$ times as an image. The factor $2$ again arises since
the absolute value of $j$ is taken in this mapping.
\item Case 5a: $\vec{x}=\vec{x}_A\marked{j}x_{i+1}\vec{x}_B$ with $j\neq0$ and $x_{i+1}\geq0$.

We map $\vec{x}$ to $\vec{y}=\vec{x}_A(\underbrace{\abs{j}+x_{i+1}}_{=y_i})\vec{x}_B\in\mathcal{F}_{n-1,k}$. Now is
$\abs{j}\geq1$ and $y_i-\abs{j}=x_{i+1}$ has to be greater or equal to $0$. Together this means that $1\leq\abs{j}\leq y_i$
such that there are $y_i$ possibilities to select $\abs{j}$ for any positive $y_i$. Denoting the sum over all positive
(resp. negative) entries of $\vec{y}$ by $\norm{\vec{y}}_+$ (resp. $\norm{\vec{y}}_-$) we have altogether
$2\sum_{y_i>0}y_i=2\norm{\vec{y}}_+$ possibilities in this case.
\item Case 5b: $\vec{x}=\vec{x}_A\marked{j}x_{i+1}\vec{x}_B$ with $j\neq0$ and $x_{i+1}<0$.

We map $\vec{x}$ to $\vec{y}=\vec{x}_A(\underbrace{-\abs{j}+x_{i+1}}_{=y_i})\vec{x}_B\in\mathcal{F}_{n-1,k}$. In the same
manner as in case 5a we find $1\leq\abs{j}\leq(-y_i)-1$. Therefore we obtain $(-y_i)-1$ possibilities for $\abs{j}$, so that
in total the frequency of $\vec{y}\in\mathcal{F}_{n-1,k}$ is
\begin{multline*}
2(\sum_{-y_i\geq2}(-y_i)-1)=2(\sum_{-y_i\geq1}(-y_i)-1)=2\sum_{-y_i>0}(-y_i)-2\sum_{-y_i>0}1=\\
=2\norm{\vec{y}}_--2N^-(\vec{y}).
\end{multline*}
\end{itemize}
Summing up cases 2 to 5b, each sequence in $\mathcal{F}_{n-1,k}$ occurs with the frequency
\begin{equation*}
1+2N^-(\vec{y})+2(k-\norm{\vec{y}})+2\norm{\vec{y}}_++2\norm{\vec{y}}_--2N^-(\vec{y})=2k+1,
\end{equation*}
which means that the number of sequences produced in these cases corresponds to $(2k+1)p_n(k)$.

\medskip

Together with case 1 this proves the recurrence (\ref{recurrence}).
\section{Permutations with coloured cycles}
The exponential generating function (\ref{exponential}) 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. \cite{strehl}), our main point of observation is, that proceeding in this way the diophantine result from
\cite{tichy} can be extended to a whole class of combinatorial counting polynomials.

Let us consider the set $\mathcal{P}_{n;a,b}$ of coloured permutations of $\set{1,2,\ldots,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 $\mathcal{P}_{n;a,b}$. Then the following
recurrence holds:
\begin{multline}
\label{coloured}
c_n(a,b)=ac_{n-1}(a,b)+(n-1)(n-2+b)c_{n-2}(a,b),\ n\geq1;\\
c_{-1}(a,b)=0,\ c_0(a,b)=1.
\end{multline}
To prove (\ref{coloured}) let us consider a permutation $\pi\in\mathcal{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 $\pi$, then there are $a$ colours for $(n)$, and there are $c_{n-1}(a,b)$ possibilities for
the remaining part of $\pi$, which may be interpreted as an element of $\mathcal{P}_{n-1;a,b}$.

If $n$ belongs to a cycle of length $\geq2$, 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 $\sigma$ of
$\set{1,2,\ldots,n-1}\without\set{m}$, there are $n-2$ different possibilities to insert the block $nm$ in an existing
block of $\sigma$ (without altering its colour) to obtain all coloured permutations of $\set{1,\ldots,n}$, where $n$ is in
a block of length $\geq3$. If we adjoin $(nm)$ as a cycle of length $2$ to $\sigma$, there are $b$ possible colours for that
cycle and we obtain the remaining coloured permutations of $\mathcal{P}_{n;a,b}$.

Thus the proof of (\ref{coloured}) is complete.

\medskip

An immediate consequence of (\ref{coloured}) is
\begin{equation}
c_n(2k+1,1)=n!p_n(k)
\end{equation}
where $p_n(k)$ is defined as in the previous sections. This coincides also with the information gained from
(\ref{coefficient}). Furthermore, we find that
\begin{equation*}
i^nc_n(-ix,b)=n!P_n^{(\frac{b}{2})}(\frac{x}{2},\frac{\pi}{2})
\end{equation*}
resp.
\begin{equation*}
c_n(x,b)=i^nn!P_n^{(\frac{b}{2})}(-\frac{ix}{2},\frac{\pi}{2}),
\end{equation*}
where $P_n^{(\lambda)}(x,\phi)$ are the Meixner-Pollaczek polynomials from (\ref{meixner}). As a consequence the diophantine
result from \cite[Theorem 4.4]{tichy} on (\ref{diophantine}) can be generalized as follows:

The diophantine equation
\begin{equation}
\overline{c}_n(x;b)=\overline{c}_m(y;b),\ b\in\N
\end{equation}
where $\overline{c}_k(x;b)=\frac{1}{k!}c_k(x;b)$ is the average number of colourings of a permutation in
$\mathcal{P}_{k;a,b}$, has for $n,m\geq3$, $n\not\equiv m\pmod 2$ only a finite number of integer solutions.

\begin{thebibliography}{99}
\bibitem{askey}
G.~E.~\textsc{Andrews}, R.~\textsc{Askey}.
\newblock \emph{ Classical orthogonal polynomials}.
\newblock Polynomes orthogonaux et applications, Proc. Laguerre Symp., Bar-le- Duc/France 1984, Lect. Notes Math. %%@
\textbf{1171}, 36-62 (1985).

\bibitem{assche}
W.~\textsc{Van Assche}.
\newblock \emph{Orthogonal polynomials in the complex plane and on the real line}.
\newblock Ismail, Mourad E. H. (ed.) et al., Special functions, $q$-series and related topics. Providence, RI: American
Mathematical Society. Fields Inst. Commun. \textbf{14}, 211-245 (1997).

\bibitem{baker}
A.~\textsc{Baker}.
\newblock \emph{Bounds for the solutions of the hyperelliptic equation}.
\newblock Proc. Camb. Philos. Soc. \textbf{65}, 439-444 (1969).

\bibitem{comtet}
L.~\textsc{Comtet}.
\newblock \emph{Advanced combinatorics : the art of finite and infinite expansions}.
\newblock Revised and enlarged edition. Dordrecht, Holland - Boston, U.S.A.: D. Reidel Publishing Company. X, 343 S. (1974).

\bibitem{favard}
J.~A.~\textsc{Favard}
\newblock \emph{Sur les polynomes de Tchebicheff}.
\newblock C. R. Acad. Sci., Paris \textbf{200}, 2052-2053 (1935).

\bibitem{lewis}
H.~\textsc{Davenport}, D.~J.~\textsc{Lewis}, A.~\textsc{Schinzel}.
\newblock \emph{Equations of the form $f(x) = g(y)$}.
\newblock Q. J. Math., Oxf. II. Ser. \textbf{12}, 304-312 (1961).

\bibitem{tichy}
P.~\textsc{Kirschenhofer}, A.~\textsc{Peth\H o}, R.~F.~\textsc{Tichy}.
\newblock \emph{On analytical and diophantine properties of a family of counting polynomials}.
\newblock Acta Sci. Math. \textbf{65}, 47-59 (1999).

\bibitem{koekoek}
R.~\textsc{Koekoek}, R.~F.~\textsc{Swarttouw}.
\newblock \emph{The Askey-scheme of hypergeometric orthogonal polynomials and its q-analogue}.
\newblock http://aw.twi.tudelft.nl/\~{}koekoek/askey/index.html

\bibitem{meixner}
J.~\textsc{Meixner}.
\newblock \emph{Orthogonale Polynomsysteme mit einer besonderen Gestalt der erzeugenden Funktion}.
\newblock J. London Math. Soc. \textbf{9} 6-13 (1934).

\bibitem{strehl}
V.~\textsc{Strehl}.
\newblock \emph{Zykel-Enumeration bei lokal-strukturierten Funktionen}.
\newblock Habilitationsschrift. Universit\"at Erlangen-N\"urnberg. 307 S. (1990).

\bibitem{wilf}
H.~S.~\textsc{Wilf}.
\newblock \emph{generatingfunctionology}.
\newblock Boston [u.a.]: Academic Press. VIII, 184 S. (1990).
\end{thebibliography}
\bibliographystyle{plain}
\end{document}