There are two particular types of counting of interest in combinatorics. One is a permutation and the other is a combination. A permutation is ordering things without repeats. A combination is arranging things without order. In this note, we study permutations and we will discuss combinations in the following note. Let us begin with an example.
Example. How many different ways can we order the three different elements of $A=\{a,b,c\}$?
Solution. We have three choices for position 1. We have two choices for position 2. And we have 1 choice for position 3. Hence, by the basic principle of counting there are $3\cdot 2\cdot 1=6$ different ways of ordering the three letters. In fact, they are \begin{array}{cc}abc & acb\\bca & bac\\cab & cba\end{array}
The above example can be generalized to ordering elements from a set of $n$ elements. By a similar account, there are $n$ choices for position 1, there are $n-1$ choices for position 2, there are $n-2$ choices for position 3, …, there is one choice for position $n$. Hence, there are $$n!:=n(n-1)(n-2)\cdots3\cdot 2\cdot 1$$ different permutations on the set of $n$ elements. The symbol $n!$ is called $n$ factorial. We define $0!=1$ for an obvious reason which will be mentioned later. Note that $n!$ is also the number of bijective (one-to-one and onto) maps from $\{1,2,\cdots,n\}$ to itself. The sage command for calculating $n!$ is factorial(n).
Example. A class in probability theory consists of 6 men and 4 women. An exam is given and students are ranked according to their performance. Assume that no students received the same score.
- How many different rankings are possible?
- If the men are ranked just among themselves and the women among themselves, how many different rankings are possible?
Solution.
- $10!=3,628,800$.
- $6!4!=(720)(24)=17280$.
Example. Mark has 10 books that he is going to put on his bookshelf. Of these, 4 are math books, 3 are physics books, 2 are computer science books, and 1 is a language book. Mark wants to arrange his books so that all the books dealing with the same subject are placed together on the shelf. How many different arrangements are possible?
Solution. There are $4!3!2!1!$ different arrangements in the order of math, physics, computer science and language. There are then $4!$ different ways to arranging the 4 subjects. Therefore, the final answer is $4!4!3!2!1!=6912$.
Example. How many different letter arrangements can be formed using the letters PEPPER?
Solution. Suppose that the 3 P’s and 2 E’s are distinguished as $P_1E_1P_2P_3E_2R$. Then there would be $6!$ permutations. Now there are $3!$ permutations among the 3P’s and $2!$ permutations among the 2 E’s. Hence, there are all $3!2!$ permutations of the form PPEPER. Therefore, there are $\frac{6!}{3!2!}=60$ possible letter arrangements of the letters PEPPER.
By a similar account, we see that there are $$\frac{n!}{n_1!n_2!\cdots n_r!}$$ different permutations of $n$ objects, of which $n_1$ are alike, $n_2$ are alike, …, $n_r$ are alike.
Example. A chess tournament has 10 competitors of which 4 are Russians, 3 are from the United States, 2 from Great Britain, and 1 from Brazil. If the tournament result lists just the nationalities of the prayers in the order in which they are placed, how may outcomes are possible?
Solution. $\frac{10!}{4!3!2!1!}=12,600$.
What if we want to arrange not all elements but only some elements from a set? Here is an example.
Example. A club of 25 members is holding an election for president, secretary and treasurer in that order. Assume that a person can hold only one position. How many different ways of choosing these officers are there?
Solution. $25\cdot 24\cdot 23$ by the basic principle of counting.
Definition. An ordered arrangement of $r$ elements selected from $n$ elements, $0\leq r\leq n$, where no two elements of the arrangement are the same, is called a permutation of $n$ objects taken $r$ at a time.The total number of such permutations is denoted by $P(n,r)$ or ${}_nP_r$.
By the basic principle of counting we find that \begin{equation}\label{eq:perm}P(n,r)=\prod_{j=0}^{r-1}(n-j)=n(n-1)(n-2)\cdots(n-r+1)\end{equation}
The expression in \eqref{eq:perm} can be written as \begin{equation}\label{eq:perm2}P(n,r)=\frac{n!}{(n-r)!}\end{equation} The sage command for calculating $P(n,r)$ is falling_factorial(n,r). Obviously, $P(n,n)=n!$. On the other hand, we have $P(n,n)=\frac{n!}{0!}$ from \eqref{eq:perm2}. Therefore, it is defined that $0!=1$.
Using the formula \eqref{eq:perm2} the answer to the question in the above example is simply $$P(25,3)=\frac{25!}{(5-3)!}=25\cdot 24\cdot 23$$
Example. Consider the digits 1, 2, 3, 4, 5.
- How many three-digit numbers can be formed if no repetition of digits can occur?
- How many three-digit numbers can be formed if repetition is allowed?
- How many three-digit numbers can be formed if only non-consecutive repetition of digits are allowed?
Solution.
- $P(5,3)=\frac{5!}{(5-3)!}=5\cdot 4\cdot 3=60$.
- $5\cdot 5\cdot 5=125$.
- $5\cdot 4\cdot 4=80$.
References: Not in particular order.
[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.
[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998