3 numbers chosen from 1, 2, ..., 10: How many ways can...?

• May 8th 2007, 06:32 PM
arden
3 numbers chosen from 1, 2, ..., 10: How many ways can...?
Three different numbers are chosen from 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10. How many ways can the numbers be chosen so that no 2 of the 3 numbers are consecutive?

I'm completely stumped when it comes to this question. How do you deal with this kind of restriction? BTW, this is a combinations question (order of numbers picked does not matter). Thanks!
• May 9th 2007, 06:19 AM
alinailiescu
You should try an indirect method.
From the total of possible choices: pick 3 numbers:10C3
subtract the number of choices that you dont want, that would be:
all 3 numbers consecutive:8 possibilities
2 of the 3 numbers are consecutive:there are 9 posibilities to have 2 consecutive numbers, so there are 9*8posibilities for this case.
So, 10C3-8-72=40
• May 9th 2007, 10:28 AM
Plato
The answer of 40 is incorrect. The error came from subtracting the same configuration more than once. That is an error of over-counting.

There is a well-known formula connected with this problem.
If S is a ordered set with n elements and k is a positive integer at most ceil(n/2), then the number of ways to choose a k-element subset of S having no consecutive members is Combin(n-k+1,k).
• May 9th 2007, 10:35 AM
alinailiescu
Thanks. I see what you mean.
2 of the 3 numbers are consecutive:there are 9 posibilities to have 2 consecutive numbers, so there are 9*8posibilities for this case include and some subset that have all 3 number consecutive.
Sorry