Permutation

Revision as of 10:01, 25 December 2020 by Aditya404 (talk | contribs) (Video)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

A permutation of a set of $r$ objects is any rearrangement (linear ordering) of the $r$ objects. There are $r!$ (the factorial of $r$) permutations of a set with $r$ distinct objects.

One can also consider permutations of infinite sets. In this case, a permutation of a set $S$ is simply a bijection between $S$ and itself.

Video

This video goes over what Permutations & Combinations are, their various types, and how to calculate each type! It serves as a great introductory video to combinations, permutations, and counting problems in general! Permutations & Combinations Video https://youtu.be/MWNe0qbBwu4


This video is a great introduction to permutations, combinations, and constructive counting: https://www.youtube.com/watch?v=t6a4uHEwQnM&

Notations

A given permutation of a finite set can be denoted in a variety of ways. The most straightforward representation is simply to write down what the permutation looks like. For example, the permutations of the set $\{1, 2, 3\}$ are $\{1,2,3\}, \{1, 3,2\}, \{2,1,3\}, \{2,3,1\},\{3,1,2\}$ and $\{3,2,1\}$. We often drop the brackets and commas, so the permutation $\{2,1,3\}$ would just be represented by $213$.

Another common notation is cycle notation.

The Symmetric Group

The set of all permutations of an $n$-element set is denoted $S_n$. In fact, $S_n$ forms a group, known as the Symmetric group, under the operation of permutation composition.


A permutation in which no object remains in the same place it started is called a derangement.

Picking Ordered Subsets of a Set

An important question is how many ways to pick an $r$-element subset of a set with $n$ elements, where order matters. To find how many ways we can do this, note that for the first of the $r$ elements, we have $n$ different objects we can choose from. For the second element, there are $n-1$ objects we can choose, $n-2$ for the third, and so on. In general, the number of ways to permute $r$ objects from a set of $n$ is given by $P(n,r)=n(n-1)(n-2)\cdots(n-r+1)=\frac{n!}{(n-r)!}$.

Related Videos

See also