数学A 場合の数(重複組合せ) 問題 1 解説

方針・初手

まず両端 $a,d$ を固定する。条件(1)より $1\leqq a<d\leqq n$ であるから、区間 $[a,d]$ の長さに着目する。

$a,d$ を固定すると、条件(2)から $b$ の選び方、条件(3)から $c$ の選び方がそれぞれ独立に決まる。

解法1

条件(1)より、まず $a,d$ は

$$ 1\leqq a<d\leqq n $$

を満たす。

このとき条件(2)は

$$ a\leqq b<d $$

であるから、$b$ は

$$ a,a+1,\dots,d-1 $$

の $d-a$ 通りである。

また条件(3)は

$$ a<c\leqq d $$

であるから、$c$ は

$$ a+1,a+2,\dots,d $$

の $d-a$ 通りである。

よって、$a,d$ を固定したときの $(b,c)$ の選び方は

$$ (d-a)^2 $$

通りである。

ここで $k=d-a$ とおく。$a<d$ より $k=1,2,\dots,n-1$ である。$d=a+k\leqq n$ だから、固定した $k$ に対して $a$ は

$$ 1\leqq a\leqq n-k $$

を満たすので、$a,d$ の選び方は $n-k$ 通りである。

したがって、求める個数は

$$ \sum_{k=1}^{n-1}(n-k)k^2 $$

である。これを計算すると、

$$ \begin{aligned} \sum_{k=1}^{n-1}(n-k)k^2 &=n\sum_{k=1}^{n-1}k^2-\sum_{k=1}^{n-1}k^3 \\ &=n\cdot \frac{(n-1)n(2n-1)}{6} -\left\{\frac{(n-1)n}{2}\right\}^2 \\ &=\frac{n^2(n-1)(2n-1)}{6} -\frac{n^2(n-1)^2}{4} \\ &=\frac{2n^2(n-1)(2n-1)-3n^2(n-1)^2}{12} \\ &=\frac{n^2(n-1){2(2n-1)-3(n-1)}}{12} \\ &=\frac{n^2(n-1)(n+1)}{12}. \end{aligned} $$

よって、

$$ \frac{n^2(n^2-1)}{12} $$

である。

解説

この問題では、$a,b,c,d$ を同時に数えようとすると条件が絡んで見える。しかし、両端 $a,d$ を先に固定すると、$b$ と $c$ の範囲がそれぞれ

$$ a\leqq b<d,\qquad a<c\leqq d $$

となり、どちらも $d-a$ 通りであることがすぐに分かる。

重要なのは、$b$ と $c$ の大小関係には条件がない点である。したがって、$b$ と $c$ は独立に選んでよい。

あとは $d-a=k$ とおいて、同じ間隔をもつ $(a,d)$ の組をまとめて数えればよい。

答え

条件(1)(2)(3)をすべて満たす自然数の組 $(a,b,c,d)$ の個数は

$$ \frac{n^2(n^2-1)}{12} $$

である。