Expand $\binom{xy}{n}$ in terms of $\binom{x}{k}$'s and $\binom{y}{k}$'s Motivated by this question, I want to find a complete set of relations for the ring of integer-valued polynomials, where the generators are the polynomials $\binom{x}{n}$ for $n\in \mathbb{N}$. The best way to do this is would be to describe how to decompose $\binom{x+y}{n}$ and $\binom{xy}{n}$ as a sum of products of $\binom{x}{0},\dots, \binom{x}{n}$ and $\binom{y}{0},\dots,\binom{y}{n}$. This can be done in principle by peeling off the binomials starting with the highest degree and working one's way down. Playing around with Sage, one soon guesses that
$\binom{x+y}{n} = \sum_{k=0}^n \binom{x}{k}\binom{y}{n-k}$
and in fact, I think this has a combinatorial proof which straightforwardly generalizes that of the identity $\binom{m}{n} = \binom{m}{n-1} + \binom{m-1}{n-1}$.
But $\binom{xy}{n}$ seems to be not so straightforward. The first few expansions are:
$\binom{xy}{2} = 2\binom{x}{2}\binom{y}{2} + x\binom{y}{2} + y \binom{x}{2}$
$\binom{xy}{3} = 6\binom{x}{3} \binom{y}{3} + $
$\qquad ~ ~ 6 \binom{x}{3}\binom{y}{2} + 6\binom{x}{2}\binom{y}{3} + $
$\qquad ~ ~ x \binom{y}{3} + 4 \binom{x}{2} \binom{y}{2} + y \binom{x}{3}  $
$\binom{xy}{4} = 24\binom{x}{4}\binom{y}{4} + $
$\qquad ~ ~ 36\binom{x}{3}\binom{y}{4} + 36 \binom{x}{4}\binom{y}{3} + $
$ \qquad ~ ~ 14 \binom{x}{2}\binom{y}{4} + 45\binom{x}{3}\binom{y}{3} + 14 \binom{x}{4}\binom{y}{2} + $
$\qquad ~ ~ 12 \binom{x}{2}\binom{y}{3} + 12 \binom{x}{3}\binom{y}{2} + $
$\qquad ~ ~ \binom{x}{2}\binom{y}{2}$
and it is not so easy to discern a pattern.
This must be well-known: what is a closed-form expression for the expansion of $\binom{xy}{n}$?
 A: The identity $\binom{x+y}{n} = \sum_{k=0}^{n} \binom{x}{k} \binom{y}{n-k}$ is well-known, it is called the Vandermonde identity. The answer for $\binom{xy}{n}$ can be explained using the notion of a $\lambda$-ring, where here we consider the binomial ring $\mathbb{Z}$ with $\lambda^n(x)=\binom{x}{n}$. The main theorem on symmetric polynomials enables us to write
$$\sum_{k=0}^{n} P_k(\sigma_1,\dotsc,\sigma_k,\tau_1,\dotsc,\tau_k) \,t^k = \prod_{i,j=1}^{n} (1+ t x_i y_j)$$
for some polynomials $P_k \in \mathbb{Z}[x_1,\dotsc,x_k,y_1,\dotsc,y_k]$, where $\sigma_1,\dotsc,\sigma_n$ are the elementary symmetric polynomials in $x_1,x_2,\dotsc,x_n$ and $\tau_1,\dotsc,\tau_n$ are the elementary symmetric polynomials in $y_1,\dotsc,y_n$. Then, one has  (by definition) $$\lambda^n(xy)=P_n\bigl(\lambda^1(x),\dotsc,\lambda^n(x),\lambda^1(y),\dotsc,\lambda^n(y)\bigr).$$
For example:
$$\lambda^2(xy) = x^2 \lambda^2(y) + \lambda^2(x) y^2 - 2 \lambda^2(x) \lambda^2(y)$$
$$\lambda^3(xy)=x^3 \lambda^3(y) + \lambda^3(x) y^3 + x \lambda^2(x) y \lambda^2(y) - 3 x \lambda^2(x) \lambda^3(y) - 3 \lambda^3(x) y \lambda^2(y) + 3 \lambda^3(x) \lambda^3(y)$$
Of course, one has to prove that every binomial ring becomes a $\lambda$-ring. See for instance  Darij Grinberg's notes, Theorem 7.2 (which is a corollary of Theorem 7.1).
A: A beautiful combinatorial answer was found by Gjergji Zajmi. For an expanded version, see the solution to Exercise 3.9 in my Notes on the combinatorial fundamentals of algebra. (At least, it is Exercise 3.9 in the version of 10 January 2019. In future versions, the numbering can shift.)
Unlike Martin's answer, this one directly gives a formula for $\dbinom{xy}{n}$ as a nonnegative linear combination of products $\dbinom{x}{k}\dbinom{y}{\ell}$, as opposed to a polynomial in the $\dbinom{x}{k}$ and the $\dbinom{y}{\ell}$. This, of course, does not work for arbitrary $\lambda$-rings.
A: There's another formula for the expression in equation (3) on the bottom of page 183 of my paper here: http://www.sciencedirect.com/science/article/pii/S0022404905002161 
The formula is ${{xy} \choose n} = \underset{l_1 + 2 l_2 + \cdots + nl_n = n}{\sum}  {{\sum_{i=1}^n l_i} \choose {l_1, l_2, \ldots, l_n}} {y \choose {\sum_{i=1}^n l_i}} \prod_{i=1}^n {x \choose l_i}$, proved by expanding $(1+T)^{xy} = ((1+T)^x)^y$ using the binomial and multinomial theorems.
