(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 ...) |
|||
| 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) | ||
Revision as of 13:40, 8 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)
