Number of injections, of functions

[geoffrey159]

Homework Statement

Show that the number of injections from $E \rightarrow F$, $E,F$ finite sets, $p = \#E ,\ n = \#F,\ p\le n$, is $\frac{n!}{(n-p)!}$
Then, find the number of functions from $E \rightarrow F$.

Homework Equations

$A = \{ \text{injections from }E \rightarrow F \}$
$B = \{ \text{arrangements of } p \text{ elements among } n \}$
$C = \{ \text{functions from }E \rightarrow F \}$
$D = (F \cup \{a\}) \times ...\times (F \cup \{a\})$, $p$ times , $a \notin F$

The Attempt at a Solution

Hello, I have to solve this problem for my homework. It took me a while but I think I have found it. Is it correct ?

a) I want to prove that there is a bijection from $A$ to $B$ so that $\# A = \#B = \frac{n!}{(n-p)!}$.
I define the mapping $h: A \rightarrow B$ by $h(f) = (f(x_1),...,f(x_p))$.

We have $h(f)\in B$ because $f$ is injective.

$h$ is injective because for all $f,g\in A$, $h(f) = h(g) \Rightarrow \forall i=1...p,\ f(x_i) = g(x_i) \iff f = g$.

For any arrangement $(y_1,...,y_p)\in B$, I define $f$ such that for all $i = 1...p$, $f(x_i) = y_i$. Then $f$ is necessarily injective because if we had $f(x_i) = f(x_j)$ and $x_i \neq x_j$, then we would have $y_i = y_j$, which contradicts the definition of an arrangement. So $f\in A$ and $h$ is a surjection.

So $h$ is a bijection

b) Same kind of problem.
I define the mapping $h: C \rightarrow D$ by $h(f) = (y_1, ..., y_p)$ where
\begin{equation}
y_i =
\left\lbrace
\begin{array}{ccc}
f(x_i) & \mbox{if} & x_i\in \cal D(f)\\
a & & \mbox{otherwise} \\
\end{array}\right.
\end{equation}

Injectivity is shown the same way as above.

For any tuple $(y_1,...,y_p)\in D$, I define $f$ by $f(x_i) = y_i \iff y_i \neq a$. Clearly $f$ belongs to $C$ and h is surjective .

Then h is bijective and $\# C = \#D = (\#(F \cup \{a\}))^p = (n+1)^p$ (because $\{a\}$ and $F$ disjoint)

 

[Delta2]

a) seems correct to me

b) You seem to also count the functions that have as domain any subset of E. Why you doing that? Otherwise the answer should be $n^p$.

 

[geoffrey159]

Hello, thank you for proofreading.
Concerning your question, the difference between a function $f$ and a mapping $g$ both from $E \rightarrow F$, is that ${\cal D}(f)\subset E$ while ${ \cal D}(g) = E$. There are functions that are not defined on $E$ entirely (ex: $E = \mathbb{R},\ f(x) = \frac{1}{x},\ {\cal D}(f) = E - \{0\}$ )