Difference between revisions of "Permutation"
(→Video) |
|||
(15 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
− | A '''permutation''' of a set of r objects is any rearrangement of the r objects. There are <math> | + | 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. |
− | An important question is how many ways to pick an r-element subset of a set with n | + | 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 | ||
+ | |||
+ | |||
+ | 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 <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 11:01, 25 December 2020
A permutation of a set of objects is any rearrangement (linear ordering) of the
objects. There are
(the factorial of
) permutations of a set with
distinct objects.
One can also consider permutations of infinite sets. In this case, a permutation of a set is simply a bijection between
and itself.
Contents
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 are
and
. We often drop the brackets and commas, so the permutation
would just be represented by
.
Another common notation is cycle notation.
The Symmetric Group
The set of all permutations of an -element set is denoted
. In fact,
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 -element subset of a set with
elements, where order matters. To find how many ways we can do this, note that for the first of the
elements, we have
different objects we can choose from. For the second element, there are
objects we can choose,
for the third, and so on. In general, the number of ways to permute
objects from a set of
is given by
.
Related Videos
- Permutation Videos