- #1

geoffrey159

- 535

- 72

## 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)

Last edited: