Please Login to access more options.

Problem 5 (Number Of Permutations)

Given finite set $X$ with $n$ elements, how many permutations are there of $X$?

  • Show that if $X=\{1\}$, then there is only one permutation of $X$.
  • Show that if $X=\{1,2\}$, then there are two permutations of $X$. List them.
  • Make a list of all permutations of $X=\{1,2,3\}$, and then of $X=\{1,2,3,4\}$. What pattern do you see?
  • Make a conjecture about the number of permutation of $X$ if $|X|=n$. Then prove your conjecture.

Solution

Let $X$ be a finite set with $n$ elements. We will discover how many permutations of $X$ exist. Recall a permutation is a bijection from $X$ to $X$. This means the permutation is a function that is both one-to-one and onto. This means we must use every element that is in $X$, and have a unique home for each element in the set after the function has finished. Note that each home for the elements must also be in the set $X$.

We will first let $X=\{1\}$. Note this means $n=1$. Then the only permutation is the identity permutation $id_x(x)=x$. Since we only have one element, the element must remain the same.

Now we consider $X=\{1,2\}$. For the first element, we see that there are two positions we can place it in, namely $1$ or $2$. Regardless of which place we choose, we will have one place left for the $2$, giving us $2\cdot 1=2$ total permutations. They are $$ \begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix}, \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}. $$

We will list all the permutations of $X=\{1,2,3\}$ as follows: $$ \begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}, \begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}, \begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}, \begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}, \begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}, \begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}. $$

The permutations of the set $X=\{1, 2, 3, 4\}$ are listed below: $$ \begin{pmatrix} 1 & 2 & 3 & 4\\1& 2& 3& 4\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\2& 3& 1& 4\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\3& 4& 1& 2\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\4& 1& 2& 3\end{pmatrix},\\ \begin{pmatrix} 1 & 2 & 3 & 4\\1& 2& 4& 3\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\2& 3& 4& 1\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\3& 4& 2& 1\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\4& 1& 3& 2\end{pmatrix},\\ \begin{pmatrix} 1 & 2 & 3 & 4\\1& 3& 2& 4\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\2& 4& 1& 3\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\3& 2& 4& 1\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\4& 2& 1& 3\end{pmatrix},\\ \begin{pmatrix} 1 & 2 & 3 & 4\\1& 3& 4& 2\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\2& 4& 3& 1\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\3& 1& 2& 4\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\4& 2& 3& 1\end{pmatrix},\\ \begin{pmatrix} 1 & 2 & 3 & 4\\1& 4& 2& 3\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\2& 1& 3& 4\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\3& 1& 4& 2\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\4& 3& 1& 2\end{pmatrix},\\ \begin{pmatrix} 1 & 2 & 3 & 4\\1& 4& 3& 2\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\2& 1& 4& 3\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\3& 2& 1& 4\end{pmatrix}, \begin{pmatrix} 1 & 2 & 3 & 4\\4& 3& 2& 1\end{pmatrix}. $$

This can be read as each entry being an individual permutation function, where the input is the set $\{1, 2, 3, 4\}$, and then the permutation changes places each element of the set into the new position specified by the list of numbers. For example for the permutation $\{1, 4, 3, 2\}$, a passed in 1 will be sent to position 1, a 2 will be sent to position 4, the 3 will remain the in the same location, and the 4 will go to position 2.

We claim the number of permutations on the set $X$ will equal $n!$. Let's look first at the finite example of $X=\{1, 2, 3, 4\}$. There are four places we can choose to place the 1, but once we do that, the 2 only has three open locations. From here two spots are left for the three, and only one for the 4. This reads $4\cdot 3\cdot 2\cdot 1 = 4!$. This easy generalizes to the case where the set $X$ contains $n$ elements. Then we have $n$ positions to pick from for the first element, then $n-1$ for the second, then $n-2$ and so on. To count all these up we multiply, which gives $(n)\cdot (n-1)\cdot\ (n-2)\cdot \cdots \cdot (2) \cdot (1) = n!$. Thus the number of permutations in the set is equal to the factorial of the number of elements in the set. $\square$

Tags

Change these as needed.

  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.