Permutations without Repetition#

Definition: Permutation

A permutation of a set \(S\) is a bijection \(f: S \to S\) between \(S\) and itself.

Intuition

A permutation of \(S\) is just a way to arrange all its elements.

Notation

Permutations are usually denoted by \(\sigma\).

Finite Permutations#

When \(S\) is finite, a permutation of \(S\) is an \(n\)-tuple which contains every element of \(S\) exactly once.

Example: Permutations of Finite Sets

Suppose \(S = \{A, B, C, D\}\). The following are permutations of \(S\):

\[ (A, B, C, D) \qquad (D, A, C, B) \qquad (B, D, A, C) \qquad (C, B, D, A) \]

The following are not permutations of \(S\):

\[ (A, B, D) \qquad (B, C) \qquad (A, B, B, D, C) \]

Theorem: Number of Permutations

If \(S\) is a finite set, then the total number of permutations \(S\) is the following:

\[ \prod_{k = 1}^n k = 1 \times 2 \times \cdots \times (n-1) \times n = n! \]

Notation

\[ P_n \]

Proof

TODO

Theorem: The Symmetric Group

If \(X\) is a finite set, then the set \(\mathcal{S}\) of all permutations of \(X\) forms a group \((\mathcal{S}, \circ)\) under composition.

Definition: The Symmetric Group

We call \((\mathcal{S}, \circ)\) the symmetric group on \(X\).

Notation

\[ \operatorname{Sym}(X) \qquad S_X \]

Proof

TODO

Parity#

Definition: Sign

TODO

Definition: Parity

A permutation \(\sigma\) of a finite set is:

odd if its sign is \(-1\): \(\operatorname{sgn}(\sigma) = -1\);
even if its sign is \(+1\): \(\operatorname{sgn}(\sigma) = +1\).

Theorem: Sign via Inversions

Let \(X\) be a totally ordered finite set and let \(\sigma\) be a permutation of \(X\).

Definition: Inversion

An inversion of \(\sigma\) are any \(i, j \in X\) such that \(i \lt j\) and \(\sigma(i) \gt \sigma(j)\).

If \(N(\sigma)\) is the total number of inversions of \(\sigma\), then the sign of \(\sigma\) is given by

\[ \operatorname{sgn}(\sigma) = (-1)^{N(\sigma)}. \]

Proof

TODO

Permutations with Repetition#

Definition: Permutation with Repetition

Let \(S\) be a multiset with cardinality \(k\).

A permutation with repetition of \(S\) is a \(k\)-tuple of elements from \(S\) in which each element \(s_i\) is present as many times as its multiplicity \(k_i\).

Example

Let \(S = \{3, 3, 4, 5, 5, 5\}\).

Some permutations with repetition of \(S\) are

\[ (4, 3, 5, 5, 3, 5) \qquad (5, 3, 4, 5, 5, 3) \qquad (5, 3, 5, 4, 3, 5). \]

Theorem: Total Number of Permutations with Repetition

If \(S = \{s_1, \dotsc, s_n\}\) is a multiset with cardinality \(k\), then the total number of permutations with repetition \(S\) can be calculated via \(k\) and the multiplicity \(k_i\) of each element as follows:

\[ \frac{k!}{k_1! \cdots k_n!} \]

Notation

Since this number depends only on the cardinality \(k\) and multiplicities \(k_i\) but does not depend on the elements themselves, we call the above number the total number of permutations with repetition of class \(k\) and denote it by

\[ \tilde{P}(k_1, \dotsc, k_n) \]

Proof

TODO