Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
1  
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}.$$

share|cite|improve this answer

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.