PDA

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



arden
05-08-2007, 08:06 PM
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
05-08-2007, 08:37 PM
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 \left( {\begin{array}{c}
8 \\
3 \\
\end{array}} \right) = \frac{{8!}}{{3!\left( {8 - 3} \right)!}}.

arden
05-08-2007, 09:26 PM
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? :oops:

pka
05-08-2007, 09:48 PM
Suppose that you have a set \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 \left( {\begin{array}{c}
{n - 2} \\
3 \\
\end{array}} \right)

Denis
05-08-2007, 10:13 PM
> 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
05-08-2007, 10:19 PM
> 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
05-09-2007, 12:01 AM
There are { 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:

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

pka
05-09-2007, 09:38 AM
The number of such strings in which no two one’s are together is \left( {\begin{array}{c}
8 \\
3 \\
\end{array}} \right) = \frac{{8!}}{{3!\left( {8 - 3} \right)!}}.
{ 10 \choose 3 } - 72 + 8 \,\, = \,\, {10 \choose 3} - 64 ways.
It may interest some that:
\left( {\begin{array}{c}
8 \\
3 \\
\end{array}} \right) = \frac{{8!}}{{3!\left( {8 - 3} \right)!}}=56 and { 10 \choose 3 } - 72 + 8 \,\, = \,\, {10 \choose 3} - 64 = 56.

Denis
05-09-2007, 11:28 AM
It may interest some that:
\left( {\begin{array}{c}
8 \\
3 \\
\end{array}} \right) = \frac{{8!}}{{3!\left( {8 - 3} \right)!}}=56 and { 10 \choose 3 } - 72 + 8 \,\, = \,\, {10 \choose 3} - 64 = 56.
And 1 + 3 + 6 + 10 + 15 + 21 = 56 :idea:

daon
05-09-2007, 10:02 PM
Hmm?...

\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? :D (Valid for n \ge 5).