A chessboard problem

Consider the cell with coordinates $(x,y)$ (for $1 \le x,y \le 8$ ). A rectangle containing that cell will extend from column $u$ to column $v$ , and from row $p$ to row $q$ , where $1 \le u \le x \le v \le 8$ and $1 \le p \le y \le q \le 8$ . Thus there are $x(9-x)$ ways of choosing $u,v$ , and $y(9-y)$ ways of choosing $(p,q)$ . Thus the number in this cell will be $x(9-x)y(9-y)$ . Thus we want to evaluate $N \; = \; \sum_{x,y=1}^8 x(9-x)y(9-y) \; = \; \left(\sum_{n=1}^8x(9-x)\right)^2 \; = \; \left(9 \times \tfrac12\times8\times9 - \tfrac16\times8\times9\times17\right)^2 \; = \; 120^2 \; = \; \boxed{14400}$

First, define $\mathcal{R}$ as the set of all rectangles and $\mathcal{C}$ as the set of all cells. Then note that every rectangle $R \in \mathcal{R}$ can be identified as $R = [L,U]$ where $L,U \in \mathcal{C}$ are respectively the lower-left and upper-right cells of $R$ . Also, every cell $c \in \mathcal{C}$ can be identified by its coordinates $(c_x,c_y)$ on the board, where $1\leq c_x,c_y \leq 8.$

Then, $\begin{aligned} \sum_{c \in \mathcal{C}} \Big|\{R \in \mathcal{R} : R \text{ contains } c\}\Big| &= \Big|\{(R,c) \in \mathcal{R}\times\mathcal{C}: R \text{ contains } c\}\Big| \\ &= \Big|\{(L,U,c) \in \mathcal{C}^3 : L_x \leq c_x \leq U_x, L_y \leq c_y \leq U_y\}\Big| \\ &= \Big|\{L_x,L_y,U_x,U_y,c_x,c_y \in \mathbb{Z} : 1\leq L_x \leq c_x \leq U_x\leq 8, 1\leq L_y \leq c_y \leq U_y\leq 8\}\Big| \\ &= \Big|\{a,b,c \in \mathbb{Z} : 1\leq a\leq b\leq c\leq 8\}\Big|^2 \\ &= \Big|\{a,b,c \in \mathbb{Z} : 0\leq a-1 < b < c+1 \leq 9\}\Big|^2 \\ &= \Big|\big\{S\subset \{0,1,2,3,4,5,6,7,8,9\} : |S| = 3\big\}\Big|^2 \\ &= \binom{10}{3}^2 = 120^2 = \boxed{14400} \end{aligned}$

---

Further commentary:

• While I haven't explicitly shown it as a combinatorial proof, I've shown a lot of steps here for the sole purpose that a combinatorial proof is evident. That is, $\sum_{c \in \mathcal{C}} \Big|\{R \in \mathcal{R} : R \text{ contains } c\}\Big| = \Big|\{(R,c) \in \mathcal{R}\times\mathcal{C}: R \text{ contains } c\}\Big|$ is just the combinatorial definition for the sum, and $\Big|\big\{S \subset \{0,1,2,3,4,5,6,7,8,9\} : |S| = 3\big\}\Big| = \binom{10}{3}$ is just the combinatorial definition of the binomial coefficient. Also, if you analyze the intermediate steps, what I actually give is a bijection $f : \{(R,c) \in \mathcal{R}\times\mathcal{C}: R \text{ contains } c\} \to \big\{S \subset \{0,1,2,3,4,5,6,7,8,9\} : |S| = 3\big\}^2$ defined by $f\Big([L,U],c\Big) = \Big(\{L_x-1, c_x,U_x+1\}, \{L_y-1, c_y, U_y+1\}\Big)$
• The notation $R = [L,U]$ may look weird, maybe even look like an abuse of notation, but it actually can be completely justified if you recognize we can partially order $\mathcal{C}$ by $c \preceq d \iff c_x\leq d_x \text{ and } c_y \leq d_y$ . Then the rectangles on the board are exactly the closed intervals under $\preceq$ , and in fact $R = [L,U]_{\preceq} \subseteq \mathcal{C}.$