1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ You can find some answers using combinatorial arguments also in this recent question on the same topic. $\endgroup$ Commented Oct 8, 2016 at 11:07

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ makes sense, thanks. But what about this proof makes it combinatorial? $\endgroup$
    – Luke
    Commented Oct 20, 2015 at 8:43
  • $\begingroup$ To me, "combinatorial" means that the quantities in the question are interpreted as the cardinalities of some sets, rather than as algebraic formulas. $\endgroup$ Commented Oct 20, 2015 at 8:47
  • $\begingroup$ Take a example and then see whether it gives the same as i hardly think there exists a formula $\endgroup$ Commented Nov 6, 2015 at 12:37
1
$\begingroup$

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*}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .