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...
 A: 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}.$$
A: In reply to this post, which has been closed as being a duplicate
of the present one, let me submit an alternative formulation, which looks more symmetrical as requested in the mentioned post.
Starting from
$$
\eqalign{
  & x^{\,\underline {\,n\,} } x^{\,\underline {\,m\,} }  = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)}
  {\left( { - 1} \right)^{\,n - k} \left[ \matrix{  n \cr   k \cr}  \right]x^{\,k} }
  \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,m} \right)}
  {\left( { - 1} \right)^{\,m - j} \left[ \matrix{  m \cr   j \cr}  \right]x^{\,j} }  =   \cr 
  &  = \left( { - 1} \right)^{\,n + m} \sum\limits_{\left( {0\, \le } \right)\,q\,\left( { \le \,n + m} \right)}
  {\left( {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,\min \left( {q,n} \right)} \right)}
  {\left( { - 1} \right)^{\,q} \left[ \matrix{  n \cr   k \cr}  \right]
  \left[ \matrix{  m \cr   q - k \cr}  \right]} } \right)x^{\,q} }  =   \cr 
  &  = \left( { - 1} \right)^{\,n + m} \sum\limits_{\left( {0\, \le } \right)\,q\,\left( { \le \,n + m} \right)}
  {\left( {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,\min \left( {q,n} \right)} \right)}
  {\left( { - 1} \right)^{\,q} \left[ \matrix{  n \cr   k \cr}  \right]
  \left[ \matrix{  m \cr   q - k \cr}  \right]} } \right)
  \sum\limits_{\left( {0\, \le } \right)\,s\,\left( { \le \,q} \right)}
  {\left\{ \matrix{  q \cr   s \cr}  \right\}\,x^{\,\underline {\,s\,} } } }  =   \cr 
  &  = \left( { - 1} \right)^{\,n + m} \sum\limits_{\left( {0\, \le } \right)\,s\,\left( { \le \,m + n} \right)}
  {\left( {\sum\limits_{\left( {s\, \le } \right)\,q\,\left( { \le \,n + m} \right)}
  {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,\min \left( {q,n} \right)} \right)}
  {\left( { - 1} \right)^{\,q} \left[ \matrix{  n \cr   k \cr}  \right]
  \left[ \matrix{  m \cr  q - k \cr}  \right]
  \left\{ \matrix{  q \cr   s \cr}  \right\}} } } \right)x^{\,\underline {\,s\,} } }  =   \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,s\,\left( { \le \,m + n} \right)} {F(n,m,s)\,x^{\,\underline {\,s\,} } }  \cr} 
$$
and putting that into matricial form I could deduce that
$$ \bbox[lightyellow] {  
F(n,m,s) = \left( {n + m - s} \right)!\binom{  m }{   s - n } \binom{  n}{   s - m }
\quad \left| \matrix{  \;0 \le n,m,s \in \mathbb Z \hfill \cr   \;s \le n + m \hfill \cr}  \right.
 }$$
In fact, that is proved by being
$$
\eqalign{
  & \sum\limits_{\left( {0\, \le } \right)\,s\, \le \,m + n} {\left( {n + m - s} \right)!
 \binom{  m }{   s - n } \binom{  n }{  s - m }\,x^{\,\underline {\,s\,} }}  = \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,s\, \le \,m + n} 
 {\left( {n + m - s} \right)!
 \binom{  m }{  n + m - s } \binom{  n }{  s - m }\,
 x^{\,\underline {\,m + \left( {s - m} \right)\,} } } =    \cr 
  &  = \sum\limits_{\left( {0\, \le } \right)\,s\, \le \,m + n}
 {\binom{  n}{   s - m } m^{\,\underline {\,n - \left( {s - m} \right)\,} } \,
 x^{\,\underline {\,m\,} } \left( {x - m} \right)^{\,\underline {\,s - m\,} } }  =    \cr 
  &  = x^{\,\underline {\,m\,} } \sum\limits_{\left( {0\, \le } \right)\,k\, \le \,n}
 {\binom{  n }{   k } m^{\,\underline {\,n - k\,} } \,\left( {x - m} \right)^{\,\underline {\,k\,} } }  =    \cr 
  &  = x^{\,\underline {\,m\,} } x^{\,\underline {\,n\,} }   \cr} 
$$
where:
 (1st step) binomial symmetry;
 (2nd) reducing the first binomial and splitting the falling factorial;
 (3rd) changing summation index;
 (4th) binomial expansion of falling factorial. 
$F(n,m,s)$ is called "connection  coefficient" in this Wikipedia article 
The conversion to the product of binomials follows immediately.
