number of rectangles

Question

The number of rectangles that can be formed on a 8x8 chessboard

Comments

https://math.stackexchange.com/questions/178693/analysis-of-how-many-squares-and-rectangles-are-are-there-on-a-chess-board

Answer 1

This is a 8x8 chessboard

We can clearly see that it consists of 8 Rows & 8 Columns. And 8 Rows & 8 Columns result in 9 Horizontal Lines & 9 Vertical Lines.

To form a rectangle we have to select 2 Horizontal lines out of 9 Horizontal lines & 2 Vertical lines out of 9 vertical lines.

So, total number of rectangles Iin this 8x8 chessboard = ⁹C₂ * ⁹C₂

 

Answer 2

Suppose a block of 1 x 1,

How many squares it can form? 
Only 1 

But if we increment by 1 (2 x 2)? 
4 (1 x 1) and 1 (2 x 2 ) = 5 squares

and similarly for 3 x 3 there are 1 square (3 x 3), 4(2 x 2) and 9 (1 x 1)
total 1 + 4 + 9 = 14 squares

We can form a recurrence relation,

T(n) = T(n-1) + n²

T(3) = T(2) + 9 = 5 + 9 = 14 

but what about T(8)? we need T(7) for that and hence we need a closed formula

which is nothing but

T(n) = $n^{2} + (n-1)^{2} + (n-2)^{2}+ ....+ 2^{2} + 1^{2}$ = $\frac{n(n+1)(2n+1)}{6}$

T(8) = $\frac{8(8+1)(16+1)}{6}$ = $12 * 17$ = 204