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

[arden]

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? Thanks!

 

[pka]

If you think of a ten-bit sting with three ones and seven zeros that represents any subset of three elements of the set {1,2,3,..,9,10}.
The number of such strings in which on two one’s are together is \(\displaystyle \left( {\begin{array}{c}
8 \\
3 \\
\end{array}} \right) = \frac{{8!}}{{3!\left( {8 - 3} \right)!}}\).

 

[arden]

I'm sorry, maybe I'm a little dense or something, but I don't understand the explanation for your answer. Could you kindly reword it in a way that's easier for me to understand?

 

[pka]

Suppose that you have a set \(\displaystyle \left\{ {1,2, \cdots ,n} \right\}\) from which we choose three terms. Now any string of three ones and n-3 zeros will represent such a set. What you want is that none of the ones are next to each other. The n-3 zero’s create n-2 places to place the one’s. Thus the answer is \(\displaystyle \left( {\begin{array}{c}
{n - 2} \\
3 \\
\end{array}} \right)\)

 

[Denis]

> How many ways can the numbers be chosen...

If by "ways" you mean, as example, that 1-3-5 and 1-5-3 are considered
"different", then there is 56*6 = 336 ways; from 1-3-5 to 10-8-6.
Right, pka?

 

[arden]

> How many ways can the numbers be chosen...

If by "ways" you mean, as example, that 1-3-5 and 1-5-3 are considered
"different", then there is 56*6 = 336 ways; from 1-3-5 to 10-8-6.
Right, pka?

To clear it up, the question is specifically a combinations question, so 1-3-5 and 1-5-3 are considered the same.

 

[daon]

There are \(\displaystyle { 10 \choose 3 }\) ways to choose three numbers from a set of 10. How many of these will have two consecutive numbers? Well, clearly any choice of the form (1,2,x),(2,3,x),(3,4,x)(4,5,x)(5,6,x)(6,7,x)(7,8,x)(8,9,x)(9,10,x). How many choices look like that? It looks like 8 for each one.. however there is an overlap of one when comparing any of the above pairs of adjacent 3-tuples.. i.e. (1,2,3) is included in both (1,2,x) and (2,3,x).

So we get:

\(\displaystyle { 10 \choose 3 } - 72 + 8 \,\, = \,\, {10 \choose 3} - 64\) ways.

 

[pka]

The number of such strings in which no two one’s are together is \(\displaystyle \left( {\begin{array}{c}
8 \\
3 \\
\end{array}} \right) = \frac{{8!}}{{3!\left( {8 - 3} \right)!}}\).

\(\displaystyle { 10 \choose 3 } - 72 + 8 \,\, = \,\, {10 \choose 3} - 64\) ways.

It may interest some that:
\(\displaystyle \left( {\begin{array}{c}
8 \\
3 \\
\end{array}} \right) = \frac{{8!}}{{3!\left( {8 - 3} \right)!}}=56\) and \(\displaystyle { 10 \choose 3 } - 72 + 8 \,\, = \,\, {10 \choose 3} - 64 = 56\).

 

[Denis]

It may interest some that:
\(\displaystyle \left( {\begin{array}{c}
8 \\
3 \\
\end{array}} \right) = \frac{{8!}}{{3!\left( {8 - 3} \right)!}}=56\) and \(\displaystyle { 10 \choose 3 } - 72 + 8 \,\, = \,\, {10 \choose 3} - 64 = 56\).

And 1 + 3 + 6 + 10 + 15 + 21 = 56 :idea:

 

[daon]

Hmm?...

\(\displaystyle \L \sum _{i=1}^{n-4} \frac{i(i+1)}{2} \,\, = \,\, {n \choose 3}-(n-2)^2 \,\, = \,\, {n-2 \choose 3}\)

Anyone feel like doing the proof? (Valid for \(\displaystyle n \ge 5\)).