Consider $R:A \rightarrow B$ where $|A|=n$ and $|B|=m$. Notation: $|A|$ denotes the cardinality of a finite set $A$. Hence: $n,m\in\mathbb{N}$.
I am asked how many injective relations exist such that $R: A \rightarrow B$. For my purposes, injective is defined as $\leq 1 $ arrow into the codomain $B$, $\forall b\in B$.
In a previous problem, I showed that $\exists (m+1)^n$ partial relations between $A$ and $B$. Therefore, my intuition tells me that this answer will be less than $(m+1)^n$ due to the new restriction of injective. Any help is greatly appreciated!
It should be clear that if $|A|> |B|$, then by the pigeonhole principle there is no injective mapping.
Suppose $n=|A| = |B|$, then we see that the class of injective mapping is the same as the class of bijective mapping which is just the permutation on $n$ element. Hence we have $n!$ injective map.
Lastly, consider the case $n=|A|<|B|=m$. We have $n$ balls and $m$ bins. So we need to first select the $n$ bins from $m$ bins to put our balls in which we have $\binom{m}{n}$ choices. Once we fix our bins, then there are exactly $n!$ ways to put the balls into the bins just like in the case when $|A|=|B|$. Hence we have exactly $\binom{m}{n}n!$ injective mappings.