How many relations can you form that are Range = $B$, $A=\{1,2,..,n\}$,$B =\{1,2,..,m\}$

Question

How many relations can you form the are Range = $B$, $A=\{1,2,..,n\}$,$B =\{1,2,..,m\}$, and $m \ge n$

From my understanding, ALL THE elements in $B$ must be in the right spot of the relation. for example (1,1),(1,2),...,(1,m) for element "1" in "A". last one is (n,1),(n,2),..,(n,m).

I think that the answer would be, $n^m$ are number of pairs we can form, and $2^{n^m}$ are number of relations we can form if $ n = m $. otherwise, if $ m > n$ then we have $m - n$ elements left, and we have $2^{m-n} + 2^{n^m}$ relations.

What do you guys think?

Edit: check my solution

Answer 1

You want to count the maps from $B$ to $P(A)\setminus\{\emptyset\}$ which has cardinality $$ \left(2^n-1\right)^m $$ since the cardinality of $P(A)\setminus\{\emptyset\}=2^n-1$.

Note that $P(A)\setminus\{\emptyset\}$ is just the collection of non-empty subsets of $A$ as stated by drhab.

---

The number of functions from $B$ to $A$ is $n^m$, but the question asks for relations whose range is $B$.

Answer 2

If I understand the question correctly then $R\subseteq A\times B$ such that for every $b\in B$ there is some $a\in A$ with $\langle a,b\rangle\in R$.

So for every $b\in B$ the set $\{a\in A\mid \langle a,b\rangle\in R\}$ is allowed to be any non-empty subset of $A$ and is not allowed to be empty.

The number of nonempty subsets of $A$ is $2^n-1$.

That gives: $$(2^n-1)^m$$ possibilities for $R$.

I don't understand the role of condition $m\geq n$, so still have doubts about my understanding.

Answer 3

So here's the solution for my exam, and the answer to that question is as I expected during the exam because it was 14 points. what do you guys think? did you solve it wrong?