Choosing Three Numbers from 1-10

Date: 06/08/2001 at 21:59:53
From: Craig Murai
Subject: Permutations & combinations

I am having difficulty solving the following 'combination' problem.
Could you please explain your reasoning in solving the problem?

Problem:

How many ways can three numbers be chosen from the numbers 
1,2,3,4,5,6,7,8,9,10 so that no two of the three numbers are 
consecutive? Answer: 56

Thanks!

Date: 06/09/2001 at 00:15:49
From: Doctor Schwa
Subject: Re: Permutations & combinations

Hi Craig,

My first impulse is to think about the numbers that are *skipped*
instead of the numbers that are chosen.

That is, if the numbers that are chosen were 1, 3, and 8, then
I'd represent that as 0142, the 0 meaning that no numbers are skipped 
at the beginning, then one number skipped after the 1, then four 
numbers skipped after the 3, then two numbers skipped after the 8. 
Since you chose three numbers out of 10, the four numbers you write 
have to add up to 7 (3 chosen leaves 7 to be skipped).

The middle two numbers have to be at least 1. So, to make all four
numbers be arbitrary (including 0 as legal), let's subtract one from
each of the middle numbers. So now the choice of 1,3,8 would be 
written as 0032, where the total now is 5, and each of the four 
numbers can be anything (including 0).

Another way to represent that, which makes it easier to count the 
number of ways to do it, is as , , xxx , xx where the commas separate 
the digits, and the x's tally the numbers. We know that there are a 
total of five x's and three commas, and they can go in any order, so 
there are (8 choose 3) which is 56 ways.

For example, if you choose to put your x's and commas in order like
xx , , x , xx that means 2012 in the later notation, but we have to 
add back the 1 in the middle, so that means 2122 are the number of 
skips, so decoding that, it means 3, 5, 8 are the numbers chosen.

That's a pretty difficult way to get the answer, though, and I just 
figured out an easier way to do it.

Because the answer I got last time was (8 choose 3), I thought
it might make sense to choose any three numbers from 1 through 8
first, like say

   1, 3, 4

Then insert one extra space to make sure there are no consecutive 
numbers (in other words, add 1 to the middle number and add 2 to the 
big number): 

   1, 4, 6

That will translate every set of three chosen from 8 into a set of 
nonconsecutives that are chosen from 10.

Does that logic make sense? Please write back if it's not clear.

Enjoy,

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/