permutations
Permutations
Suppose we have five distinct items and wish to find the number of possibilities to place them in order. In this case, the order matters for each possibility thus called a permutation. Now, for the first position we have five distinct items to choose from, for the second position we're down to four distinct items to choose from and so on. Then, the total number of possibilities would be \[5\cdot4\cdot3\cdot2\cdot1=5!=120\].
Now assume we only wish to select three out of five. This would leave us with \[5\cdot4\cdot3=60\] possibilities. Notice that \[5\cdot4\cdot3=\frac{5\cdot4\cdot3\cdot2\cdot1}{2\cdot1}=\frac{5!}{(5-3)!}\]. This is in fact the general rule where suppose we have \[n\] distinct items and wish to select \[k\] of them and place them in order, then he total number of possibilities is, as demonstrated above, is \[P(n,k)=\frac{n!}{(n-k)!}\].
Example 1
Suppose we have seven distinct items and we want to arrange five of them in a circle. Assume the absolute position of the items does not matter. Now, logically there are \[P(7,5)=\frac{7!}{(7-5)!}=2520\] possible ways we can achieve this. However, since the absolute position is irrelevant, that means for every permutation, say "ABCDE", when arranged in a circle, becomes identical to "BCDEA", "CDEAB", "DEABC" and "EABCD". This means that out of the 2520 possible permutations, only \[\frac{2520}{5}=504\] permutations are truly unique.
Example 2
Suppose we have a string of letters "ABCDEF" and we are tasked to find the number of possible ways to permute the string such that "A" and "B" are not adjacent. The trick here is to first find the total number of possible permutations, \[P(6,6)\], then subtract it by the number of "incorrect" permutations.
First, note that "AB" itself has two possible permutations "AB" and "BA". Then, there are a total of five ways that "AB" can be together, i.e. "AB????", "?AB???", "??AB??" and etc. Notice that if we treat "AB" as a single letter, the calculation becomes as simple as permuting all five distinct letters, i.e. \[P(5,5)\]. So, the total "incorrect" permutations would be \[P(5,5)+P(5,5)\].
Together, all the number of possible permutations would be \[P(6,6)-P(5,5)-P(5,5)=480\].
Permuting sets with repeated indistinguishable elements
Suppose we have a string of letters "AABBC" where both As and Bs are identical/indistinguishable. How many possible permutations are there?
Now, assume we have five initially empty slots and since order matters here we'll choose in which positions to put the As first. The manual way would be that if we slot A into the first slot, " A _ _ _ _ ", naturally we would have four possible ways to slot A the other four slots; if A were to be slotted into the second slot, " _ A _ _ _ ", we would have three possible unique ways to slot A into the remaining four slots (as the case "A A _ _ _" is already previously covered) and so on. This would leave us with a total of \[4+3+2+1=10\] ways. A keen eye would also notice that since we are trying to pick two slots out of five empty slots, this is essentially a combination, thus we can say that there are \[C(5,2)=10\] possible combinations of slots we can pick.
The reason why we choose to use combinations is to avoid dealing with the fact that while "AABBC" and "AABBC" are identical permutations, the formula \[P(5,5)\] does not take that into account and assumes they are different.
Next, we will choose were to put the Bs into the remaining three slots, assuming that we've already slotted both As into two of the slots. Repeating the process above would give us a total of \[C(3,2)=3\] possible combinations to slot the Bs. The remaining R no matter where we slot it will not have any effect on the total possible combinations.
Now that we've calculated all these, the total number possible permutations would be \[C(5,2)\cdot C(3,2)\cdot C(1,1)=\frac{5!}{(5-2)!\cdot2!}\cdot \frac{3!}{(3-2)!\cdot2!}\cdot1=\frac{5!}{2!\cdot2!}\].
A much easier method when we are permuting \[n\] items with repeated elements, assuming the number of repeated elements for element \[i\] is given as \[r_{i}\], is to use the formula \[\frac{n!}{r_{1}!\cdot r_{2}!\cdot r_{3}!\cdots}\].
Example 3
Suppose we have a string "111111110000". Find the number of possible permutations.
Simply using the formula would tell us there are \[\frac{12!}{8!\cdot4!}=495\] possible permutations.
Example 4
Now, suppose we have a string "AAAABBBC". All the repeated letters are indistinguishable from each other and we have an additional constraint that all four As can not be next each other, i.e. "??AAAA??" is an invalid permutation. Find the number of possible permutations.
Similar to Example 2, we'll first calculate the number of "incorrect" permutations then subtract it from the total possible permutations without any constraints. Notice that there are a total of five scenarios where the permutation would be invalid, "PPPP????", "?PPPP???", "??PPPP??" and etc. This reduces the question down to, how many ways we can permute the remaining "?". We also know that three Bs and one C must all go into the remaining four slots. So, for each scenario, there are \[\frac{4!}{3!\cdot1!}\] ways we can permute the remaining four slots. Since we have five identical scenarios, the total invalid permutations would be \[5\cdot \frac{4!}{3!\cdot1!}\].
Finally, the total possible permutation regardless of the constraints is \[\frac{8!}{4!\cdot3!\cdot1!}\], thus the answer is \[\frac{8!}{4!\cdot3!\cdot1!}-5\cdot \frac{4!}{3!\cdot1!}=260\].