Permutation

Countable sequences!

Broadly speaking, a permutation of a set is a sequence made from its elements. The generalized rule of product can be applied to count the number of permutations, or in other words, different arrangements, that can be made from a set.

Since permutations are sequences, the order of their elements matters, unlike combinations.

Contents

$r$-permutation

An $r$-permutation of a set is a sequence of $r$ of its elements, with no repetitions. For example, $(9, 5, 6)$ and $(6, 1, 7)$ are both $3$-permutations of the set $\set{9, 1, 6, 5, 7, 8}.$ However, $(7, 7, 9)$ would not be a $3$-permutation of that set, because it repeats $7.$ By the generalized rule of product, the total number of $3$-permutations that can be made from that set is $6 * 5 * 4 = 120.$ This is because, when an element is selected, there is $1$ fewer choice for the next element, as repetitions are not allowed in $r$-permutations. This line of thinking leads to the following formula:

The number of $r$-permutations that can be made from a set of $n$ elements, denoted $P(n, r)$, is: $$P(n, r) = \frac{n!}{(n-r)!}$$

⚠ This formula originates from a pattern that arises in the generalized rule of product when counting $r$-permutations of a set with $n$ elements. It seems that you always have to multiply $n$ by progressively smaller integers, with the last integer being $n - r + 1.$ Written out, it's $n * (n - 1) * ... * (n - r + 1)$, which is formalized above.

⚠ $nPr$ is another way of writing $P(n, r).$ Both are read "$n$ permute $r.$"

⚠ It is assumed that $n$ and $r$ are always non-negative in these equations, and satisfy $n \geq r.$ You probably wouldn't want to count the number of $-2$-permutations of a set with $-5$ elements... that would just be weird and make no sense.

Plenty of problems can be solved by counting $r$-permutations. Here's some quick examples. How many ways are there to elect a president, vice president, and treasurer from $6$ people? How many ways can $3$ people be seated at $6$ desks? How many ways can $3$ dice all show different numbers? Though the wording may vary, these questions are all asking for the number of $3$-permutations that can be made from a set of $6$ elements. The answer, as you know by now, is $P(6, 3) = \frac{6!}{(6 - 3)!} = 6 * 5 * 4 = 120.$

$r$-permutations happen between two sets. Previously, it was asked how many ways $3$ dice could all roll different numbers. Let's arrange the dice in an arbitrary order, $(\text{dice}_1, \text{dice}_2, \text{dice}_3)$, and consider the set of numbers that could be rolled $\set{1, 2, 3, 4, 5, 6}.$ If we make the decisions in order, $\text{dice}_1$ has $6$ choices of numbers, then $\text{dice}_2$ has $5$ choices, and finally $\text{dice}_3$ has $4$ choices, with the result being $6 * 5 * 4 = 120.$ This may be a more intuitive way of thinking about counting $r$-permutations.

In the event that $n = r$, $r$-permutations are called "permutations" and the formula from above simplifies greatly:

The number of permutations that can be made from a set of $n$ elements, denoted $P(n, n)$, is: $$P(n, n) = n!$$

Here, what is being counted is the number of different sequences which use each element of a set exactly once, which is essentially just how many ways the elements of that set can be ordered. Consider the set $\set{a, b, c}.$ It has $6$ permutations in total: $(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a).$

A bride, a groom, $3$ bridesmaids, and $3$ groomsmen line up for a photo at a wedding. How many ways can the party line up with the bride next to the groom? Well, the bride could be either left or right of the groom, meaning there are $2$ ways for them to be next to each other. Treat the bride+groom pair as if it represented $1$ person. Now, we only need to figure out how many ways a bride+groom pair, $3$ bridesmaids, and $3$ groomsmen can be arranged. This is a permutation of $7$ things. There are $7!$ ways to arrange $7$ things. Therefore, taking into account the $2$ ways the bride and groom can be next to each other, there are, in total, $2 * 7! = 10,080$ ways the party could be lined up with the bride and groom next to each other.

If a password must be $10$ characters long, consist of only lowercase alphabetical characters, and characters cannot be repeated, then there are $P(26, 10)$ different passwords that can be made.

Permutation with repetition

A permutation with repetition of a sequence (in which some elements appear more than once) is a sequence that uses all of its elements the same number of times they appeared in the original sequence. For instance, $P(3,3) = 3! = 6$ permutations of $ANT$ ($ANT$, $ATN$, $NAT$, $NTA$, $TAN$, $TNA$) exist, but just $3$ non-identical permutations of $BEE$ ($BEE$, $EBE$, $EEB$) exist, because swapping the identical $E$'s will have no effect. Since these sequences have repetitions, the previous formula for counting permutations will need a correction to avoid overcounting:

The number of permutations with repetition that can be made from a sequence that consists of $n$ distinct elements $\set{x_1, x_2, ... x_n}$ such that $x_1$ is used $k_1$ times, $x_2$ is used $k_2$ times, ... and $x_n$ is used $k_n$ times, is: $$\frac{n!}{k_1! \times k_2! \times ... \times k_n!} = \frac{P(n, n)}{k_1! \times k_2! \times ... \times k_n!} = \frac{P(n, n)}{P(k_1, k_1) \times P(k_2, k_2) \times ... \times P(k_n, k_n)}$$ It should always be the case that $n = k_1 + k_2 + ... + k_n.$

Dividing by the factorials of the frequencies of each element has the effect of ensuring identical rearrangements are never counted more than once. Each factorial represents the number of ways rearranging that element will result in an identical sequence.

⚠ The above formula is an application of the rule of product. Wanna see why? There are $\binom{n}{k_1}$ ways to pick where the $k_1$ identical versions of $x_1$ are placed among $n$ slots. For every way of picking where the $x_1$'s are placed, there are $\binom{n - k_1}{k_2}$ ways to pick where the $k_2$ identical versions of $x_2$ are placed among $n - k_1$ slots (as $k_1$ are already taken). Further down the line, there are $\binom{n - k_1 - k_2 - ... - k_{n-1}}{k_n}$ ways to pick where the $k_n$ identical versions of $x_n$ are placed among the final remaining slots. By the rule of product, there are, in total, $\binom{n}{k_1} \times \binom{n - k_1}{k_2} \times ... \times \binom{n - k_1 - k_2 - ... - k_{n-1}}{k_n} = \frac{n!}{k_1! \times k_2! \times ... \times k_n!}$ ways to scramble the original sequence.

Let's try this out. How many ways can you uniquely scramble $TENNESSEE$? There are $9$ letters. Since $T$ is used $1$ time, $E$ is used $4$ times, $N$ is used $2$ times, and $S$ is used $2$ times, the answer is simply $\frac{9!}{1! \times 4! \times 2! \times 2!} = 3,780.$

Imagine you have $4$ slices of pepperoni pizza, $3$ slices of cheese pizza, and $1$ slice of Hawaiian pizza to share with $8$ friends. How many different ways can you give $1$ slice of pizza to each friend? Let's make use of the bijection rule here. Assign each of your $8$ friends to a slot in a sequence. Assign each of the $3$ types of pizza to a letter $\set{P, C, H}.$ Then, a bijection exists between the number of ways of scrambling $PPPPCCCH$ and the number of ways of giving slices of pizza to your friends. Counting permutations with repetition, the answer is $\frac{8!}{4!3!1!} = 280.$

⚠ You could also just use the rule of product to answer this question. Although, it is important to be able to recognize that this is a situation where the same role (pizza type) is being assigned multiple times to different people. That thought process should guide you to the formula best suited for this situation.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort