A simple question.
They give the definition of permutation as
"a one to one mapping of the set onto the set of positive integers $\{1, 2,3,4, \ldots n\}$."
What does this definition exactly mean??
Thank you...
$\endgroup$ 12 Answers
$\begingroup$You can think of this as mapping a set of "things" to their respective positions.
For example, I will consider the set to be $$S = \{A, B, C\}$$
However, the idea of a set has no notion of order. Hence, I can write statements like
$$ S = \{ A, B, C \} = \{B, C, A\} = \ldots $$
So, we need to be able to formalise an idea of "order". One way to do this is to map every element of the set $S$ to some unique number $i \in [1, |S|] \in \mathbb{Z}$ (where $|S|$ is the size of the set).
So, in this case, if we wish to represent the permutation $(A, C, B)$ (notice the rounded brackets and not the curly brackets), we can use a function
$$P : S \to {1, 2, 3} \\ P (A) = 1\\ P(B) = 3 \\ P(C) = 2 $$
This tells us that $A$ is at position $1$, $C$ is at position $2$ and $B$ is at position $3$.
We need to lay down some restrictions on this function, to eliminate weird things like this:
$$ Q : S \to {1, 2, 3} \\ Q(A) = 1 \\ Q(B) = 1 \\ Q(C) = 1 $$
This is nonsense since we can't have all three of them occupy the same position! Hence, for every number $i \in [1, n]$, we need a unique $s \in S$. This tells us that the function must be one-one.
Since both $S$ and the set $[1, |S|]$ have the same cardinality, any one-one function between them is guaranteed to be onto. Hence, any mapping $$F: S \to [1, |S|]$$
is guaranteed to be invertible.
That's why we say that any permutation is the same as an invertible / "bijective" mapping from the set to the set of positive integers $[1, 2, \ldots n]$
$\endgroup$ 2 $\begingroup$It means a permutation can be considered as a function that maps the elements of the set $\left\{ 1,2,3,4,\ldots,n \right\}$ to itself in such a way that every number appears exactly once as an image.
This means you can think of a permutation as a reordering; for example, in the case of $\left\{ 1,2,3,4,5 \right\}$, one possible permutation is: $$\begin{array}{c} 1 \mapsto 4 \\ 2 \mapsto 5 \\ 3 \mapsto 1 \\ 4 \mapsto 3 \\ 5 \mapsto 2 \\ \end{array}$$ In total there are $5! = 120$ of these possible permutations. You can easily see this as there are 5 possible choices for the image of 1, then there are 4 possible numbers left as the image of 2, etc. In general there are $n!$ permutations of $\left\{ 1,2,3,4,\ldots,n \right\}$.
$\endgroup$
