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

方針・初手

$a,b,c$ はそれぞれ $1$ 以上 $n$ 以下の整数である。条件が「厳しい大小関係」か「重複を許す大小関係」かを見て、組合せとして数える。

（3） は $a<b$ と $a\leqq c$ の2条件だけで、$b$ と $c$ の大小関係は指定されていない。そのため、$a$ を固定して $b,c$ の選び方を数えるのが自然である。

解法1

(1)

$a<b<c$ の場合を考える。

これは $1,2,\ldots,n$ から異なる3個の数を選び、それを小さい順に $a,b,c$ とすればよい。したがって、選び方は

$$ {}_nC_3=\frac{n(n-1)(n-2)}{6} $$

である。

(2)

$a\leqq b\leqq c$ の場合を考える。

これは $1,2,\ldots,n$ から重複を許して3個の数を選び、それを小さい順に並べることに対応する。したがって、重複組合せにより

$$ {}*{n+3-1}C_3={}*{n+2}C_3 $$

である。よって

$$ {}_{n+2}C_3=\frac{(n+2)(n+1)n}{6} $$

となる。

また、別の見方として、$a\leqq b\leqq c$ に対して

$$ a'=a,\quad b'=b+1,\quad c'=c+2 $$

とおくと、

$$ 1\leqq a'<b'<c'\leqq n+2 $$

となる。したがって、$1,2,\ldots,n+2$ から3個を選ぶことと同じであり、

$$ {}_{n+2}C_3=\frac{n(n+1)(n+2)}{6} $$

である。

(3)

$a<b$ かつ $a\leqq c$ の場合を考える。

$a$ を固定する。$a$ は $1$ から $n-1$ まで動く。なぜなら、$a<b\leqq n$ より $a=n$ は不可能だからである。

$a$ を固定すると、$b$ は

$$ a+1,a+2,\ldots,n $$

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

また、$c$ は $a\leqq c\leqq n$ より

$$ a,a+1,\ldots,n $$

の $n-a+1$ 通りである。

したがって、$a$ を固定したときの組の数は

$$ (n-a)(n-a+1) $$

である。よって、求める個数は

$$ \sum_{a=1}^{n-1}(n-a)(n-a+1) $$

である。

ここで $k=n-a$ とおくと、$a=1,2,\ldots,n-1$ に対して $k=n-1,n-2,\ldots,1$ となるので、

$$ \begin{aligned} \sum_{a=1}^{n-1}(n-a)(n-a+1) &= \sum_{k=1}^{n-1}k(k+1) \end{aligned} $$

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

$$ \begin{aligned} \sum_{k=1}^{n-1}k(k+1) &=\sum_{k=1}^{n-1}(k^2+k)\\ &=\sum_{k=1}^{n-1}k^2+\sum_{k=1}^{n-1}k\\ &=\frac{(n-1)n(2n-1)}{6}+\frac{(n-1)n}{2}\\ &=\frac{(n-1)n(2n-1+3)}{6}\\ &=\frac{(n-1)n(2n+2)}{6}\\ &=\frac{n(n-1)(n+1)}{3} \end{aligned} $$

したがって、$a<b$ かつ $a\leqq c$ となる組の数は

$$ \frac{n(n-1)(n+1)}{3} $$

である。

解説

（1） は3つの数がすべて異なり、順序が小さい順に固定されるため、単純な組合せで数える。

（2） は重複を許す小さい順の並びなので、重複組合せで処理するのが最短である。変換 $a'=a,\ b'=b+1,\ c'=c+2$ によって、通常の組合せに直す考え方も重要である。

（3） は $b$ と $c$ の大小関係が指定されていない点に注意する。$a<b\leqq c$ ではなく、条件は $a<b$ かつ $a\leqq c$ である。したがって、$a$ を固定して $b$ と $c$ を独立に数えるのが安全である。

答え

(1)

$$ \frac{n(n-1)(n-2)}{6} $$

(2)

$$ \frac{n(n+1)(n+2)}{6} $$

(3)

$$ \frac{n(n-1)(n+1)}{3} $$