An interesting combinatorial identity

For discussing Olympiad Level Combinatorics problems
User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am
An interesting combinatorial identity

Unread post by Thanic Nur Samin » Mon Mar 30, 2015 6:06 pm

Prove that
\[2{m \choose 2}{n \choose 2}={mn \choose 2}-n{m \choose 2}-m{n \choose 2}\]
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Prosenjit Basak
Posts:53
Joined:Wed Nov 28, 2012 12:48 pm

Re: An interesting combinatorial identity

Unread post by Prosenjit Basak » Tue Mar 31, 2015 9:31 pm

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.
Yesterday is past, tomorrow is a mystery but today is a gift.

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: An interesting combinatorial identity

Unread post by Thanic Nur Samin » Wed Apr 01, 2015 6:10 pm

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}\]
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Tahmid
Posts:110
Joined:Wed Mar 20, 2013 10:50 pm

Re: An interesting combinatorial identity

Unread post by Tahmid » Fri Apr 24, 2015 12:21 am

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 :)

Post Reply