方針
黒石を置く3つの位置を選べば、残りの位置はすべて白石で決まる。したがって、 かつ隣り合わない、つまり 、 を満たす3点の選び方を数えればよい。隙間を1つずつ詰める変換 、、 によって、 から までの中から3個選ぶ問題に直す。別解として、3個の黒石の間と両端の白石数を分配して数える方法もある。
解答
黒石を置く位置を とする。黒石どうしが隣り合わない条件は である。
そこで とおく。このとき である。逆に、 を満たす3つの整数を選べば により、隣り合わない3つの黒石の位置がただ1通り定まる。
したがって置き方の数は、 から3つを選ぶ数に等しい。よって 通りである。
別解
解法2(白石をすき間へ分配)
方針
3個の黒石を先に置き、間の2か所に白石を1個ずつ必須配置する。残る白石を両端を含む4つのすき間へ分配し、非負整数解を数える。
解答
3個の黒石をの順に先に置く。これで黒石3個と必須の白石2個を使うので、残る白石は 個である。
追加の白石を、左端、2つの黒石間、2つの黒石間、右端という4つのすき間へ入れる個数を とするとこの非負整数解の個数はである。各解から石の並びが一意に決まり、逆も成り立つので、求める置き方は通りである。
総評
隣接しない位置の選択を数える問題で、目安は12分。位置を詰める方法と、必須の白石を先に置いてすき間へ分配する方法が対応する。n=5では黒白黒白黒の1通りとなり公式の端も確認できる。