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"

m (wikify)
(→‎Video)
 
(14 intermediate revisions by 9 users not shown)
Line 1: Line 1:
−
{{stub}}
+
A '''permutation''' of a [[set]] of <math>r</math> objects is any rearrangement (linear ordering) of the <math>r</math> objects.  There are <math>r!</math> (the [[factorial]] of <math>r</math>) permutations of a set with <math>r</math> distinct objects.
  
 +
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==
 +
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! [https://bit.ly/CombinationsAndPermutations Permutations & Combinations Video]
 +
https://youtu.be/MWNe0qbBwu4
  
−
A '''permutation''' of a [[set]] of <math>r</math> objects is any rearrangement (linear ordering) of the <math>r</math> objects.  There are <math>\displaystyle r!</math> (the [[factorial]] of <math>r</math>) permutations of a set with <math>r</math> objects.
 
  
 +
This video is a great introduction to permutations, combinations, and constructive counting:
 +
https://www.youtube.com/watch?v=t6a4uHEwQnM&
  
−
An important question is how many ways to pick an <math>r</math>-element [[subset]] of a set with <math>n</math> elements, where order matters.  To find how many ways we can do this, note that for the first of the <math>r</math> elements, we have <math>n</math> different objects we can choose from.  For the second element, there are <math>n-1</math> objects we can choose, <math>n-2</math> for the third, and so on.  In general, the number of ways to permute <math>r</math> objects from a set of <math>n</math> is given by
+
==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 <math>\{1, 2, 3\}</math> are <math>\{1,2,3\}, \{1, 3,2\}, \{2,1,3\}, \{2,3,1\},\{3,1,2\}</math> and <math>\{3,2,1\}</math>.  We often drop the brackets and commas, so the permutation <math>\{2,1,3\}</math> would just be represented by <math>213</math>.
 +
 
 +
Another common notation is cycle notation.
 +
 
 +
==The Symmetric Group==
 +
The set of all permutations of an <math>n</math>-element set is denoted <math>S_n</math>.  In fact, <math>S_n</math> 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 <math>r</math>-element [[subset]] of a set with <math>n</math> [[element]]s, where order matters.  To find how many ways we can do this, note that for the first of the <math>r</math> elements, we have <math>n</math> different objects we can choose from.  For the second element, there are <math>n-1</math> objects we can choose, <math>n-2</math> for the third, and so on.  In general, the number of ways to permute <math>r</math> objects from a set of <math>n</math> is given by
 
<math>P(n,r)=n(n-1)(n-2)\cdots(n-r+1)=\frac{n!}{(n-r)!}</math>.
 
<math>P(n,r)=n(n-1)(n-2)\cdots(n-r+1)=\frac{n!}{(n-r)!}</math>.
  
 +
==Related Videos==
 +
*'''Permutation Videos'''
 +
** [http://www.artofproblemsolving.com/Videos/external.php?video_id=183 (Counting Permutations)]
 +
** [http://www.artofproblemsolving.com/Videos/external.php?video_id=184 (Permutations and Factorials)]
 
== See also ==
 
== See also ==
 +
*[[Combinations]]
 
* [[Combinatorics]]
 
* [[Combinatorics]]
 +
* [[Derangement]]
 +
 +
[[Category:Combinatorics]]
 +
[[Category:Definition]]

Latest revision as of 10:01, 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

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

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