Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am stuck with the following problem. Every polynomial of degree $d$ can be expressed as $$ p(x) = p_d \cdot \binom{x}{d}+ p_{d-1} \cdot \binom{x}{d-1} + \cdots + p_0 \binom{x}{0} $$ What is the representation of : $$ \binom{x}{i} \cdot \binom{x}{j} $$ in such a basis?

I have no idea how to solve this...

share|improve this question
1  
The coefficients are the divided differences. See en.wikipedia.org/wiki/Newton_polynomial. –  lhf Nov 10 '12 at 14:16
add comment

1 Answer

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, and assume $j\geq i, x\geq i+j$. 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}.$$

share|improve this answer
add comment

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.