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