問題
を5以上の整数とする。1以上以下の整数から，相異なる個の整数を選ぶ。ただし1は必ず選ぶこととする。選んだ数の集合をとし，に関する以下の条件を考える。
条件1： は連続する2個の整数からなる集合を1つも含まない。
条件2： は連続する個の整数からなる集合を少なくとも1つ含む。
ただし，2以上の整数に対して，連続する個の整数からなる集合とは，ある整数を用いてと表される集合を指す。例えばは連続する3個の整数からなる集合，，を含む。
(1) 条件1を満たすような選び方は何通りあるか。
(2) 条件2を満たすような選び方は何通りあるか。
方針
(1) は1が必ず選ばれるため2が選べないことから， から隣り合わない 個を選ぶ問題にする。(2) は選ばれた数の最大連続ブロックの長さで分類する。条件2は最大長が のいずれかであることと同値であり，この分類なら重複しない。各場合で，ブロックが1を含むか，1がブロックの外にあるかを分け，ブロックを延長してしまう隣接位置を除いて残りの選び方を数える。
解答
(1)
1は必ず選ばれる。条件1を満たすには，1と連続する2は選ばれない。したがって，3以上 以下の 個の整数から，隣り合わない 個を選べばよい。
選ぶ 個を小さい順に とする。隣り合わない条件は である。ここで とおくと となる。逆にこのような を選べば， により隣り合わない選び方が得られる。
したがって， の 個から 個を選ぶので，求める選び方は 通りである。
(2)
選ばれた整数の連続ブロックのうち，最大の長さを とする。条件2を満たすことは と同値である。選ばれる数は全部で 個なので， の場合に分けて数えればよい。この分け方は最大長による分類なので重複しない。
まず の場合，選んだ 個すべてが連続する。1を含むので，集合は の1通りである。
次に の場合を考える。最大ブロックが1を含むなら，そのブロックは である。残り1個として を選ぶと長さ に延びてしまうので，選べるのは の 通りである。
最大ブロックが1を含まないなら，選んだ集合は1と長さ のブロックからなる。1と連結しないために，ブロックを と書くと である。よってこの場合も 通りである。したがって の場合は 通りである。
最後に の場合を考える。最大ブロックが1を含むなら，そのブロックは である。残り2個は，ブロックを延長しないように を避けて から選ぶ。よって 通りである。
最大ブロックが1を含まないなら，ブロックを と書ける。1と連結しないために である。さらに，残り1個を選ぶとき，ブロックを延長する と は選べない。ただし のとき右隣 は を超えて存在しない。
したがって， の 通りの については残り1個の選び方が 通り， については 通りである。よってこの場合は 通りである。
以上を合計して，条件2を満たす選び方は 通りである。