3
$\begingroup$

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$?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – JMoravitz Mar 14 '16 at 4:10
6
$\begingroup$

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)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Ah yes, thank you I did not expect such a simple and elegant answer. The counting seemed very messy to me. This way of representing it is quite clever. $\endgroup$ – Kevin Driscoll Mar 14 '16 at 4:34
  • $\begingroup$ Is this a standard trick in combinatorics? (I've never taken a discrete math class, this question arose in research and not as homework) $\endgroup$ – Kevin Driscoll Mar 14 '16 at 4:35
  • $\begingroup$ I would say it's fairly standard - there are always variations on how you use these methods. Look up "stars and bars" for something similar. $\endgroup$ – David Mar 14 '16 at 4:36
  • $\begingroup$ I had upvoted earlier; it really is nicely elegant ! $\endgroup$ – true blue anil Mar 14 '16 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.