If $S$ is a nonempty set then $A(S)$ is the set of all one-to-one mappings of $S$ onto itself.

If the set $S$ has $n$ elements, prove that $A(S)$ has $n!$ elements.

Proof: First of all we'll prove the following useful lemma.

Lemma: Let $\sigma: S\to S$, $|S|=n$ and $\sigma$ is one-to-one mapping then $\sigma$ is onto.

Proof of lemma: Suppose $\sigma$ is not onto then $\exists y\in S$ such that for any $x\in S$ we have $\sigma (x)\neq y$. Hence $|\sigma(S)|\leqslant n-1$ but $|S|=n$. Thus some two elements from $S$ have the identical images so $\sigma$ is not one-to-one. Contradiction.

Let's find the number of injective mappings from $S$ to $S$, since $|A(S)|=$ the number of injective functions. Let $S=\{x_1, x_2, \dots, x_n\}$ and $\sigma: S\to S$. In order $\sigma$ to be injective it should correspond $\{x_1, x_2, \dots, x_n\}$ to some of its permutations. There $n!$ permutations. So, we have proven that $|A(S)|=n!$

Is it correct?


Yes, it is the case. To be more precise, we can say: there is $n$ possibility to $\sigma(x_1)$, and $n-1$ for $\sigma(x_2)$ and so on.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.