next up previous
Next: Cycles and Cycle Structure Up: Random Permutation Matrices An Previous: Introduction

Background About Permutations and Probability

For our purposes, a permutation can be thought of as a one-to-one mapping of the set of integers $\{1, 2, \ldots, n\}$ onto itself. The group of all permutations of n numbers is known as the symmetric group, Sn, and it is a simple matter to verify that there are n!permutations in Sn. In standard notation, a permutation $\sigma \in S_n$ is written as

\begin{displaymath}\sigma = \pmatrix{1 & 2 & \cdots & n\cr
\sigma(1) & \sigma(2) & \cdots & \sigma(n)\cr},

where $\sigma(1)$ is the image of 1 under $\sigma$, $\sigma(2)$ is the image of 2, and so on.