Skip to main content
1 of 4
Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402

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

Gjergji Zaimi
  • 85.6k
  • 4
  • 236
  • 402