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

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 = 9C2 * 9C2

answered by (5.7k points) 7 22 138
selected

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) + n2

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

answered by (236 points) 5 12