Finding the range of a function given the cardinality of two sets

Question

If I am given that a set $A$ has size $5$ and another set $B$ has size $4$, how many functions of range with cardinality $3$ can there from $A$ to $B$? I am unsure as to how to go about solving this problem. Please offer assistance.

Answer 1

I suppose that with "of range 3" you mean "where the cardinality of the range is exactly 3".

First of all, two functions $f$ and $g$ with different ranges are obviously different, as there is at least one element $a\in A$ where $f(a)\notin f(B)$ (or the opposite).

So for each subset $S$ of three elements of $B$ (there are exactly $4$ of them) you need to find all functions that have exactly range $S$. This number can be calculated by the inclusion/exclusion principle, so

$$ |\{f:A\twoheadrightarrow S\}| = |\{f:A\to \mathbb 3\}| - 3 |\{f:A\to \mathbb 2\}| + 3|\{f:A\to \mathbb 1\}| $$

that is, count all the functions with range included in S, subtract the number of functions with range included in a subset of size 2 (there are 3 of them), and add again the number of constant functions (again there are 3 of them).

So this gives $$ |\{f:A\twoheadrightarrow S\}| = 3^5-3·2^5+3 = 243 - 96 + 3 = 150 $$ for each subset of cardinality 3.

The total number of functions is then $150·4=600$.

---

If on the other side you looked for the number of function with range "up to three" (that is non-surjective), you can apply the same reasoning to find the number of surjective functions and subtract it from the number of all functions:

$$ |\{f:A\twoheadrightarrow \mathbb 4\}| = |\{f:A\to \mathbb 4\}| - 4 |\{f:A\to \mathbb 3\}| + 6|\{f:A\to \mathbb 2\}| - 4|\{f:A\to \mathbb 1\}| $$

so the number of non-surjective is $$ |\{f:A\to \mathbb 4\}| - |\{f:A\twoheadrightarrow \mathbb 4\}| = 4 |\{f:A\to \mathbb 3\}| - 6|\{f:A\to \mathbb 2\}| + 4|\{f:A\to \mathbb 1\}| $$

that is $$ 4·3^5-6·2^5+4 = 4*243 - 128 + 4 = 848 $$