$n$個の整数 $1, 2, 3, ..., n$ のうちから3個の整数を選ぶとき、どの2つの数の差の絶対値も3以上となるような選び方は何通りあるか。ただし、$n$は7以上とする。

1. 問題の内容

$n$個の整数 $1, 2, 3, ..., n$ のうちから3個の整数を選ぶとき、どの2つの数の差の絶対値も3以上となるような選び方は何通りあるか。ただし、$n$は7以上とする。

2. 解き方の手順

選んだ3つの整数を小さい順に$x, y, z$とする。条件より、

$1 \le x < y < z \le n$

かつ

$y - x \ge 3$

$z - y \ge 3$

$y - x \ge 3$ より $y \ge x + 3$

$z - y \ge 3$ より $z \ge y + 3 \ge x + 6$

$x, y, z$ を

$x = x'$

$y = x' + 3 + y'$

$z = x' + 3 + y' + 3 + z' = x' + 6 + y' + z'$

と置く。ただし、$x' \ge 0$, $y' \ge 0$, $z' \ge 0$を満たす整数とする。

$z \le n$ より

$x' + 6 + y' + z' \le n$

$x' + y' + z' \le n - 6$

$x \ge 1$ より $x' \ge 1$ なので、$x'' = x' - 1$ とすると $x'' \ge 0$.

$x'' + y' + z' \le n - 7$

$x'' + y' + z' + w = n - 7$ となる非負整数$x'', y', z', w$の組を求める問題に帰着する。

これは、$n-7$個の○と3つの仕切りの並び方を考える問題と同じである。

よって、求める場合の数は、

$_{n-7+4-1}C_{4-1} = _{n-4}C_3 = \frac{(n-4)(n-5)(n-6)}{3 \cdot 2 \cdot 1} = \frac{(n-4)(n-5)(n-6)}{6}$

通りである。

3. 最終的な答え

$\frac{(n-4)(n-5)(n-6)}{6}$ 通り