Next: Permutations Up: Elementary combinatorics Previous: Mappings from a finite   Contents

Arrangements

Definition 7.2.2   Let and are two integers verifiying the inequalities: .The number is defined by:

For example,

Proposition 7.2.3   Let and be two finite sets such that and , where and are two integers verifiying the inequalities: . The set of all the injections is finite and its cardinality is equal to .

Proof. Denote the elements of by and let be an injection from to . For we have possible choices; for , we have choices, and so on. As the choices alreday made have no other influence on the further ones than the impossibility of chosing once again the same element in as an image, the total number of choices is the product .

The following tree represents injections form to when and :

For example, 20 horses have a race. Gamblers try to guess the results; a winner gamble consists of the ordered triple of horses arriving first. There are possibilities for such a triple. The following results are quite obvious:

Proposition 7.2.4   Let and be two natural numbers such that . Then we have:
1. ;
2. .

We need only to replace into the definition.

Next: Permutations Up: Elementary combinatorics Previous: Mappings from a finite   Contents
root 2002-06-10