Prove that
\[2{m \choose 2}{n \choose 2}={mn \choose 2}-n{m \choose 2}-m{n \choose 2}\]
An interesting combinatorial identity
- Thanic Nur Samin
- Posts:176
- Joined:Sun Dec 01, 2013 11:02 am
Hammer with tact.
Because destroying everything mindlessly isn't cool enough.
Because destroying everything mindlessly isn't cool enough.
-
- Posts:53
- Joined:Wed Nov 28, 2012 12:48 pm
Re: An interesting combinatorial identity
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.
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.
- Thanic Nur Samin
- Posts:176
- Joined:Sun Dec 01, 2013 11:02 am
Re: An interesting combinatorial identity
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}\]
\[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.
Because destroying everything mindlessly isn't cool enough.
Re: An interesting combinatorial identity
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
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