# How many ways are there of removing $m$ distinct pairs of consecutive natural numbers from a list of the first $n$ natural numbers?

Given the set of the first $n$ natural numbers, $\{1, 2, \ldots, n\}$, I would like to count the ways that we can remove $m$ distinct pairs of consecutive integers from this set.

For $m=0$ it is trivial, there is only one way to do it.

For $m=1$, there are $n-2$ ways to choose a number with 2 adjacent numbers to pick for its partner, and 2 ways to choose a number with only 1 adjacent number, for $2(n-2)+2 = 2(n-1)$ ways, except that this method will count duplicates. So to avoid that, instead when you choose the first number, always construct the pair by taking the number that follows it. There are only $n-1$ ways of doing this, since $n$ does not have a follower.

For $m=2$ we do not require that the second pair be consecutive with the first, only that the 2 numbers within a pair be consecutive. I have tried to work out this case, but it is complicated both by the fact that choosing $\{2,3\}$ as the first pair, means it is impossible to select $1$ second because it no longer has a pair (and similarly for $n-2$), and also that I do not know how to count without introducing duplicates.

What is the intelligent way to count for the first few $m$ and how can we find the general formula for any $m$?

• Try to compare this to the problem of counting the number of sequences of $(n-2m)~$ $x$'s, and $m~$ $D$'s. E.g. for $n=10$ and $m=2$, what might the sequence $xDxxxxDx$ represent in terms of pairs being picked? What about $DDxxxxxx$? Is there a bijection between the problems? How many answers exist to this related problem? – JMoravitz Mar 14 '16 at 4:10

Denote all the pairs you are removing by "$2$" and all remaining elements by "$1$". For example, if you have $10$ elements and you are removing the three pairs $\{2,3\}$ and $\{4,5\}$ and $\{9,10\}$, this would be denoted $$1221112\ .$$ Now if there are $n$ elements and you are removing $m$ pairs, the above "code" will consist of $m$ digits $2$ and $n-2m$ digits $1$. That's $n-m$ digits altogether; you have to choose which $m$ of them are $2$; the answer is $C(n-m,m)$.