# How many ways can $r$ nonconsecutive integers be chosen from the first $n$ integers?

During self-study, I ran across the question of how many ways six numbers can be chosen from the numbers 1 - 49 without replacement, stipulating that no two of the numbers be consecutive.

I can obtain a simple lower bound by saying that, in the worst-case scenario, when you choose a particular number, there are now three numbers that cannot be chosen next. For example, if I first pick 17, then I can't choose 16, 17, or 18 for the remaining choices. This gives me the lower bound

$$\frac{49*46*43*40*37*34}{6!} = 6,773,770 \frac{8}{9}$$

This is about 48% of ${}_{49}C_6 = 13,983,816$. The real answer must be bigger (and an integer). I haven't found a way to calculate it, though.

The original problem asked to show that the probability of having non-consecutive integers when you choose six is greater than 50%, so if the problem is complicated to count exactly, better approximations that show the answer is above 50% would also be appreciated.

Of course, I can use a computer to do the counting, but I'm interested in learning what methods I'm missing.

-
Did you try searching the site? Try the search term "non-consecutive". – Aryabhata Feb 2 '11 at 21:51
@Moron Yes, I did search this site. I found someone talking about non-consecutive birthdays, but that's sampling with replacement, and this is without replacement. Did I miss something? – Mark Eichenlaub Feb 2 '11 at 21:55
I think that on the initial choice you miss the chance that you picked $1$ or $49$ and then there's only one choice you need to avoid. – Asaf Karagila Feb 2 '11 at 22:30
The answer is in Moron's answer about non-consecutive birthdays. – Wok Feb 2 '11 at 22:41
@Mark: As wok pointed out, it is there in my answer. In fact, I believe it is present in all three answers and gives you three different view points! – Aryabhata Feb 2 '11 at 22:50

Another good way of solving problems like this is to set up a correspondence with a problem you already know how to solve. In this case, imagine that you've got a sorted set of six non-consecutive numbers $a_1, a_2, \dots a_6$ between 1 and 49. What does it look like? Well, the first number $a_1$ is essentially arbitrary; it can't be greater than a certain value (i.e. 39) or else there isn't 'room' for five more non-consecutive numbers above it, but we can ignore that for now. The second number $a_2$ has to be greater than $a_1+1$ — that's what it means to be nonconsecutive, after all — so we know that $a_2-1$ (call this $b_2$) is greater than $a_1$. Similarly, $a_3$ has to be greater than $a_2+1$, so $a_3-1$ is greater than $a_2$, and $a_3-2$ is greater than $a_2-1 = b_2$; we can call this $b_3$. And so on, and so forth, until we define $b_6 = a_6-5$. But this correspondence works both ways — given the $b_n$ it's easy to get the $a_n$ — and so we have a one-to-one correspondence between our non-consecutive sets of numbers and an ordinary combination (but with a different upper bound - can you see what it should be?). It takes a while to build this sort of instinct, but learning how to spot these correspondences is the most basic tool for proving most combinatorial identities.
Yes, I get in now. The answer is just ${}_{n-r+1}C_r$. Thank you encouraging me rather than giving it away. – Mark Eichenlaub Feb 3 '11 at 3:54