Subsets with one consecutive pair

HardCombinatorics~10m

From $\{1, 2, \dots, 10\}$ , how many subsets contain exactly one pair of consecutive integers? (For example, $\{3,5,6,9\}$ qualifies - the only consecutive pair is $5,6$ ; a subset like $\{3,4,5\}$ does not, since $3,4$ and $4,5$ 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 $m$ singletons along $1..10$ with gaps between runs, summed over $m$ .

Answer

Reveal answer →

235

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Systematic & Data-Driven Trading

Subsets with one consecutive pair

Answer

Related questions