# Product of binomial coefficient as a basis

I am stuck with the following problem. Every polynomial of degree $d$ can be expressed as $$p(x) = p_d \binom{x}{d}+ p_{d-1}\binom{x}{d-1} + \cdots + p_0 \binom{x}{0}$$

What is the representation of $$\binom{x}{i} \binom{x}{j}$$ in such a basis?

I have no idea how to solve this...

-
The coefficients are the divided differences. See en.wikipedia.org/wiki/Newton_polynomial. – lhf Nov 10 '12 at 14:16
See Proposition 3.7 in my PRIMES 2015 problem collection ( cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf ). (If the numbering changes, search for "S-junction" and scroll up a bit. – darij grinberg Dec 4 '15 at 10:20

There is a nice combinatorial interpretation. The product $$\binom{x}{i}\cdot\binom{x}{j}$$ gives the number of ways in which one can select $i$ objects among $x$, then select $j$ objects among $x$. Let $I$ be the set of the elements chosen in the first instance, $J$ be the set of the elements chosen in the second one. In how many cases $I$ and $J$ are disjoint? We have to choose $i+j$ elements among $x$, then choose the elements of $I$ among the $i+j$ selected, so $I$ and $J$ are disjoint in: $$\binom{x}{i+j}\binom{i+j}{i}$$ cases. In how many cases we have $|I\cap J|=k\leq i$? The answer is clearly: $$\binom{x}{i+j-k}\binom{i+j-k}{k}\binom{i+j-2k}{i-k},$$ since we have to choose the $(i+j-k)$ elements that belong to $I\cup J$, which $k$ of these belong to $I\cap J$, which $i-k$ of the remaining belong to $I$. So we have: $$\binom{x}{i}\cdot\binom{x}{j}=\sum_{k=0}^{i}\binom{x}{i+j-k}\binom{i+j-k}{k}\binom{i+j-2k}{i-k}.$$