# Non-arithmetic proof of the integrality of a rational expression

The following expression is an integer for any natural $$n,k$$ $$c(n,k)=\frac{k^n\prod_{m=0}^{n-1}(1+mk)}{n!}.$$ The generating function for these numbers is $$\sum_{n\geq 0} c(n,k)x^n=(1-k^2x)^{-1/k}$$, a generalization of the generating function for central binomial coefficients $$\sum_{n\geq 0} \binom{2n}{n}x^n=\frac{1}{\sqrt{1-4x}}.$$

Is there any other way to prove that $$c(n,k)$$ are integers, besides comparing the powers of $$p$$ dividing the numerator and denominator? Do these numbers have a combinatorial meaning for $$k\geq 3$$?

Notice that the expression $$\frac{k^{\binom{n}{2}}\prod_{m=0}^{n-1}(1+km)}{n!}$$ counts the number of non-intersecting paths (in $$\mathbb Z^2$$) from the sources $$\{(-i,0)\} _{i=1}^n$$ to the sinks $$\{ (k-1-j,j) \} _{j=1} ^n$$, which means it is equal to the determinant of a matrix with entries $$a _{ij}=\binom{k-1+i}{j}$$, but the exponent of $$k$$ is to high.

Remark 1: I have seen the argument above in the context of the nice little identity $$\prod_{1\le i < j\le n}\frac{a _j-a _i}{j-i}=\det \left(\binom{a_i}{j-1}\right) _{1\le i,j\le n}.$$

Remark 2: The paper that Steve mentions says that in fact $$\frac{c(n,k)}{k}$$ is an integer for $$n\geq 1$$. Unfortunately it doesn't seem to a give proof of this fact, except for showing that these numbers are related to certain other sequences of rational expressions which take integer values. The questions I ask here probably apply to those sequences as well, k-Stirling numbers, k-Catalan numbers etc. In fact I've seen a paper that calls the $$c(n,k)$$, k-central binomial coefficients.

• Gjergji, you ask a question somehow mentioned in Timothy's response to my post mathoverflow.net/questions/26336. – Wadim Zudilin May 30 '10 at 11:50
• I was secretly hoping this would be simpler than the hard questions you asked in the other thread. I still have to check the links in that response and the comments carefully though. – Gjergji Zaimi May 30 '10 at 12:01
• In fact, Timothy responses more to your question rather than mine. The article from the Fibonacci Quart. he mentions can be downloaded from the author's webpage, but it's about an algorithm. I like your example (with meaning +1 :) ), as it has a combinatorial interpretation "up to a power of $k$". – Wadim Zudilin May 30 '10 at 12:10
• I've wondered this as well. Is there a natural equivalence relation on non-intersecting paths which might reduce the exponent of k? – Qiaochu Yuan May 30 '10 at 21:48
• Without the factor of $k^n/n!$ your expression counts $(k+1)$-ary increasing trees. See for example Bergeron, Flajolet, and Salvy, "Varieties of increasing trees," in CAAP '92 (LNCS vol. 581). This doesn't immediately answer your question but it might be a place to start looking for a combinatorial interpretation. – Timothy Chow May 31 '10 at 20:38

The generating function $g(x):=(1−k^2 x)^{-1/k}$ satisfies, besides $g(0)=1,$

$g^k= 1 + k^2 x\ g^k$,

whence we may express $c(k,n)$ as a sum of products of $c(k,j)$, with $j < n$, showing inductively that they are all integers, and in fact, multiples of $k$ for $n>0$.

Indeed, hiding the variable $k$ in $c(k,n)=c(n)$, one has

$c(0)=1$, $c(1)=k$

and in general for n>1,

$c(n)= k\sum_\mu c(\mu_1)c(\mu_2)..c(\mu_k) - \frac{1}{k}\sum_\nu c(\nu_1)c(\nu_2)..c(\nu_k)$

