Combinations and permutations...
Jan. 10th, 2014 11:58 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
alexpgpFurther to my line of inquiry from my previous post (and probably boring as all get-out, if math makes your eyes glaze over... so you've been warned), I ran across a post at a site called Answers that purported to answer the question : How many ways can you arrange 3 geometry books and 4 algebra books on a shelf?
The answer was good in that it addressed more than one interpretation of the question. The part they got right had to do with the number of ways this can be done if you do not pay any particular attention to subjects and just want to know how to arrange seven books, the answer to which is 7! (7x6x5x4x3x2x1 = 5040). The part the answer got wrong considered simply the subjects of the books, e.g., AAGAGGA, where the suggested answer (12) is wrong.
Based on my calculation (the number of items, factorial, divided by the numbers of items in each group, factorial) the answer should be (7!/4!3! = 35), but to be frank, my confidence had been shaken a bit with my crazy results while calculating the Farkel numbers, so I wanted a second way of verifying that the number that I arrived at computationally was actually, llike, correct.
After a few moments, I came across a rather whimsical method of figuring this out that did not involve writing a cumbersome computer program to actually step through the process.
If one represents each algebra book with a 0 and each geometry book with a 1 (so that AAGAGGA is represented by 0010110), the problem reduces to figuring out how many 7-bit binary numbers contain exactly three 1s.
Now frankly, the idea of writing out all 128 (2^7) binary numbers and crossing out the ones that don't fit the criteria didn't seem like much of a path to a solution, but it occurred to me to consider a 7-bit binary number as a two-digit hexadecimal number (between 0x00 and 0x7F), and after writing out 0 through 7 in one column and 0 through F in another column, and then writing the number of 1s in each of these twenty-four numbers, it was fairly straightforward to combine columns and figure out how many numbers contain only three 1s. That answer is 35.
This really didn't bring me much closer to the question that's really bugging me, which is (restated using a more sensible formulation): In how many unique ways can I arrange two red blocks, two yellow blocks, and two blue blocks in a row next to each other?
I don't know of any easy way to do base-3 calculations, so instead, I turned to an allied question: In how many ways can I arrange two red blocks and four green blocks in a row next to each other?
I used the same shortcut, letting 1 represent red and 1 represent green, except that now, the range of hex numbers I was dealing with had narrowed to between 0x00 and 0x3F). The answer was 15.
(This, by the way, addressed the question of how many ways, given two specific numbers, can six dice come up with one number on four of them and the second number on the other two? If we figure six possibilities for the first number, and five for the second, that means there ought to be 6x5 = 30 ways the aforementioned 15 combinations can show up, or 30 x 15 = 450 in all. But I digress...)
Using the same "logic" (for me, a very slippery term when dealing with probability calculations), I asked myself "If I were to replace the four green blocks with two yellow blocks and two blue blocks, in how many unique ways could I arrange these new blocks?" Here, it was sufficient to just write out the numbers from 0x0 to 0xF in binary, let 1 denote yellow and 0 denote blue, and cross out any number that didn't have two 1s. What's left is 6 numbers.
If I've done this right, then there ought to be 15 x 6 = 90 ways to arrange six dice, where two of the dice show some number, two more show another number, and the last two show a third number. And this is where I get stuck.
Because if we assume that there are 6 alternatives for the first number, 5 for the second number, and 4 for the third number, then there are 6x5x4 ways to get those 90 arrangements of three "pairs" of dice, or (6x5x4x90 =) 10800 ways. The problem is, several sources I've looked at online say the right number is 1800.
My math would appear to be off by a factor of exactly 6, but where?
UPDATE: On a whim, as a quick-and-dirty statistical attempt at getting my bearings, I rolled my Farkel dice 50 times and recorded the results. I got one four-of-a-kind, 9 triples, two occurrences of three pairs, and 26 occurrences of two pairs. As there are 46,656 different ways to roll 6 dice, if there were 10,800 ways of coming up with three pairs, one might not be surprised to end up with 10 or so occurrences, which clearly did not happen. If the online figure is correct, I should have gotten about two occurrences, which is what occurred. This is additional evidence that my math is "off." Al, well...
The answer was good in that it addressed more than one interpretation of the question. The part they got right had to do with the number of ways this can be done if you do not pay any particular attention to subjects and just want to know how to arrange seven books, the answer to which is 7! (7x6x5x4x3x2x1 = 5040). The part the answer got wrong considered simply the subjects of the books, e.g., AAGAGGA, where the suggested answer (12) is wrong.
Based on my calculation (the number of items, factorial, divided by the numbers of items in each group, factorial) the answer should be (7!/4!3! = 35), but to be frank, my confidence had been shaken a bit with my crazy results while calculating the Farkel numbers, so I wanted a second way of verifying that the number that I arrived at computationally was actually, llike, correct.
After a few moments, I came across a rather whimsical method of figuring this out that did not involve writing a cumbersome computer program to actually step through the process.
If one represents each algebra book with a 0 and each geometry book with a 1 (so that AAGAGGA is represented by 0010110), the problem reduces to figuring out how many 7-bit binary numbers contain exactly three 1s.
Now frankly, the idea of writing out all 128 (2^7) binary numbers and crossing out the ones that don't fit the criteria didn't seem like much of a path to a solution, but it occurred to me to consider a 7-bit binary number as a two-digit hexadecimal number (between 0x00 and 0x7F), and after writing out 0 through 7 in one column and 0 through F in another column, and then writing the number of 1s in each of these twenty-four numbers, it was fairly straightforward to combine columns and figure out how many numbers contain only three 1s. That answer is 35.
This really didn't bring me much closer to the question that's really bugging me, which is (restated using a more sensible formulation): In how many unique ways can I arrange two red blocks, two yellow blocks, and two blue blocks in a row next to each other?
I don't know of any easy way to do base-3 calculations, so instead, I turned to an allied question: In how many ways can I arrange two red blocks and four green blocks in a row next to each other?
I used the same shortcut, letting 1 represent red and 1 represent green, except that now, the range of hex numbers I was dealing with had narrowed to between 0x00 and 0x3F). The answer was 15.
(This, by the way, addressed the question of how many ways, given two specific numbers, can six dice come up with one number on four of them and the second number on the other two? If we figure six possibilities for the first number, and five for the second, that means there ought to be 6x5 = 30 ways the aforementioned 15 combinations can show up, or 30 x 15 = 450 in all. But I digress...)
Using the same "logic" (for me, a very slippery term when dealing with probability calculations), I asked myself "If I were to replace the four green blocks with two yellow blocks and two blue blocks, in how many unique ways could I arrange these new blocks?" Here, it was sufficient to just write out the numbers from 0x0 to 0xF in binary, let 1 denote yellow and 0 denote blue, and cross out any number that didn't have two 1s. What's left is 6 numbers.
If I've done this right, then there ought to be 15 x 6 = 90 ways to arrange six dice, where two of the dice show some number, two more show another number, and the last two show a third number. And this is where I get stuck.
Because if we assume that there are 6 alternatives for the first number, 5 for the second number, and 4 for the third number, then there are 6x5x4 ways to get those 90 arrangements of three "pairs" of dice, or (6x5x4x90 =) 10800 ways. The problem is, several sources I've looked at online say the right number is 1800.
My math would appear to be off by a factor of exactly 6, but where?
UPDATE: On a whim, as a quick-and-dirty statistical attempt at getting my bearings, I rolled my Farkel dice 50 times and recorded the results. I got one four-of-a-kind, 9 triples, two occurrences of three pairs, and 26 occurrences of two pairs. As there are 46,656 different ways to roll 6 dice, if there were 10,800 ways of coming up with three pairs, one might not be surprised to end up with 10 or so occurrences, which clearly did not happen. If the online figure is correct, I should have gotten about two occurrences, which is what occurred. This is additional evidence that my math is "off." Al, well...
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2014-01-11 06:13 am (UTC)no subject
Date: 2014-01-11 06:49 am (UTC)As tomorrow is a Saturday, I'm burning a little of the ol' midnight oil on this. Film at, um, about 1 am.
:^)
no subject
Date: 2014-01-11 12:48 pm (UTC)This is given by the binomial coefficient (http://en.wikipedia.org/wiki/Binomial_coefficient), nchoosek(N,k)=(N!)/(k! * (N-k)!), which tells you how many ways there are to pick k things out of N things when the order of your picking is not significant.
In this case, nchoosek(7,3) = (7!)/(3! * 4!) = 35.
> I don't know of any easy way to do base-3 calculations, so instead, I turned to an allied question: In how many ways can I arrange two red blocks and four green blocks in a row next to each other?
In this case you have six things, and you want to pick 2 of them to be red, so the answer is nchoosek(6,2) = 6!/(2!4!) = 15.
Of course, you can also phrase this as having 6 things and wanting to pick 4 things to be green. The answer comes out the same: nchoosek(6,4) = nchoosek(6,2).
> This really didn't bring me much closer to the question that's really bugging me, which is (restated using a more sensible formulation): In how many unique ways can I arrange two red blocks, two yellow blocks, and two blue blocks in a row next to each other?
Here we start with 6 things, and pick 2 to be red. There are nchoosek(6,2)=15 ways to do this. Then, of the remaining 4 things, we want to pick 2 to color yellow. There are nchoosek(4,2)=6 ways to do this. Finally, we pick 2 of the remaining 2 things to paint blue. There is only nchoosek(2,2)=1 way to do this.
Thus the total number of ways to do the coloring is nchoosek(6,2)*nchoosek(4,2)*nchoosek(2,2) = 90.
> If I've done this right, then there ought to be 15 x 6 = 90 ways to arrange six dice, where two of the dice show some number, two more show another number, and the last two show a third number.
yup!
> Because if we assume that there are 6 alternatives for the first number, 5 for the second number, and 4 for the third number, then there are 6x5x4 ways to get those 90 arrangements of three "pairs" of dice, or (6x5x4x90 =) 10800 ways. The problem is, several sources I've looked at online say the right number is 1800. My math would appear to be off by a factor of exactly 6, but where?
The problem is that saying there are 6 ways to choose the first number, 5 ways to choose the second number, and four ways to choose the third number, is that this implies that, say, having the three numbers be (1,2,3) would be distinct from (2,1,3). But these are equivalent configurations (two 1's, two 2's, two 3's - there's no sense of ordering).
So we have to divide 6x5x4 by the number of possible orderings of three numbers, which is 3!=6. That's your factor of six.
no subject
Date: 2014-01-11 04:50 pm (UTC)The light begins to dawn!