# Discrete Math Problem! HELP!!

Printable View

• Mar 25th 2008, 08:43 PM
jzellt
Discrete Math Problem! HELP!!
Let m,n be positive integers. An m x n chessboard is a rectangle of length m and height n that is divided into mn squares of length 1. For example, a stardard chessboard is 8 x 8. A rectangle on a chessboard, is a rectangle all of whose sides are made up of sides of the 1 x 1 squares.

How many rectangles are there on an m x n chessboard? For example, when m = n = 2, then the answer is 9.

I just don't know where to begin! Any help is greatly appreciated. Thanks.
• Mar 30th 2008, 11:48 AM
mskia
You are able to put numbers standing by each vertical and horizontal line of the chessboard. Just like what I am doing below,
[HTML]
1 2 3
--- ---
| | |
2 --- ---
| | |
3 --- ---
[/HTML]
Then I can say for the longer border of rectangle, I have 3 pairs of start and end points, since picking up 2 numbers from 3 numbers has 3 possibilities, they are 12, 13, 23.

Similarly, I also have 3 choices when facing the situation of the shorter border of the rectangle. The possible combinations are 12, 13, 23.

So, for the rectangle permutation, I have 9 choices, they are 12-12, 12-13, 12-23, 13-12, 13-13, 13-23, 23-12, 23-13, 23-23. They are exactly the answers to your example question.

For general cases, just think about it in the same way, then you may come to the conclusion that
[HTML]
-- 2 -- 2 m! n!
Answer = | x | = ------------------------
-- m -- n 2！ 2！ (m-2)! (n-2)!
[/HTML]