Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Permutation"

(→‎Video)
(→‎Video)
Line 3: Line 3:
 
One can also consider permutations of [[infinite]] sets.  In this case, a permutation of a set <math>S</math> is simply a [[bijection]] between <math>S</math> and itself.
 
One can also consider permutations of [[infinite]] sets.  In this case, a permutation of a set <math>S</math> is simply a [[bijection]] between <math>S</math> and itself.
 
==Video==
 
==Video==
 +
https://youtu.be/MWNe0qbBwu4
  
 
This video is a great introduction to permutations, combinations, and constructive counting:
 
This video is a great introduction to permutations, combinations, and constructive counting:

Revision as of 09:56, 25 December 2020

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Permutation&oldid=140560"