next up previous contents
Next: Permutations Up: Elementary combinatorics Previous: Mappings from a finite   Contents

Arrangements

Definition 7.2.2   Let $ p$ and $ n$ are two integers verifiying the inequalities: $ 0 \leq p \leq n$.The number $ A_n^p$ is defined by:

$\displaystyle A_n^p= n (n-1)(n-2) \dots (n-p+1)=\frac {n!}{(n-p)!}.$    

For example,

$\displaystyle A_6^3$ $\displaystyle =6 \cdot 5 \cdot 4 = 120.$    
$\displaystyle A_7^4$ $\displaystyle = 7 \cdot 6 \cdot 5 \cdot 4 = 840.$    

Proposition 7.2.3   Let $ A$ and $ B$ be two finite sets such that $ \vert A\vert=p$ and $ \vert B\vert=n$, where $ p$ and $ n$ are two integers verifiying the inequalities: $ 0 \leq p \leq n$. The set of all the injections $ A \longrightarrow B$ is finite and its cardinality is equal to $ A_n^p$.

Proof. Denote the elements of $ A$ by $ a_1, a_2, \cdots, a_p$ and let $ f$ be an injection from $ A$ to $ B$. For $ f(a_1)$ we have $ n$ possible choices; for $ f(a_2)$, we have $ n-1$ 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 $ B$ as an image, the total number of choices is the product $ n(n-1)\cdots (n-(p-1))= n(n-1)\cdots (n-p+1)=A_n^p$. $ \qedsymbol$

The following tree represents injections form $ A$ to $ B$ when $ \vert A\vert=3$ and $ \vert B\vert=5$:

Figure 2: Injection from a finite set to a finite set
\begin{figure}
\centering
\mbox{\epsfig{file=tree-inj.eps, height=5cm}}
\end{figure}

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 $ A_{20}^3=6840$ possibilities for such a triple. The following results are quite obvious:

Proposition 7.2.4   Let $ n$ and $ p$ be two natural numbers such that $ 0 \leq p \leq n$. Then we have:
  1. $ A_n^1=n$;
  2. $ A_n^p=n \; A_{n-1}^{p-1}$.

We need only to replace into the definition.
next up previous contents
Next: Permutations Up: Elementary combinatorics Previous: Mappings from a finite   Contents
root 2002-06-10