next up previous contents
Next: Arrangements Up: Elementary combinatorics Previous: Elementary combinatorics   Contents

Mappings from a finite set to a finite set

Proposition 7.2.1   Let $ A$ and $ B$ be two finite and non empty sets; we denote $ \vert A\vert=n$ and $ \vert B\vert=q$.The number of mappings from $ A$ to $ B$ is equal to $ q^n$.

Proof. Denote the elements of $ A$ by $ a_1, a_2, \dots, a_n$ and let $ f: \; A \rightarrow B$ be a mapping. For any index $ i$ such that $ 0 \leq i \leq n$, we have $ p$ possible choices for $ f(a_i)$. As every choice is independent from the other ones, the total number of possibilities is $ p \cdot p \dots p \cdot p=p^n$. $ \qedsymbol$

The following tree represents the choices for a mapping from $ A$ to $ B$ whenh $ \vert A\vert=\vert B\vert=3$::

Figure 1: Mappings from a finite set to a finite set
\mbox{\epsfig{file=tree-1.eps, height=5cm}}

For example, at a tea-room, they offer 9 different kinds of tea. Five people order a cup of tea; there are $ 9^5=59,049$ different possibilities of service.

root 2002-06-10