Hi there. In this math post, I take a look on the number of key arrangements (permutations) on a circular keychain. I came across this type of problem from my work. It did not look familiar to me as it is not specialty. With some research and thinking I think I understand the logic that goes behind the problem and its solution.
Math text rendered with Quicklatex.com and screenshots are from a whiteboard website.
Topics
- Factorials Review
- Number Of Key Arrangements On Circular Keychain Problem
- Dealing With Duplicate Keys
Factorials
The concept of a factorial looks scary but it is not that bad. Given a whole number n that is at least 1, the factorial is defined by:
You can have the factorial in the ascending order like this.
Example
There are four chairs in a row. How many ways can Alex, Betty, Cheryl and Douglas be seated?
You can lay the chairs out from left to right. It would like Chair 1, Chair 2, Chair 3, Chair 4.
Starting from Chair 1 there are 4 choices or candidates that can be seated. After someone is seated in Chair 1 there are 3 people left to be seated in chair 2. Next there would be 2 people left to be seated in chair 3. The last person would be seated in chair 4.
The number of ways that Alex, Betty, Cheryl and Douglas can be seated would be 4 x 3 x 2 x 1 = 24. This is to same as 4 factorial.
Number Of Key Arrangements On Circular Keychain Problem
In the example above, the chairs are arranged in a row. There is a far left seat and there is a far right seat. When it comes to a circular keychain, there is no end in the keychain. This is important to note as we cover this problem.
Problem
Jack has 5 keys to put in his circular keychain. How many different arrangements are there for Jack with the keys?
With the first key there is one way as the circular keychain can be turned. The second key can be on the left side of the first key or the right side of the first key. The position is still the same as this second key can be shifted to the other side. (Picture below with K1 as key 1, K2 as key 2)
We have the third key next. Assume that key 2 is on the left side of key 1. This third key can be in between key 2 and key 1. Key 3 can also be on the left of key 2 which is the same as the right side of key 1 in the ciruclar keychain. This would be two choices.
For the fourth key, it would be three choices. There are two choices in between the 3 keys and 1 choice which represents the far left side or far right side.
With the fifth and final key, there would be four choices.
The number of different arrangements on the circular keychain for 5 keys is an ascending factorial of 1 x 2 x 3 x 4 = 4! = 24.
General Formula
Given n number of keys (n is a whole positive number) the number of different arrangements for n keys is (n - 1)!. I use the ascending factorial starting from 1 this time around.
Dealing With Duplicate Keys Example
Example
Tyler has seven keys where 3 of the keys are the same. The other 4 keys are different keys. How many different ways can these 7 keys be arranged on a circular keychain?
As there are seven keys it would be (7 - 1)! or 6 factorial.
To deal with the three keys being the same we divide the 6 factorial by 3 factorial.
The solution above is a slight variation to permutations involving duplicates. With permutations involving duplicates if there are n objects/keys with n1 of one type n2 of a seccond type up to nk of a k-th type where:
then the number of arrangements (permutations) is:
From the example we change n factorial from the numerator to (n - 1)!. As there are 3 duplicates out of 7, the denominator would have 3! times 1 times 1. The times 1 is omitted in the fraction as one factorial is just 1.
