Non-arithmetic proof of the integrality of a rational expression

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

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

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.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

For discussion on these coefficients $c(n,k)$, take a look at this paper "The $p$-adic valuation of $k$-central binomial coefficients", joint work with V H Moll and A Straub.