Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
3  
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

2 Answers 2

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

share|improve this answer

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.

share|improve this answer
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.