Intereting Posts

Is $n! + 1$ often a prime?
Prove that a sequence is a Cauchy sequence.
How many solutions has the equation $\sin x= \frac{x}{100}$ ?
How does linear algebra help with computer science
Examples of Diophantine equations with a large finite number of solutions
Two conjectures of four squares
Irreducibility of $x^{p^r} – a$ if $a$ is not a $p$-th power.
Is there a non-constant function $f:\mathbb{R}^2 \to \mathbb{Z}/2\mathbb{Z}$ that sums to 0 on corners of squares?
Prob. 1, Sec. 27 in Munkres' TOPOLOGY, 2nd ed: How to show that the compactness of every closed interval implies the least upper bound property?
Discontinuities of the derivative of a differentiable function on closed interval
Show that the product of two consecutive natural numbers is never a square.
Is it possible to generalize Ramanujan's lower bound for factorials when $\{\frac{x}{b_2}\} + \{\frac{x}{b_3}\} < 1$?
What is known about these arithmetical functions?
there exist infinite many $n\in\mathbb{N}$ such that $S_n-<\frac{1}{n^2}$
Finding the ring of integers of $\mathbb Q$ with $\alpha^5=2\alpha+2$.

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

- The empty function and constants
- Category with zero morphisms
- why is this composition well defined?
- If $\operatorname{Hom}(X,-)$ and $\operatorname{Hom}(Y,-)$ are isomorphic, why are $X$ and $Y$ isomorphic?
- In what sense is the forgetful functor $Ab \to Grp$ forgetful?
- Preserving structures

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

- inductive proof for $\binom{2n}{n}$
- Combinatorial proof of the identity ${n+1\choose k+1}={k\choose k}+{k+1\choose k}+…+{n-1\choose k}+{n\choose k}$
- Evaluating even binomial coefficients
- $p$ divides $ax+by+cz$
- A question related to Pigeonhole Principle
- Kan extensions for linear categories
- Sum of combinations of the n by consecutive k
- Solutions to Binary Equations
- Inside a card deck there are 52 cards with 4 colors, 13 cards for each color
- Covering with most possible equal size subsets having pairwise singleton intersections

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.

- Mathematics applied to biology
- Testing whether a hypersurface is singular
- Need verification – Prove a Hermitian matrix $(\textbf{A}^\ast = \textbf{A})$ has only real eigenvalues
- Is there any abstract theory of electrical networks?
- What is wrong with this proof that there are no odd perfect numbers?
- Do the Kolmogorov's axioms permit speaking of frequencies of occurence in any meaningful sense?
- Prove that 1+1=2
- How did “one-to-one” come to mean “injective”?
- Sum the infinite series
- $n \mid (a^{n}-b^{n}) \ \Longrightarrow$ $n \mid \frac{a^{n}-b^{n}}{a-b}$
- For a $C^1$ function, the difference $|{g'(c)} – {{g(d)-g(c)} \over {d-c}} |$ is small when $|d-c|$ is small
- What is the largest perfect square that divides $2014^3-2013^3+2012^3-2011^3+\ldots+2^3-1^3$
- Always a double root between “no roots” and “at least one root”?
- Proving $\kappa^{\lambda} = |\{X: X \subseteq \kappa, |X|=\lambda\}|$
- Showing that $X^2$ and $X^3$ are irreducible but not prime in $K$