A generalization of the Vandermonde's convolution I need to find a closed formula for the following sum:
\begin{equation}
\sum_{i=0}^{n}i^{k}\left(\begin{array}{c}
n\\
i
\end{array}\right)\left(\begin{array}{c}
n^{2}-n\\
c-i
\end{array}\right)
\end{equation}
It is a sort of Vandermonde's convolution, and in particular I know that for $k=1$ the result should be:
\begin{equation}
\frac{c}{n}\left(\begin{array}{c}
n^{2}\\
c
\end{array}\right)
\end{equation}
Many thanks in adavance for any help you can provide!
EDIT:
I think the solution should be something similar to formula (6.18) at this link, even if my case is slightly more general because $c\neq n$.
According to Maple:
$k = 1$: $\frac{n\Gamma\left(n^{2}\right)}{\Gamma\left(c\right)\Gamma\left(n^{2}-c+1\right)}$,
$k = 2$: $\frac{n\left(n+c\right)\Gamma\left(n^{2}\right)}{\left(n+1\right)\Gamma\left(c\right)\Gamma\left(n^{2}-c+1\right)}$,
$k = 3$: $\frac{n\left(3n^{2}c-3nc+n^{3}-2n^{2}-2c^{2}+nc^{2}\right)\Gamma\left(n^{2}\right)}{\left(n^{2}-2\right)\left(n+1\right)\Gamma\left(c\right)\Gamma\left(n^{2}-c+1\right)}$ etc.
 A: We'll find something more general: we'll find 
$$\sum_{i} f(i) \binom{n}{i}\binom{m}{c-i},$$
where $f$ is a polynomial, with your problem the special case $m = n^2 - n$ and $f(i) = i^k$. 
[A note on the range of the index $i$: The summation runs over all integers $i$, but as $\binom{a}{b}$ for integers $a \ge 0$ and $b$ is nonzero only when $0 \le b \le a$, the only $i$ that matter are those satisfying $0 \le i \le n$ and $0 \le c-i \le m$, or in other words $\max(0, c-m) \le i \le \min(n, c)$, so it's the same as your sum.]
Note that, when the polynomial $f$ is itself a "binomial coefficient" $x \mapsto \binom{x}{r} = \frac{x(x-1)\dots(x-r+1)}{r!}$, we have 
$$\sum_i \binom{i}{r}\binom{n}{i}\binom{m}{c-i} = \binom{n}{r}\binom{n+m-r}{c-r}.$$
There is a combinatorial proof of this, just in the case of the Vandermonde convolution: suppose you want to make a club of $c$ people out of $n$ women and $m$ men, that includes a special women's group of $r$ people. You can count the number of ways of doing this by either 


*

*[left-hand side] counting all possible number of women $i$ that will be in your club, and then counting ways of picking the women's group from the $i$ women ($\binom{i}{r}$), picking the $i$ women $(\binom{n}{i}$), and picking the $c - i$ men ($\binom{m}{c-i}$), or

*[right-hand size] count the number of ways of picking the women's group first ($\binom{n}{r}$), and then the number of ways of picking the remaining $c-r$ members of the club from the remaining $n-r+m$ people ($\binom{n+m-r}{c-r}$).

Now for any polynomial $f$, instead of writing its coefficients $a_r$ in the usual "powers" basis of monomials (writing $f(x) = \sum_{r} a_r x^r$), we can write its coefficients in the "binomial coefficient" basis of monomials (related to the "falling factorial" basis), i.e. we can write $f(x) = \sum_{r} b_r \binom{x}{r}$. If we do that, then the sum we want becomes
$$
\sum_{i}f(i)\binom{n}{i}\binom{m}{c-i} 
= \sum_{i} (\sum_{r} b_r \binom{i}{r}) \binom{n}{i}\binom{m}{c-i} 
= \sum_r b_r (\sum_i \binom{i}{r}\binom{n}{i}\binom{m}{c-i}) 
= \sum_r b_r \binom{n}{r}\binom{n+m-r}{c-r}
$$
In general, the representation of a polynomial $f$ in the binomial-coefficient basis is given by the coefficients
$$ b_r = \sum_{j=0}^r (-1)^{r-j}\binom{r}{j}f(j),$$
whose special case when $f$ is the polynomial $f(x) = x^k$ is what we are interested in.

Putting it all together, the answer you want is 
$$\boxed{\displaystyle \sum_{i}i^k \binom{n\vphantom{n^2}}{i} \binom{n^2 - n}{c-i} 
= \sum_{r=1}^k \binom{n\vphantom{n^2}}{r}\binom{n^2-r}{c-r} \left(\sum_{j=1}^r (-1)^{r-j}\binom{r}{j}j^k\right)}$$
which may not look like a simplification, but is a sum over only $k$ terms (or, if you include the inner sum, $O(k^2)$ terms) instead of $n$.
(I took the inner sum to start at $j=1$ instead of $j=0$, because assuming that $k \ge 1$, the $j=0$ term has a $j^k = 0$ factor which makes the whole thing zero, so we can leave it out. Similarly the $r=0$ term in the outer term. In fact, the inner sums for different $r$ are $b_0 = 0$, $b_1 = 1$, $b_2 = -2 + 2^k$, $b_3 = 3 - 3(2^k) + 3^k$, $b_4 = -4 + 6(2^k) - 4(3^k) + 4^k$, etc.)
The expressions for the first few $k$ are:


*

*$k=1$ gives $n\binom{n^2 - 1}{c - 1}$

*$k=2$ gives $n\binom{n^2 - 1}{c - 1} + \binom{n}{2}\binom{n^2-2}{c-2}(2)$

*$k=3$ gives $n\binom{n^2 - 1}{c - 1} + \binom{n}{2}\binom{n^2-2}{c-2}(6) + \binom{n}{3} \binom{n^2-3}{c-3} (6)$
Further simplification may be possible.
