Prove using a combinatorial argument the following statement: $\binom{n+m}{2} = \binom{m}{2} + \binom{n}{2} + \binom{n}{1}\binom{m}{1}$

Question

$$\binom{n+m}{2} = \binom{m}{2} + \binom{n}{2} + \binom{n}{1}\binom{m}{1}$$

I already proved this algebraically by using the formula for choose, but I don't know what exactly the question means by "combinatorial" and don't know how to start.

Thanks.

Answer 1

Consider an $m$-element set $M$ and an $n$-element set $N$ such that $M\cap N=\varnothing$, so $M\cup N$ is an $(m+n)$-element set. The left side of your equation is the number of $2$-element subsets of $M\cup N$. These $2$-element subsets are of $3$ sorts: subsets of $M$, subsets of $N$, and subsets consisting of one element from $M$ and one from $N$. There are $m$ choose $2$ sets of the first sort, $n$ choose $2$ of the second, and $m\cdot n$ of the third.

Answer 2

I am not sure whether this counts as a combinatorial argument, but if you know that this is triangular number: $$T_{n-1}=\binom n2= 1+2+\dots+(n-1)$$ You can see this from picture that $$T_{m-1}+T_{n-1}+mn=T_{m+n-1}.$$

Or simply by rewriting the sums: \begin{align*} \binom {m+n}2 &= 1+2+\dots+(m-1)+m+(m+1)+\dots+(m+n-1)\\ &= 1+2+\dots+(m-1)+(m\cdot n)+1+\dots+n-1\\ &=\binom m2+mn+\binom n2 \end{align*}