方針
座る椅子の番号を小さい順に置き、番号を段階的に左へずらして「隣り合わない」条件を通常の組合せへ変換する。人の並べ方を最後に掛ける。
解答
座る椅子の番号を小さい順に 1≦x1<x2<⋯<xk≦n とする。どの二人も隣り合わないので xi+1≧xi+2(1≦i≦k−1) である。
ここで yi=xi−(i−1) とおく。すると yi+1−yi=(xi+1−i)−(xi−i+1)=xi+1−xi−1≧1 だから 1≦y1<y2<⋯<yk≦n−k+1 である。逆に，このような y1,…,yk が与えられれば xi=yi+(i−1) によって隣り合わない k 個の椅子が一意に定まる。
したがって椅子の選び方は n−k+1Ck 通りである。さらに，選ばれた k 個の椅子に k 人を座らせる方法は k! 通りである。よって f(n,k)=n−k+1Ck⋅k! である。
別解
解法2
方針
先に人を一列に並べ、間へ必須の空席を1個ずつ入れる。残りの空席を両端と各隙間へ重複を許して分配する。
解答
まず k 人を横一列に並べる方法は k! 通りである。この k 人の間には，隣接を避けるために少なくとも k−1 個の空席が必要である。残りの空席数は n−k−(k−1)=n−2k+1 であり，これを左端，右端，および k−1 個の間の隙間に追加して配る。追加分の入れ方は (n−2k+1)+kCk=n−k+1Ck 通りである。したがって同じく n−k+1Ckk! を得る。
総評
「隣り合わない」を一つずつ左へ詰める変換で消す典型問題である。所要時間は8分程度。xi から yi=xi−(i−1) へ移すと，上限が n−k+1 になる理由を丁寧に書くとよい。最後に k! を掛けるのは，人が区別されているためである。別解の隙間法は発想が図形的で，条件 n≧2k−1 が「最低限の空席を入れられる」ことを意味していると分かりやすい。
冊子PDFで見る北大の場合の数の問題で問題集を作る
出典: 北海道大学 1998年度 前期 理系 第3問。問題文はHTML表示のために再入力・数式組版しています。
Evolton