1

Let $A$ and $B$ two sets with $|A|=n$ and $|B|=m$. Then

  1. find total number of injective mappings from $A$ to $B$ if $n\leq m$.
  2. find total number of surjective mappings from $A$ to $B$ if $n\geq m$.

In the first case the total number of injective mappings is $^mP_n.$

Because among the $n$ elements of $A$, the first element can goes to any one among the $m$ elements of $B$. The second element can goes to any one among the $m-1$ elements of $B$. Proceeding in this way the $n$th element can goes to any one among the $m-n+1$ elements of $B$. The total number of possible mappings(since $f$ is injective) is $m(m-1)\cdots(m-n+1)= ^mP_n$.
How can I find the total number of surjective mappings. Thank you.

user26857
  • 52,094
user181598
  • 21
  • 2

1 Answers1

1

$\mathbf{Hint:}$

Let $B=\{x_1,\cdots,x_m\}$, and

let $A_i$ be the set of mappings from A to B which do not have $x_i$ in their range, for $1\le i\le m$.

Now use Inclusion-Exclusion to find $\left|A_1^{c}\cap\cdots\cap A_m^{c}\right|$:

$\displaystyle\left|A_1^{c}\cap\cdots\cap A_m^{c}\right|=|S|-\sum_{i}|A_i|+\sum_{i<j}|A_i\cap A_j|-\sum_{i<j<k}|A_i\cap A_j\cap A_k|+\cdots$

where S is the set of all functions from A to B and, for example, $|A_i|=(m-1)^n$ for $1\le i\le m$.

user84413
  • 27,211