Number of surjective functions $f:X\rightarrow Y$ where $|X| = n,|Y| = 3$.

Question

Let $f:X\rightarrow Y$ be a function where $|X| = n$ and $|Y| = 3$.

I think it is $n(n-1)(n-2)$ since for the first element in $Y$, I pick out of $n$ possible elements that map to this first element and so on.

Is this the correct line of thinking?

Answer 1

Okay, so you write down $Y = \{y_1, y_2, y_3\}$ and you pick out an element $x_1$ of $X$ and you say that $f(x_1) = y_1$ and you pick out a second element, $x_2$ and you say that $f(x_2) = y_2$, and you pick a third and say $f(x_3) = y_3$. That's fine, you've defined $f$ on three values but what about the rest of $X$? How do you define $f$ on $X - \{x_1,x_2,x_3\}$? What if you have two elements of $X$, say $x_1$ and $x_1'$ such that $f(x_1) = y_1$ and $f(x_1') = y_1$, which one are you picking? How do you distinguish between them?

Answer 2

$\sum _{i=1}^{n-2}\sum_{j=1}^{n-i-1} \binom{n}{i}\binom{n-i}{j}$ where $i$ of the $n$ elements of $X$ are mapped to $1$, $j$ of the remaining $n-i$ elements are mapped to $2$ and the remaining $n-i-j$ elements are mapped to $3$ and where $ Y= \{1, 2, 3\}$

---

Observe that this answer is equivalent to the answer by @N. F. Taussig as follows. $\begin {align} \sum _{i=1}^{n-2}\sum_{j=1}^{n-i-1} \binom{n}{i}\binom{n-i}{j} &= \sum _{i=1}^{n-2}\binom{n}{i}\sum_{j=1}^{n-i-1} \binom{n-i}{j}\\ &= \sum _{i=1}^{n-2}\binom{n}{i}(2^{n-i}-2)\\ &= \sum _{i=1}^{n-2}\binom{n}{i}2^{n-i}-2\sum _{i=1}^{n-2}\binom{n}{i}\\ &= \sum _{i=0}^{n}\binom{n}{i}2^{n-i}-(1+2n+2^n)-2[\sum _{i=0}^{n}\binom{n}{i}-(1+n+1)]\\ &= 3^n - 3\times2^n +3 \end{align}$

Answer 3

Trevor Gunn has explained why your approach leads to an incorrect answer.

Observe that if we did not have the restriction that $f: X \to Y$ is surjective, we would have three choices for the image of each of the $n$ elements of $X$, so there are $3^n$ functions $f: X \to Y$. From these, we must exclude those in which there are fewer than three elements in the range.

There are $\binom{3}{k}$ ways to exclude $k$ of the $3$ elements in the codomain from the range and $(3 - k)^n$ ways to map the $n$ elements of $X$ to the remaining $3 - k$ elements in the codomain. Hence, by the Inclusion-Exclusion Principle, the number of surjective functions $f:X \to Y$ is $$\sum_{k = 0}^{3} (-1)^k\binom{3}{k}(3 - k)^n = \binom{3}{0}3^n - \binom{3}{1}2^n + \binom{3}{2}1^n - \binom{3}{3}0^n = 3^n - 3 \cdot 2^n + 3$$

Answer 4

One way of thinking about it, which ties into other areas which you may have studied or may study in the future, is that if $f:X\to Y$ is surjective then the inverse $f^{-1}$ creates a set partition of $X$ into $|Y|$ non-empty subsets, or an equivalence relation on $X$ with $|Y|$ equivalence classes.

In particular, the number of partitions of a set of $n$ into $k$ non-empty subsets is important enough to be named: a Stirling number of the second kind, commonly denoted ${n \brace k}$.

As Stephen Meskin pointed out in a comment, this isn't quite the full story: the correspondence between the parts of each partition and the elements of $|Y|$ allows for an arbitrary permutation, so the final answer is $|Y|! {|X| \brace |Y|}$

Further reading:

• OEIS A008277
• Wikipedia:Stirling number of the second kind
• MathWorld:Stirling number of the second kind