03 Sep 09
Originally posted by clandarkfirethere are combinatorical numbers called the "choose" numbers that describe the answer to the generic question you just asked... they also are the elements of pascals triangle, and there is a discrete formula for computing "n choose k," or in other words, counting the number of ways you can order "n" things while "choosing k" of the elements.
How many seven digit numbers can be built using two 2s and five 5s?
A friend asked me this last week, and I cant figure out how to do it. There must be a way to do it without trying every possibility, but I cant figure it out.
in this case you want to order 7 things while choosing two of them as 2 and letting the rest be 5's (note: alternatively, you could think of this as ordering 7 things while choosing 5 of them as 5's and leaving the rest 2's... and you will see by the computation that these processes are identical)
now "n choose k," sometimes seen as nCk (or as an n-superscript and a k-subscript directly above and below each other, in between parentheses), is computed as follows:
nCk = n!/(k! * [n-k]!) . i won't derive it for you here, but a little wikipedia and/or searching for combinatorics literature is quite nice!
so in your case: 7C2 = 7!/(5!*2!) = 7*6/2*1 = 21 different ways. computing 7C5 and verifying its equality, and considering why nCk and nC(n-k) are equal is left to the reader.
hope this helps! cheers!
03 Sep 09
Originally posted by AetheraelTwo 2's and five 5's.
there are combinatorical numbers called the "choose" numbers that describe the answer to the generic question you just asked... they also are the elements of pascals triangle, and there is a discrete formula for computing "n choose k," or in other words, counting the number of ways you can order "n" things while "choosing k" of the elements.
in this ca ...[text shortened]... ] and [b]nC(n-k) are equal is left to the reader.
hope this helps! cheers![/b]
How many places do you have to place the first 2?
Seven places, so seven possibilities.
How many places do you have left for the second 2?
Six places, so 6 possibilities.
So far that gives us 7*6=42 possibilities.
The rest of the places is filled up by 5's, so those don't give more possibilities (the order doesn't matter, it always gives the same number as result).
We have some doubles in our 42 possibilities though. For the resulting number, it doesn't matter if the two 2's switch places; 5555522' is the same number as 555552'2. We HAVE counted those seperately though.
This means we have twice as much possibilities as there really are.
Final answer: 21 possibilities to arrange two 2's and five's.
Aetherael hit the nail on the head about combinatorial numbers, that is exactly what we're talking about.
05 Sep 09
However, I do have another question. Just to try out these methods, I decided to try both of these ideas, (which both seem to work well, at least for the first problem.) I decided to try a 14 digit number, with six 6s and eight 8s.
Using the first method:
14!/8!*6! I have very little expierience with factorials, so I dont know how do multiply and divide them. Instead, I just worked this out using the full numbers. So: 87178291200/29030400 = 3003.
Now, when I use the other meathod I work it out like this:
the first 6 has 14 possible places where it can go. The next one has 13, etc.
The rest of the eights are all the same, so you dont have to worry about them. Now: 14*13*12*11*10*9 = 2162160. Since there are six 6s, they can be switched. Therfore, 2162160/6. This number is far too large. I believe my mistake is in the last step, but I cant figure out what it is. Could someone point me toward my mistake?
05 Sep 09
Originally posted by clandarkfireIn your last step you have assumed only 6 ways of 'switching' the 6s. Think about that.
However, I do have another question. Just to try out these methods, I decided to try both of these ideas, (which both seem to work well, at least for the first problem.) I decided to try a 14 digit number, with six 6s and eight 8s.
Using the first method:
14!/8!*6! I have very little expierience with factorials, so I dont know how do multiply a ...[text shortened]... is in the last step, but I cant figure out what it is. Could someone point me toward my mistake?
07 Sep 09
Originally posted by clandarkfireAnyone who goes in their local bookies will tell you there are 21 separate pairs [doubles] in a group of 7 horses. If you count them both ways that's 42. The answer to life, the universe, and everything. Simple.
How many seven digit numbers can be built using two 2s and five 5s?
A friend asked me this last week, and I cant figure out how to do it. There must be a way to do it without trying every possibility, but I cant figure it out.
Just ask Woodgie.