Permutations
In combinatorics, a permutation is an ordering of a list of objects. For example, arranging four people in a line is equivalent to finding permutations of four objects. More abstractly, each of the following are permutations of the letters \( a, b, c,\) and \(d\):
\[\begin{align} → \ & a, b, c, d\\ → \ & a, c, d, b\\ → \ & b, d, a, c\\ → \ & d, c, b, a\\ → \ & c, a, d, b \end{align}\]
All possible arrangements or permutations of a,b,c,d.
Note that all of the objects must appear in a permutation and two orderings are considered different if some object appears in a different place in the orderings.
Permutations are important in a variety of counting problems (particularly those in which order is important), as well as various other areas of mathematics; for example, the determinant is often defined using permutations.
Contents
Permutations of a set of distinct objects
The simplest example of a permutation is the case where all objects need to be arranged, as the introduction did for \(a, b, c, d.\) The question thus becomes:
Given a list of objects, how can all possible permutations be listed?
There are several algorithms for enumerating all permutations; one example is the following recursive algorithm:
- If the list contains a single element, then return the single element.
- If the list contains more than one element, loop through each element in the list, returning this element concatenated with all permutations of the remaining \(n-1\) objects.
Lisa has 5 different ornaments she wants to arrange in a line on her mantle. How many ways can she arrange the ornaments?
We can think of Lisa’s mantle as having five positions in a line. There are 5 ornaments, which gives 5 choices for which ornament goes into the first position. After placing the first ornament, there are 4 choices of which ornament to put into the second position . Repeating this argument, there are 3 choices for the third position, 2 choices for the fourth position and 1 choice for the last position. By the rule of product, the total number of ways to place the ornaments is \[ 5 \times 4 \times 3 \times 2 \times 1 = 120. \ _\square\]
More generally,
Given a list of \( n\) distinct objects, how many different permutations of the objects are there?
Since each permutation is an ordering, start with an empty ordering which consists of \( n\) positions in a line to be filled by the \(n\) objects. There are \( n\) choices for which object to place in the first position. After the first object is placed, there are \(n-1\) remaining objects, so there are \( n-1\) choices for which object to place in the second position. Repeating this argument, there are \( n-2\) choices for the third position, \( n-3\) choices for the fourth position, and so on. For the \( n^\text{th}\) position, the number of choices is \( n - (n-1)= 1.\) Then the rule of product implies the total number of orderings is
\[ n \times (n-1) \times (n-2) \times (n-3) \times \ldots \times 1 = n!.\]
For a positive integer \(n\), the notation \( n!\) denotes the factorial of \(n\) and refers to the product of all positive integers from \( 1\) to \( n\). Note that \( 0!\) is the empty product and is defined to be \( 1\).
The argument above shows the following result:
The number of permutations of \(n\) distinct objects is \(n!\), the factorial of \(n.\) \(_\square\)
Jack is playing with a standard deck of \(52\) playing cards. He shuffles the cards and then turns the top card over to show an ace of spades. If he continues to deal the cards from the top of the deck, how many different permutations are there for the remaining cards in the deck?
Since the first card is an ace of spades, there are \(51\) remaining distinct playing cards in the deck. Then there are \(51!\) different permutations of the remaining playing cards. \(_\square\)
The first few values of \(n!\) are
\[\begin{array} &1!= 1, &2! = 2, &3! = 6, &4! = 24, &5! =120, &6! = 720, &7! = 5040, &\ldots .\end{array}\]
As the above table shows, \(n!\) grows very quickly with \(n\); \(60!\), for example, is already larger than the number of atoms in the observable universe.
Suppose Ellie is choosing a secret passcode consisting of the digits \(0,1,2, \ldots, k\) for some \(k \leq 9\). She would like her passcode to use each digit at most once and because she is concerned about security, she would like to choose a value of \(k\) such that the number of possible permutations is at least 250,000. What is the smallest value of \(k\) Ellie can use?
Note that \(8! = 40320\) and \(9! = 362880.\) Therefore, Ellie needs at least \(9\) digits in her passcode. Since the digits start from \(0\), the smallest value of \(k\) Ellie can choose is \(k = 8.\) \(_\square\)
More precisely, Stirling's formula states that \(n!\) is approximated by
\[ n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n.\]
The precise bounds for the approximation are shown in the inequality
\[ \sqrt{2\pi}\ n^{n+1/2}e^{-n} \le n! \le e\ n^{n+1/2}e^{-n}. \]
In the case that the the objects are not distinct, we have a permutations with repetition problem; in the case that the permutation must satisfy certain constraints, we have a permutations with restriction problem.
Permutations of a subset of distinct objects
Consider the following problem:
Lisa has 13 different ornaments and wants to put 4 ornaments on her mantle. In how many ways is this possible?
Using the product rule, Lisa has 13 choices for which ornament to put in the first position, 12 for the second position, 11 for the third position, and 10 for the fourth position. So the total number of choices she has is \( 13 \times 12 \times 11 \times 10 \). Using the factorial notation, the total number of choices is \( \frac{13!}{9!} \).
Using the same argument, we can proceed with the general case. If we have \( n \) objects and want to arrange \( k \) of them in a row, there are \( \frac{n!}{(n-k)!} \) ways to do this. This is also known as a \(k\)-permutation of \(n\), and is denoted by \( P_k ^n \).
How many 3-digit numbers can be formed without repitition of digits?
The hundredth place cannot contain \(0\). But, we can put any of the other numbers in the hundredth place. So, it can be filled in \(9\)ways. Now we cannot use the number we used in the hundredth place in the tenth place. But, we can use \(0\). So, we can fill the tenth place in \(9\) ways too. And the units's digit can be filled in \(8\) places since two numbers are now unavailable. So, the total number of 3-digit numbers without repitition of digits that can be formed = \((9×9×8) = \boxed{648}\). \(_\square\)
How many 4 letter passwords can be formed if the allowed characters are 0,1,...9 and A,B,C...Z and a,b,...z?
We have 26+26+10 choices to choose from. So we have to arrange 4 objects out of 62 available objects, which is equal to \(\frac {62!}{(62-4)!}=62×61×60×59=13388280\) and thats the answer
How many 4 letter passwords can be formed if the allowed characters are 0,1,...9 and A,B,C...Z and a,b,...z?
We have 26+26+10 choices to choose from. So we have to arrange 4 objects out of 62 available objects, which is equal to \(\frac {62!}{(62-4)!}=62×61×60×59=13388280\) and thats the answer
Suppose Lisa has 13 different ornaments and would like to place 4 of the ornaments in a row on her mantle, and Anna has 12 different ornaments and would like to place 5 of the ornaments in a row on her mantle. Does Lisa have more choices in the possible number of ways to place her ornaments or does Anna?
Since Lisa has 13 ornaments and would like to place 4 of them on her mantle, she has
\[\frac{13!}{(13-4)!} = \frac{13!}{9!} = 13 \times 12 \times 11 \times 10\]
choices in the possible number of ways to place her ornaments. Similarly, since Anna has 12 ornaments and would like to place 5 of them on her mantle, she has
\[\frac{12!}{(12-5)!} = \frac{12!}{7!} = 12 \times 11 \times 10 \times 9 \times 8\]
choices in the possible number of ways to place her ornaments. Now,
\[ 13 \times 12 \times 11 \times 10 < 12 \times 11 \times 10 \times 9 \times 8\]
since by cancelling terms, we can see that \(13 < 9 \times 8\). This shows that Anna has more choices in the possible ways to place her ornaments. \(_\square\)
In general, if Anna has \(12\) different ornaments and would like to place \(k\) of them on the mantle (with \(1 < k \leq 12\)) and if Lisa has \(13\) different ornaments and would like to place \(k-1\) of them on a mantle, for what values of \(k\) does Anna have more choices in the possible number of ways to place all of her ornaments?
Since Anna has \(12\) ornaments and would like to place \(k\) of them on her mantle, she has
\[\frac{12!}{(12-k)!} = 12 \times 11 \times \cdots \times (12 - k + 1) \]
choices in the possible number of ways to place her ornaments. Similarly, since Lisa has \(13\) ornaments and would like to place \(k-1\) of them on her mantle, she has
\[\frac{13!}{(13-(k-1))!} = 13 \times 12 \times \cdots \times (13 - k + 2) \]
choices in the possible number of ways to place her ornaments. Now, let's compare the two quantities by cancelling terms:
\[\begin{align} 13 \times 12 \times \cdots \times (13 - k+2) & \qquad ? \qquad 12 \times 11 \times \cdots \times (12 - k + 1)\\ 13 & \qquad ? \qquad (12 - k + 2) \times (12 - k + 1). \end{align}\]
Now since \(1 < k \leq 12\), we can check that for \(k = 10, 11, 12\), we have
\[13 > (12 - k + 2) \times (12 - k + 1), \]
and for \(k = 1, 2, \ldots ,9\), we have
\[13 < (12 - k + 2) \times (12 - k + 1).\]
This shows that Anna has more choices in the possible ways to place her ornaments for \(k = 1,2, \ldots ,9\). \(_\square\)
Permutations with Repetition
Here are few appropriate examples for permutations with repetition.
Main Article: Permutations with Repetition
How many different six digit numbers can be obtained by using all of the digits \[5,5,7,7,7,8? \]
We first count the total number of permutations of all six digits. This gives a total of
\[6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720 \]
permutations. Now, there are two 5s, so the repeated 5s can be permuted in \(2!\) ways and the six digit number will remain the same. Similarly, there are three 7s, so the repeated 7s can be permuted in \(3!\) ways and the six digit number will remain the same. This shows the number of different six digit numbers using all of the digits is
\[ \frac{6!}{2! 3!} = \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1 }{2! 3!} = 5 \times 4 \times 3 = 20 \times 3 = 60.\ _\square\]
\[\large \text{HUNG WOEI NEOH}\]
From the name above how many words with or without meaning can be created auch that the relative order of the consonant and vowels do not change.
Details and assumptions: Relative order of consonants and vowels do not change means that vowels and consonants should occupy the same place as they did in the original name but they can be juggled with their places.
Permutations with Restriction
Main Article: Permutations - With Restriction
Lisa has 4 different dog ornaments and 6 different cat ornaments that she wants to place on her mantle. All of the dog ornaments should be consecutive and the cat ornaments should also be consecutive. How many ways can they be arranged?
We have to decide if we want to place the dog ornaments first, or the cat ornaments first, which gives us 2 possibilities. We can arrange the cat ornaments in \( 6!\) ways, and the dog ornaments in \( 4!\) ways. Hence, by the rule of product, there are \( 2 \times 6! \times 4! = 34560\) ways to arrange the ornaments. \(_\square\)
Permutations - Problem Solving
Given a permutation problem, how do we determine which category the problem falls under and which technique should be applied to solve the problem? It may be useful to first ask yourself a few questions:
- Are the objects all distinct?
- How many objects are there in total?
- How many objects are we asked to place into an ordering?
- Are there any restrictions on the objects or on the ordering?
Based on the answers to these questions, it may become easier to decide which technique should be applied. Working through many examples is one way to become better at recognizing whether a permutation problem should fall in the category of permutation with or without repetition, or permutation with or without restriction.