BdMO Online Forum

Prove that
\[2{m \choose 2}{n \choose 2}={mn \choose 2}-n{m \choose 2}-m{n \choose 2}\]

Here's a Combinatorial argument:
Consider a $m \times n$ chessboard. Now we want to place $2$ rooks such that no two rooks attack each other. In how many ways can we do that?

We count it in two different ways. The first way is to choose the rows and columns. First we choose $2$ rows from the $m$ rows. Then we choose $2$ columns from the $n$ columns. This can be done in ${m \choose 2}{n \choose 2}$ ways. In this procedure, we get 4 unique squares. So, we can choose any $2$ squares from this $4$ squares that are not in the same row or column. This can be done in $2$ ways as we cannot choose the two squares in the same row or column. Finally we can place the rooks in $2{m \choose 2}{n \choose 2}$ ways.

Now we are going to count this a little differently. First there are $mn$ squares in the chessboard. We choose any two squares from this squares. This can be done in ${mn \choose 2}$ ways. Now we subtract the cases where the squares are in the same row or column. We consider two cases. In the first case, the squares are in the same column. In any column the squares can be chosen in ${m \choose 2}$ ways. There are $n$ columns. So the total number is $n{m \choose 2}$. In the second case, where no two rooks are in the same row, a similar argument yields the number of ways to place the rooks which is $m{n \choose 2}$. Subtracting this we get

${mn \choose 2} - n{m \choose 2} - m{n \choose 2}$

And we're done.

Nice one.Try the 3 variable form:
\[4{a \choose 2}{b \choose 2}{c \choose 2}={abc \choose 2}-a{bc \choose 2}-b{ac \choose 2}-c{ab \choose 2}+ab{c \choose 2}+bc{a \choose 2}+ca{b \choose 2}\]

argument is as same as prosenjit .
but this time , just think about a $a\cdot b\cdot c$ cube .
we want to place two rooks such that they are not in the same plane .
and in $R.H.S$ a little bit of inclusion and exclusion is needed