北海道大学 1998年 理系 第3問 解説

方針・初手

「どの二人も隣り合わない」という条件は、まず $k$ 個のいすの位置を選び、そのあと $k$ 人を並べるという2段階で数えるのが自然である。

解法1

$n$ 個のいすが横一列に並んでいる。 $k$ 人がどの二人も隣り合わないように座る場合の数を $f(n,k)$ とする。

まず、座る 位置 だけを考える。 $k$ 個のいすを選ぶとき、隣り合わないという条件は

$$ 1\leqq i_1<i_2<\cdots<i_k\leqq n,\qquad i_{j+1}-i_j\geqq 2 $$

と表せる。

ここで

$$ j_1=i_1,\quad j_2=i_2-1,\quad j_3=i_3-2,\ \dots,\ j_k=i_k-(k-1) $$

とおくと、

$$ 1\leqq j_1<j_2<\cdots<j_k\leqq n-k+1 $$

となる。

逆に、この条件を満たす $j_1,\dots,j_k$ が与えられれば

$$ i_r=j_r+(r-1)\qquad (r=1,2,\dots,k) $$

と戻せるので、隣り合わない $k$ 個の席の選び方と、$1,2,\dots,n-k+1$ から異なる $k$ 個を選ぶ方法とは1対1に対応する。

したがって、隣り合わないような 席の選び方 は

$$ {}_{\,n-k+1}\mathrm{C}_{k} $$

通りである。

次に、その $k$ 個の席に $k$ 人を並べる方法は

$$ k! $$

通りある。

よって求める場合の数は

$$ f(n,k)={}_{\,n-k+1}\mathrm{C}_{k}\cdot k! $$

である。

解説

「隣り合わない席の選び方」は、そのまま数えるよりも、間隔1個分を先に吸収して

$$ i_r\mapsto i_r-(r-1) $$

とずらすのが定石である。これで普通の組合せに落ちる。

答え

$$ f(n,k)={}_{\,n-k+1}\mathrm{C}_{k}\cdot k! $$