# 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 2$. 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$).

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