Subsets with one consecutive pair
From , how many subsets contain exactly one pair of consecutive integers? (For example, qualifies - the only consecutive pair is ; a subset like does not, since and are two consecutive pairs.)
Show hints (2)+
- Think in terms of maximal runs of consecutive chosen integers. "Exactly one consecutive pair" means one run of length 2 and the rest length 1.
- Count layouts of one doubleton plus singletons along with gaps between runs, summed over .
Answer
Reveal answer →Final answer
235
Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.
Asked at: Jane Street, Two Sigma