棋盤上的矩形個數

==問題==

如圖所示，有多少個矩形？

 ==解答==

本題使用排容原理。

先將不完整的棋盤裡的線補完，同時對垂直線以及水平線編號，如下圖所示。

在不考慮中間是否挖空的情況下，由$r_1, \cdots, c_6$與$c_1, \cdots, c_7$等線所決定的矩形個數為${6 \choose 2} \times {7 \choose 2} = 315$個。

現在回過頭來考慮挖空的影響。

在以上315個矩形中，只要邊界之一由$r_4$或$c_3$構成者，一概都不可計入。所以
\begin{eqnarray*}
n(\text{不可計入矩形}) &=& n(\text{邊界之一由}r_4\text{或}c_3\text{構成者}) \\
&=& n(\text{邊界之一由}r_4\text{構成者}) + n(\text{邊界之一由}c_3\text{構成者}) - n(\text{邊界之二由}r_4\text{及}c_3\text{構成者}) \\
&=& {5 \choose 1} \times \left[ {7 \choose 2} - {2 \choose 2} - {4 \choose 2} \right] + {6 \choose 1} \times \left[ {6 \choose 2} - {3 \choose 2} - {2 \choose 2} \right] - {5 \choose 1} \times {6 \choose 1} \\
&=& 70 + 66 - 30 \\
&=& 106\text{個}.
\end{eqnarray*}
因此所求矩形數$= 315 - 106 = 209$個。