Evolton

北海道大学 1998年度 前期日程 第2次学力試験理系数学 第3問

ある駅の待合室に,n個のいすが横一列に並んでいる.
k人が,どの二人も隣り合わないように,いすにすわる場合の数を,f(n, k)とする.
n≧2k−1のとき,次を証明せよ.f(n, k)=n−k+1Ck⋅(k !)

難易度4/ 10計算量3/ 10目安8分

場合の数 数え上げ、置換、一般化

方針

座る椅子の番号を小さい順に置き、番号を段階的に左へずらして「隣り合わない」条件を通常の組合せへ変換する。人の並べ方を最後に掛ける。

解答

座る椅子の番号を小さい順に 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 が「最低限の空席を入れられる」ことを意味していると分かりやすい。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る北大の場合の数の問題で問題集を作る

出典: 北海道大学 1998年度 前期 理系 第3問。問題文はHTML表示のために再入力・数式組版しています。