数学A 場合の数 問題 1 解説

方針・初手

白石は黒石の位置が決まれば自動的に決まる。したがって、問題は $1,2,\ldots,n$ の中から、隣り合わない $3$ 個の整数を選ぶ問題に言い換えられる。

解法1

黒石を置く位置を小さい順に

$$ a<b<c $$

とする。黒石どうしが隣り合わない条件は

$$ b-a\geqq 2,\qquad c-b\geqq 2 $$

である。

この条件を普通の大小関係に直すため、

$$ A=a,\qquad B=b-1,\qquad C=c-2 $$

とおく。すると

$$ A<B<C $$

となる。

また、$1\leqq a<b<c\leqq n$ より、

$$ 1\leqq A<B<C\leqq n-2 $$

である。

したがって、条件を満たす黒石の置き方は、$1,2,\ldots,n-2$ の中から $3$ 個を選ぶ方法の数に等しい。

よって求める数は

$$ {}_{{n-2}}C_3 $$

である。

これを展開すると、

$$ {}_{{n-2}}C_3=\frac{(n-2)(n-3)(n-4)}{6} $$

となる。

解法2

黒石を $3$ 個置くには、まず隣り合わないための最低限の並びを考える。

黒石を $B$、黒石どうしの間に必ず必要な白石を $W$ とすると、最小の形は

$$ BWBWB $$

であり、この時点で $5$ 個の場所を使う。

残りの白石は

$$ n-5 $$

個である。

これらを、次の $4$ か所に分配すればよい。

$$ \boxed{\phantom{W}}B\boxed{\phantom{W}}W B\boxed{\phantom{W}}W B\boxed{\phantom{W}} $$

つまり、左端、$1$ 個目と $2$ 個目の黒石の間、$2$ 個目と $3$ 個目の黒石の間、右端の $4$ か所に、合計 $n-5$ 個の白石を入れる。

ただし、黒石どうしの間にはすでに白石が $1$ 個ずつ入っているので、追加の白石は $0$ 個でもよい。

よって、非負整数 $x_1,x_2,x_3,x_4$ について

$$ x_1+x_2+x_3+x_4=n-5 $$

の解の個数を求めればよい。

これは重複組合せより

$$ {}*{(n-5)+4-1}C*{4-1}={}_{n-2}C_3 $$

である。

したがって、

$$ {}_{n-2}C_3=\frac{(n-2)(n-3)(n-4)}{6} $$

となる。

解説

この問題では、白石を個別に区別する必要はない。黒石を置く位置を決めれば、残りの位置にはすべて白石が置かれるからである。

したがって本質は、「$1$ から $n$ までの整数から、隣り合わない $3$ 個を選ぶ」問題である。解法1のように番号をずらして通常の組合せに直す方法は、隣接禁止の典型処理である。

解法2は、黒石どうしの間に最低限必要な白石を先に置き、残りの白石をすき間に分配する方法である。どちらも同じく

$$ {}_{n-2}C_3 $$

に帰着する。

答え

$$ \boxed{{}_{n-2}C_3=\frac{(n-2)(n-3)(n-4)}{6}} $$