Discrete math fun :)
Ok so I've got a question on a problem. It's not homework, I'm studying for the first test in the class. I already know the answer, I just don't know how to get there. Anyway, here it is :D
"How many ways can 6 keys be placed on a circular key ring? Both sides of the ring are the same, and there is no way to tell which is the 'first' key on the ring"
No clue how to get to the answer, I've tried multiple approaches and both got me quite a bit off.
"How many ways can 6 keys be placed on a circular key ring? Both sides of the ring are the same, and there is no way to tell which is the 'first' key on the ring"
No clue how to get to the answer, I've tried multiple approaches and both got me quite a bit off.
circular permutation
P_n = (n-1)! = 120
but the ring is symmetric, so
P_n_sym = (n-1)!/2 = 60
P_n = (n-1)! = 120
but the ring is symmetric, so
P_n_sym = (n-1)!/2 = 60
Ah I had no idea about circular permutation. Professor nor the book mentioned, was just one of the questions. Could you explain as to why this works? I understand why regular permutations work for their situations, but have never been in contact with circular permutation.
Thanks
Thanks
I'm going to use 3 keys for the derivation, since it's less work for me :P, but the idea can be extended to an arbitrary integer n.
If you place the keys in a straight line on a table, there are 3! ways to do it.
key1, key2, key3
1,3,2
2,1,3
2,3,1
3,2,1
3,1,2
If you place the keys on a ring, the same possibilities are available.
1,2,3
1,3,2
2,1,3
2,3,1
3,2,1
3,1,2
Now imagine you have a bird's eye view of the ring with the keys on it.
The 2,1,3 order is just 1,3,2 only rotated clockwise one key. (with 3 keys, rotate the ring 120o), so 2,1,3 is not a distinct permutation.
The 2,3,1 is the same thing as 1,2,3 just rotated 240o clockwise.
3,2,1 is 1,3,2 rotated clockwise two keys.
3,1,2 is 1,2,3 rotated one key.
This means that, for circular permutations, you divide the number of regular permutations, n!, by the number of rotation for each distinct permutation, n (for this example, this number is 3: rotate 0 keys, rotate 1 key, or rotate 2 keys.)
So, for circular permutations, P_n = n!/n = (n-1)!
Since your problem states that both sides of the ring are the same, symmetry is applied (i.e., counter clockwise rotations are allowed, and the number of rotations for each distinct permutation is 2n.
P_n_sym = n!/2n = (n-1)!/2
EDIT: I kan spel gud won day (typos fml)
If you place the keys in a straight line on a table, there are 3! ways to do it.
key1, key2, key3
1,3,2
2,1,3
2,3,1
3,2,1
3,1,2
If you place the keys on a ring, the same possibilities are available.
1,2,3
1,3,2
2,1,3
2,3,1
3,2,1
3,1,2
Now imagine you have a bird's eye view of the ring with the keys on it.
The 2,1,3 order is just 1,3,2 only rotated clockwise one key. (with 3 keys, rotate the ring 120o), so 2,1,3 is not a distinct permutation.
The 2,3,1 is the same thing as 1,2,3 just rotated 240o clockwise.
3,2,1 is 1,3,2 rotated clockwise two keys.
3,1,2 is 1,2,3 rotated one key.
This means that, for circular permutations, you divide the number of regular permutations, n!, by the number of rotation for each distinct permutation, n (for this example, this number is 3: rotate 0 keys, rotate 1 key, or rotate 2 keys.)
So, for circular permutations, P_n = n!/n = (n-1)!
Since your problem states that both sides of the ring are the same, symmetry is applied (i.e., counter clockwise rotations are allowed, and the number of rotations for each distinct permutation is 2n.
P_n_sym = n!/2n = (n-1)!/2
EDIT: I kan spel gud won day (typos fml)
Last edited on
Not quite. Although for n=3 the order doesn't matter, it does for larger values. 1234 and 1324 are different circular permutations, yet the same combination. Likewise for 1234 and 1243.
Ooh that makes sense. I didn't think about larger numbers. This whole when to use combination vs permutation is the one thing in struggling with for this coming test
Topic archived. No new replies allowed.