Question

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.

Answer 1

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

Answer 2

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.