Counting 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 is a permutation 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}\]

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.

All possible arrangements or permutations of a,b,c,d.

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.

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 the following:

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:

1. If the list contains a single element, then return the single element.
2. 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 \cdots \times 1 = n!.\ _\square\]

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.\)

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 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 list shows, \(n!\) grows very quickly with \(n\); \(60!\), for example, is already larger than the number of atoms in the observable universe.

In how many ways can a party of 4 men and 4 women be seated at a circular table so that no two women are adjacent??

---

The 4 men can be seated at the circular table such that there is a vacant seat between every pair of women.

The number of ways in which these 4 men can be seated at the circular table is \(3! = 6.\) Now the 4 vacant seats can be occupied by the women in \( 4! = 24\) ways. Thus, the required number of ways is \(6\times24 = 144 \) ways. \(_\square\)

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 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.

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 repetition of digits?

---

The hundredth place cannot contain \(0\), but we can put any of the other numbers in the hundredths place. So, it can be filled in \(9\) ways. Now we cannot use the number we used in the hundredths place in the tenth place. But we can use \(0\). So, we can fill the tenth place in \(9\) ways, too. The units digit can be filled in \(8\) places since two numbers are now unavailable. So, the total number of 3-digit numbers without repetition of digits that can be formed is \(9×9×8 = 648.\ _\square\)

How many 4-letter passwords can be formed if the characters allowed to use without repetition are 0, 1, 2, 3, ..., 9 and A, B, C, ..., Z and a, b, c, ..., z?

---

We have \(26+26+10=62\) choices to choose from. So we have to arrange 4 objects out of 62 available objects, the number of ways of doing which is equal to \(\frac {62!}{(62-4)!}=62\times 61\times 60\times 59=13388280.\) \(_\square\)

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 canceling 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!}{\big(13-(k-1)\big)!} = 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) & \quad ? \quad 12 \times 11 \times \cdots \times (12 - k + 1)\\\\ 13 & \quad ? \quad (12 - k + 2) \times (12 - k + 1). \end{align}\]

Now since \(1 < k \leq 12\), we can check that for \(k = 10, 11, 12\), and we have

\[13 > (12 - k + 2) \times (12 - k + 1). \]

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\)

Here are some examples for permutations with repetition:

Main Article: Permutations with Repetition

How many different 6-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 5's, so the repeated 5's can be permuted in \(2!\) ways and the six digit number will remain the same. Similarly, there are three 7's, so the repeated 7's can be permuted in \(3!\) ways and the six digit number will remain the same. This shows the number of different 6-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\]

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\)

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.

• Combinations
• Derangements
• Permutations with Restriction