問題
を5以上の整数とする。1以上以下の整数から，相異なる個の整数を選ぶ。ただし1は必ず選ぶこととする。選んだ数の集合をとし，に関する以下の条件を考える。
条件1： は連続する2個の整数からなる集合を1つも含まない。
条件2： は連続する個の整数からなる集合を少なくとも1つ含む。
ただし，2以上の整数に対して，連続する個の整数からなる集合とは，ある整数を用いてと表される集合を指す。例えばは連続する3個の整数からなる集合，，を含む。
(1) 条件1を満たすような選び方は何通りあるか。
(2) 条件2を満たすような選び方は何通りあるか。
方針
解法1（最大連続ブロックで分類する）
(1) は1が必ず選ばれるため2が選べないことから， から隣り合わない 個を選ぶ問題にする。(2) は選ばれた数の最大連続ブロックの長さで分類する。条件2は最大長が のいずれかであることと同値であり，この分類なら重複しない。各場合で，ブロックが1を含むか，1がブロックの外にあるかを分け，ブロックを延長してしまう隣接位置を除いて残りの選び方を数える。
解法2（隙間表示と二重計数を使う）
(1) は選んだ数の間の空きと末尾の空きを変数にすると，余分な空きが合計1であることから直ちに数えられる。(2) は長さ の区間 と，それを含む集合 の組を数える。同じ が複数回数えられるのは最大連続長が または の場合だけなので，その余分を差し引く。
解答
解法1（最大連続ブロックで分類する）
(1)
1は必ず選ばれる。条件1を満たすには，1と連続する2は選ばれない。したがって，3以上 以下の 個の整数から，隣り合わない 個を選べばよい。
選ぶ 個を小さい順に とする。隣り合わない条件は である。ここで とおくと となる。逆にこのような を選べば， により隣り合わない選び方が得られる。
したがって， の 個から 個を選ぶので，求める選び方は 通りである。
(2)
選ばれた整数の連続ブロックのうち，最大の長さを とする。条件2を満たすことは と同値である。選ばれる数は全部で 個なので， の場合に分けて数えればよい。この分け方は最大長による分類なので重複しない。
まず の場合，選んだ 個すべてが連続する。1を含むので，集合は の1通りである。
次に の場合を考える。最大ブロックが1を含むなら，そのブロックは である。残り1個として を選ぶと長さ に延びてしまうので，選べるのは の 通りである。
最大ブロックが1を含まないなら，選んだ集合は1と長さ のブロックからなる。1と連結しないために，ブロックを と書くと である。よってこの場合も 通りである。したがって の場合は 通りである。
最後に の場合を考える。最大ブロックが1を含むなら，そのブロックは である。残り2個は，ブロックを延長しないように を避けて から選ぶ。よって 通りである。
最大ブロックが1を含まないなら，ブロックを と書ける。1と連結しないために である。さらに，残り1個を選ぶとき，ブロックを延長する と は選べない。ただし のとき右隣 は を超えて存在しない。
したがって， の 通りの については残り1個の選び方が 通り， については 通りである。よってこの場合は 通りである。
以上を合計して，条件2を満たす選び方は 通りである。
解法2（隙間表示と二重計数を使う）
(1)
選んだ数を
とする。条件1より，隣り合う選択数の間にある未選択数の個数
はすべて1以上である。また末尾の空きを とする。選ばない数は全部で 個なので
である。最初の 個から1ずつ差し引くと， 個の非負整数の和が1になる。したがって1を置く場所の選び方だけがあり，求める個数は
通りである。
(2)
長さ の連続区間を とし， となる組 を数える。
のとき，残る2個は外側の 個から選ぶので
通りである。 の先頭が2以上のとき，先頭は の 通りである。1はすでに選ばれ，残る1個は の外の 個から選べる。よって組 の総数は
である。
ただし，同じ が複数の を含む場合を補正する。最大連続長が の集合は，長いブロックが1を含む場合に 通り，含まない場合に 通りあり，合計 通りである。この各集合は長さ の区間を2個含むので，1回ずつ余分に数えられている。また最大連続長が の集合は の1通りで，長さ の区間を3個含むため2回余分である。
したがって条件2を満たす集合の個数は
通りである。