Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Did you try searching the site? Try the search term "non-consecutive". –  Aryabhata Feb 2 '11 at 21:51
1  
@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
1  
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
1  
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
show 1 more comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
2  
True. Just a remark, this was in Moron's answer about non-consecutive birthdays. –  Wok Feb 2 '11 at 22:42
    
Ahh, thank you - I didn't do the 'non-consecutive' search myself, so I presumed that the poster hadn't been able to track anything else directly apropos down; mea culpa. –  Steven Stadnicki Feb 2 '11 at 22:51
    
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
add comment

In analogy to the Pascal triangle, define D(n,r) as the number of ways to select r items from n with no two consecutive. You can either use 1 or not. If you do use it, you can't use 2 but only need to pick r-1. If you don't use it you have n-1 items to pick r from. So D(n,r)=D(n-2,r-1)+D(n-1,r). The base case is D(2r-1,r)=1For values like this you can use a spreadsheet.

share|improve this answer
    
Nice and simple. Thank you. –  Mark Eichenlaub Feb 2 '11 at 22:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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