(New page: Am I missing something "obvious" on how to do this one? I know that there are 26! total permutation, but I can't think of any "fancy" ways to count for things like first 13 in alphabetic ...) |
|||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
Am I missing something "obvious" on how to do this one? I know that there are 26! total permutation, but I can't think of any "fancy" ways to count for things like first 13 in alphabetic order, without starting to list them all which is definately not the point of such a problem. Please help --[[User:Mnoah|mnoah]] 17:03, 8 October 2008 (UTC) | Am I missing something "obvious" on how to do this one? I know that there are 26! total permutation, but I can't think of any "fancy" ways to count for things like first 13 in alphabetic order, without starting to list them all which is definately not the point of such a problem. Please help --[[User:Mnoah|mnoah]] 17:03, 8 October 2008 (UTC) | ||
| + | |||
| + | |||
| + | ---- | ||
| + | |||
| + | One way to do this problem is just by dividing all 26! ways into some number of groups of the same size, one of which is the desired group (it has all the ones we want to count and none that we don't). | ||
| + | |||
| + | For example, consider just the letters ABCD. We want the first two letters to be in alphabetical order. Then ABCD, ABDC, ACBD, ACDB, ADBC, ADCB all fit, while BACD, BADC, CABD, CADB, DABC, DACB do not. Here we have two groups of the same size, one of which we want to count. Since we have 2 groups of the same size and 4! overall, we don't need to mess with how many are in each group directly, it's just 4!/2 | ||
| + | |||
| + | We can create a similar example for ABCDEF. There's 720 such combinations, so it's impractical to list them all, but you can divide them up among multiple groups of equal size based on some rule based on order of their first three letters. | ||
| + | |||
| + | The way you can prove they are of equal size is by establishing a one to one correspondence between elements in one group and elements in another. For example, in the case of 4 letters, link elements from the first group with elements of the second group by changing the order of the first two letters. ABCD can be linked with BACD (the first and second letter are switched) and BCDA can be linked with CBDA (the first and second letter are switched) | ||
| + | |||
| + | By using 26 letters instead of 6 or 4, you can answer the problem. The trick is just figuring the rule on how to define the groups and what items go where. | ||
| + | |||
| + | |||
| + | ---- | ||
| + | |||
| + | I found the last part to be interesting. The question was (paraphrased) "What is the probability that z comes after b and a?" (It may be before, but the difference is negligible.) One way to solve this would be to come up with all the ways to put z after both b and a, and then divide by 26!. However, the trickier/easier way would be to simply notice that we can group permutations of 26 letters into groups of 6, where all letters but a, b, and z are fixed. Then, we notice that in exactly two of the six permutations in each group, namely the ones with a, b, and z ordered as (a, b, z) and (b, a, z), z comes before a and b. Thus, we have a 2/6 = 1/3 chance that z comes after both a and b. (Coincidentially, we could use this to show that there are 26!/3 ways to permute 26 letters such that z comes after both a and b, since the probability would then be (26!/3)/(26!) = 1/3.) | ||
| + | |||
| + | --[[User:Thomas34|Thomas34]] 20:01, 10 October 2008 (UTC) | ||
| + | |||
| + | ---- | ||
| + | |||
| + | I think that's probably a better example of this method than problem 10 itself. Also, the suggestion Uli gave in class to solve this problem is similar to this method. | ||
Latest revision as of 19:05, 10 October 2008
Am I missing something "obvious" on how to do this one? I know that there are 26! total permutation, but I can't think of any "fancy" ways to count for things like first 13 in alphabetic order, without starting to list them all which is definately not the point of such a problem. Please help --mnoah 17:03, 8 October 2008 (UTC)
One way to do this problem is just by dividing all 26! ways into some number of groups of the same size, one of which is the desired group (it has all the ones we want to count and none that we don't).
For example, consider just the letters ABCD. We want the first two letters to be in alphabetical order. Then ABCD, ABDC, ACBD, ACDB, ADBC, ADCB all fit, while BACD, BADC, CABD, CADB, DABC, DACB do not. Here we have two groups of the same size, one of which we want to count. Since we have 2 groups of the same size and 4! overall, we don't need to mess with how many are in each group directly, it's just 4!/2
We can create a similar example for ABCDEF. There's 720 such combinations, so it's impractical to list them all, but you can divide them up among multiple groups of equal size based on some rule based on order of their first three letters.
The way you can prove they are of equal size is by establishing a one to one correspondence between elements in one group and elements in another. For example, in the case of 4 letters, link elements from the first group with elements of the second group by changing the order of the first two letters. ABCD can be linked with BACD (the first and second letter are switched) and BCDA can be linked with CBDA (the first and second letter are switched)
By using 26 letters instead of 6 or 4, you can answer the problem. The trick is just figuring the rule on how to define the groups and what items go where.
I found the last part to be interesting. The question was (paraphrased) "What is the probability that z comes after b and a?" (It may be before, but the difference is negligible.) One way to solve this would be to come up with all the ways to put z after both b and a, and then divide by 26!. However, the trickier/easier way would be to simply notice that we can group permutations of 26 letters into groups of 6, where all letters but a, b, and z are fixed. Then, we notice that in exactly two of the six permutations in each group, namely the ones with a, b, and z ordered as (a, b, z) and (b, a, z), z comes before a and b. Thus, we have a 2/6 = 1/3 chance that z comes after both a and b. (Coincidentially, we could use this to show that there are 26!/3 ways to permute 26 letters such that z comes after both a and b, since the probability would then be (26!/3)/(26!) = 1/3.)
--Thomas34 20:01, 10 October 2008 (UTC)
I think that's probably a better example of this method than problem 10 itself. Also, the suggestion Uli gave in class to solve this problem is similar to this method.
