問題
数直線上の整数点に，合計個の黒または白の石を1つずつ，黒石どうしは隣り合わないように置く．黒石を3個使う置き方は何通りあるか．ただし，とする．
出典：北海道大学 1986年度 前期日程 第2次学力試験 理系 前期 第5問
方針
黒石を置く3つの位置を選べば、残りの位置はすべて白石で決まる。したがって、 かつ隣り合わない、つまり 、 を満たす3点の選び方を数えればよい。隙間を1つずつ詰める変換 、、 によって、 から までの中から3個選ぶ問題に直す。別解として、3個の黒石の間と両端の白石数を分配して数える方法もある。
解答
黒石を置く位置を とする。黒石どうしが隣り合わない条件は である。
そこで とおく。このとき である。逆に、 を満たす3つの整数を選べば により、隣り合わない3つの黒石の位置がただ1通り定まる。
したがって置き方の数は、 から3つを選ぶ数に等しい。よって 通りである。
別解。3個の黒石を先に並べ、その間には少なくとも1個ずつ白石を入れる。すると、黒石3個と必須の白石2個で合計5個を使う。残りの白石は 個であり、左端、2つの間、右端の合計4か所に自由に分配できる。したがって分配の数は であり、同じ結果を得る。