Next: Surjections Up: Elementary combinatorics Previous: Arrangements   Contents

## Permutations

Proposition 7.2.5   Let and be two finite sets such that and let be a mapping from to . Then the following properties are equivalent:
(i)
is an injection;
(ii)
is a surjection;
(iii)
is a bijection.

Proof. It suffices to prove that in this case injection and surjection are equivalent.
1. Suppose that is an injection. Then the set is finite and . It follows that is a subset of such that , hence , i.e. is a surjection.
2. Suppose that is a surjection, i.e. . Thus and must be an injection.

Corollary 7.2.6   The set of natural numbers is not finite.

Proof. The mapping from to is an injection (prove it!), but not a surjection. The result is a consequence of Proposition 2.5.

Non finite sets are called infinite. We will see later that there is still a need for further classification among infinite sets, namely into countable (v.i. section ) and non countables sets. If and are infinite then there exist injections which are not bijections and vice versa. For instance if , define

 and

Then is surjective but not injective and is injective but not surjective.

Corollary 7.2.7   If is a non empty finite set such that , then the number of permutations of is equal to .

Proof. As is finite, the permutations are exactly the injections from to itself. Thus, the number of permutations of is equal to .

Example 7.2.8
1. If we wish to place 8 books on a shelf, there are possible orderings. .
2. We wish to place 5 chemistry books and 8 physics books on the same shelf, letting together books of the same discipline. Among the chemistry books, there are orderings and among the physics books, there are orderings. Axs there are two choices for the respective places of the discipline (physics on the left and chemistry on the right, or physics on the right and chemistry on the left), the number of different orderings is here .

Next: Surjections Up: Elementary combinatorics Previous: Arrangements   Contents
root 2002-06-10