the first sum being extended over all multi-indices $\mu\in \mathbb{N}^k$ with weight $|\mu|:=\mu_1+\mu_2\dots +\mu_k=n-1$, while the second over all $\nu\in \mathbb{N}^k$ with $|\nu|=n$ and $\nu_j< n$ for $j=1\dots k$. It follows that if $c(j)$ are multiple of $k$ for $1 < j < n$, so is $c(n)$, and by induction this proves the claim. (The factor 1/k doesn't bother, because each term in the second sum contains at least 2 factors $c(j)$ with $0 < j < n$).

The integrality of the coefficients of $$(1-k^2x)^{-1/k}$$ follows from the integrality of the coefficients of the generalized Catalan number generating function $$c_k(x)=\frac{1-(1-k^2 x)^{1/k}}{kx},$$ which has integer coefficients since the compositional inverse of $$xc_k(x)$$ is $$\frac{1-(1-kx)^k}{k^2}=x-\binom{k}2 x^2+k\binom{k}{3}x^3-\cdots$$ which clearly has integer coefficients.

• More generally, for any integers $a_1,\dots, a_k$, the coefficients of $$\frac{k}{(1-k^2x)^{a_1/k}+\cdots +(1-k^2x)^{a_k/k}}$$ are integers. – Ira Gessel Jul 22 at 4:01

See the bottom of page 8 of "On Generalizations of the Stirling Number Triangles" by Lang, where the $c(n,k) \equiv b^{(k)}_n$ are related to the so-called $k$-Catalan numbers.

• Hm, but where is a non-series (serious!) proof of the integrality of those $b_n^{(k)}$? – Wadim Zudilin May 30 '10 at 13:20

Here is a kind of fun observation which probably doesn't help. The quantity $$\frac{k-1}{k}\frac{2k-1}{2k}\cdots \frac{nk-1}{nk}$$ has an interpretation as the probability that an element of $$S_{nk}$$ has no cycle with length divisible by $$k$$. To get an interpretation of the quantity $$\pm\frac{1}{k}\frac{k+1}{2k}\cdots \frac{(n-1)k+1}{nk}$$ which is related to your quantity by a power of $$k$$, we should take the signed probability that an element of $$S_{nk}$$ has no cycle with length divisible by $$k$$ (i.e. count such elements with a sign according to the sign of the partition, then divide by the order $$(nk)!$$ of the group). Note that when $$k=2$$, the sign is always positive, since all cycles have odd length, which is why the two agree in this case.

This is probably equivalent or at least closely related to the argument using power series (which I think is the most natural one), but: I give a proof using induction and the Chu--Vandermonde identity in Notes on the combinatorial fundamentals of algebra, arXiv:2008.09862v1. More precisely, Theorem 7.63 of these notes says that if $$a$$ and $$b$$ are integers and $$n$$ is a positive integer, then \begin{align} \dfrac{1}{n!} \cdot a\left(a+b\right)\left(a+2b\right)\cdots\left(a+\left(n-1\right)b\right) \cdot b^{n-1} \in \mathbb{Z} . \label{darij1.1} \tag{1} \end{align} Your claim $$\dfrac{c\left(n,k\right)}{k} \in \mathbb{Z}$$ (for $$n \geq 1$$) follows by applying this to $$a = 1$$ and $$b = k$$.

The proof of \eqref{darij1.1} takes up basically the entire Subsection 7.34.2 of my notes, so it is not very short (although much of it is the level of detail). The idea is to rewrite \eqref{darij1.1} as $$b^{2n-1}\dbinom{a/b}{n} \in \mathbb{Z}$$, and to apply the Chu--Vandermonde identity to express $$\dbinom{ba/b}{n} = \dbinom{a/b+a/b+\cdots+a/b}{n}$$ as a polynomial in the $$\dbinom{a/b}{k}$$ (Lemma 7.60), allowing a proof by strong induction on $$n$$.