Let $A$ and $B$ be two sets with $|A|=n$ and $|B|=m,$ where $m>n.$
(a) Determine the number of bijective functions $f : A \to B.$
I believe the answer for the first part is that there are mPn functions
(b) Determine the number of injective functions $f : A \to B.$
For the second part I believe there are $\sum_{i=0}^{m-n} (m-i)Pn$ different injective functions. Could someone guide me if these questions are wrong, I'm more than happy to share my reasoning if required!
Best Answer
A function is bijective if and only if the function is both surjective (i.e. onto) and injective (i.e. 1-to-1). If sets $A$ and $B$ each have a finite number of elements, and there exists some bijection $M$ that maps $A$ to $B$, then you must have that $|A| = |B|$.
Since, by premise, $|A| \neq |B|$, it is impossible for a bijection to exist between sets $A$ and $B$.
Assuming that your notation of $mPn$ is intended to signify
$$\frac{m!}{(m-n)!},$$
then $mPn$ does in fact represent the number of injective functions from $A$ to $B$. This is reasoned as follows:
$A$ has $n$ elements.
Denote them as $a_1, a_2, \cdots, a_n$.
$B$ has $m$ elements.
Denote them as $b_1, b_2, \cdots, b_m.$
You have that $m > n$.
There are $m$ choices for which element in $B$ receives the mapping of the element $a_1$.
Then, since the mapping is injective (i.e. 1-to-1), there are only $(m-1)$ elements remaining that can receive the mapping of $a_2$.
This type of analysis applies to the subsequent mappings of $a_3, a_4, \cdots, a_n$.
Therefore, the computation of the number of distinct injections from $A$ to $B$ is exactly identical to the number of ways of selecting $n$ items, in order, from the set $B$, sampling without replacement (which analogizes to forcing the mapping to be 1-to-1).
This computation is in fact
$$\frac{m!}{(m-n)!}.$$
The above analysis hightlights the difference between a bijection between sets, each with a finite number of elements, and an injection.
The only difference between the bijection and an injection is that with a bijection, at the very moment that you map all of the elements in $A$, you will at that exact instant have run out of elements in $B$. This is what is intended by referring to the mapping as also being surjective (i.e. onto). With a bijection, each element in the set $B$ receives a mapping from some element in the set $A$.
This is clearly impossible when $A$ and $B$ each have a finite number of elements, and $A$ has fewer elements than $B$.