next up previous contents
Next: Stirling numbers of the Up: Mappings Previous: The characteristic function of   Contents

Permutations

Definition 5.6.1   A permutation of a set $ E$ is a bijection $ f: \; E \rightarrow E$.

For the set $ E=\{ 1,2,3,4,5,6,7,8 \}$, the notation

$\displaystyle f = \begin{pmatrix}
 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\  
 1 & 3 & 4 & 2 & 8 & 7 & 6 & 5
 \end{pmatrix}$    

denotes the permutation $ \sigma$ of $ E$ such that $ \sigma(1)=1$, $ \sigma(2)=3$, etc.

Definition 5.6.2   Let $ E$ be a set and $ A = \{ a_1, a_2, ... , a_r \}$ be a subset of $ E$. Let $ \sigma$ be a permutation of $ E$ verifying the following properties:
(i)
$ \sigma (a_1) = a_2$, $ \sigma (a_2)=a_3$, ..., $ \sigma(a_n)=a_1$ (renumbering the elements of $ A$ if necessary;
(ii)
for any $ x \not\in A$, $ \sigma (x)=x$.
Then $ \sigma$ is called a cycle.

For example, in $ \sigma = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
2 & 7 & 3 & 1 & 5 & 6 & 4 & 8 & 9
\end{pmatrix}$ is a cycle, whose notation can be shortened to $ (1 2 7 4)$.

Proposition 5.6.3   Any permutation is the product of disjoint cycles.



Subsections

root 2002-06-10