Find number of relations $R$ that are onto

Question

$A= \{1,2,3,...m\}$ $B= \{1,2,3,...n\}$

The relation from $A$ to $B$ is onto such that Range($R$) $= B$

Find Find number of relations $R$ from $A$ to $B$ that are onto

since for every $b$ in $B$ must be in relation with every $a$ in $A$ then I figured there must be $m^{n}$ $R$ relations that are onto but I can be completely wrong

How can I approach this question?

Answer 1

For each element in the range, pick which element or elements from the domain there are who are related to that element in the range. The only requirement is that there be at least one element from the domain who is related to it.

Apply rule of product and conclude.

There are $2^m-1$ non-empty subsets of the domain

$~$

For each element in the range there are $2^m-1$ choices for which set of elements in the domain are related to it

$~$

There are then $(2^m-1)^n$ total such onto relations