箱の数

鈴木寛太郎の番組で紹介されていた奈良県立医大の入試問題がおもしろかった。

図１：すべての四角形の数え上げ問題

問題は簡単で，図１のような階段型の図においてとりうるすべての可能な四角形の数を数えるというものだ。このぐらいならば，順番に数えつくすこともできなくはない。

縦（横）が $n$ マスの場合の四角形の数を$S_n$とすると，$S_1=1,\  S_2=5\ $である。次に，$S_{n}-S_{n-1}$の漸化式を，$n \ge 2$の場合に求めてみよう。$S_{n-1}$ブロックの各列の上に1マスが加わっているので，これを含んで新たに加わる四角形の数は，左から1列目の１マスに対して$1 \cdot n$個，2列目の１マスに対して$2 \cdot (n-1)$個，…，$n$列目が$n \cdot 1$個となる。

これらの和が，$S_{n}-S_{n-1}$になり次式で与えられる。$\displaystyle S_{n}-S_{n-1} = \sum_{k=1}^n k \cdot  (n-k+1) = \sum_{k=1}^n \{ (n+1) k -k^2 \}$

$= \dfrac{n(n+1)^2}{2} - \dfrac{n(n+1)(2n+1)}{6} = \dfrac{n(n+1)(n+2)}{6}$

そこで，$S_k-S_{k-1}= \dfrac{k(k+1)(k+2)}{6}\ $の両辺を$k=2$から$k=n$までそれぞれ加えると，

$\displaystyle S_n-S_1 = \sum_{k=2}^n \dfrac{k(k+1)(k+2)}{6} = \dfrac{1}{6}  \sum_{k=2}^n (k^3+3k^2+2k)$

$S_n = 1 + \dfrac{1}{6} \Bigl\{ \dfrac{n^2(n+1)^2}{4} -1 +3\bigl( \dfrac{n(n+1)(2n+1)}{6} -1 \bigr)  +2\bigl( \dfrac{n(n+1)}{2}-1 \bigr) \Bigr\}$

$= \dfrac{n(n+1)}{24}\Bigl\{ n(n+1) + 2(2n+1) + 4 \Bigr\} = \dfrac{n(n+1)(n+2)(n+3)}{4!}=_{n+3}C_4$

答えは求まったがとても簡単な式で意味付けができそうだ。鈴木貫太郎の番組の答えをみると小倉悠司さんの素晴らしい解説が紹介されていてオオオッとなった。

図２：四角形数え上げの答えの解釈

与えられた図形の上に次のような$n+3$個の赤点を置く。上から始めて時計回りに2点を縦の分割線，さらに2点を横の分割線として4点選ぶと，1つの四角形に一意的に対応する。つまり，$n+3$個の点から4点選ぶことが四角形の選び方と対応するというわけだ。すごくない。