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.

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