問題
ある駅の待合室に，個のいすが横一列に並んでいる．人が，どの二人も隣り合わないように，いすにすわる場合の数を，とする．のとき，次を証明せよ．
出典：北海道大学 1998年度 前期日程 第2次学力試験 理系 前期 第3問
方針
座る椅子の番号を小さい順に とし，隣り合わない条件 を取り除くために と置く。これにより通常の 個の椅子選びに対応する。最後に，選ばれた 個の椅子へ 人を座らせる順列 を掛ける。別解として，空席の隙間に人数を分配する方法でも同じ式を得られる。
解答
座る椅子の番号を小さい順に とする。どの二人も隣り合わないので である。
ここで とおく。すると だから である。逆に，このような が与えられれば によって隣り合わない 個の椅子が一意に定まる。
したがって椅子の選び方は 通りである。さらに，選ばれた 個の椅子に 人を座らせる方法は 通りである。よって である。
別解。まず 人を横一列に並べる方法は 通りである。この 人の間には，隣接を避けるために少なくとも 個の空席が必要である。残りの空席数は であり，これを左端，右端，および 個の間の隙間に追加して配る。追加分の入れ方は 通りである。したがって同じく を得る。