# 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}$?

#### Solutions Collecting From Web of "Expand $\binom{xy}{n}$ in terms of $\binom{x}{k}$'s and $\binom{y}{k}$'s"

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 beautiful combinatorial answer was found by Gjergji Zajmi. For an expanded version, see the solution to Exercise 3 in my Notes on the combinatorial fundamentals of algebra. (At least, it is Exercise 3 in the version of 4 September 2016. 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.

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.