2
$\begingroup$

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?

$\endgroup$
10
  • 3
    $\begingroup$ No, that's not correct. You'll have to use inclusion-exclusion. $\endgroup$
    – iamwhoiam
    Nov 11, 2017 at 4:44
  • $\begingroup$ Isn't the answer is $C(n,3)$. $\endgroup$ Nov 11, 2017 at 4:45
  • $\begingroup$ @iamwhoiam how come I can't do it that way? $\endgroup$ Nov 11, 2017 at 4:46
  • $\begingroup$ @DionelJaime no, there may be various elements in $X$ that map to the same element in $Y$. $\endgroup$
    – Bergson
    Nov 11, 2017 at 4:48
  • $\begingroup$ Suppose $n = 4$, and you have the map $\{(1, 2), (2, 2), (3, 3), (4, 1)\}$. This is surjective. You haven't counted this case. $\endgroup$
    – iamwhoiam
    Nov 11, 2017 at 4:49

4 Answers 4

5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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$$

$\endgroup$
2
  • $\begingroup$ Thank you and thanks for everyone else that cleared my misunderstanding as well. To me this seems hard to picture: why we use Inclusion Exclusion principle. As in, I see that we count the total number of unrestricted functions. Then we take away the number of functions where we exclude one element in the range. And then the part with adding back the number of functions where we exclude two of the elements in range confuses me, i can't see where the over lap is $\endgroup$ Nov 11, 2017 at 10:17
  • 1
    $\begingroup$ The three constant functions are each subtracted twice, once for each way of excluding one of the other two elements from the range. Since we only wish to exclude them once, we must add them back. $\endgroup$ Nov 11, 2017 at 10:21
4
$\begingroup$

$\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}$

$\endgroup$
2
$\begingroup$

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:

$\endgroup$
2
  • $\begingroup$ Each partition of $X$ can be obtained from $|Y|!$ different surjections. So the answer is NOT ${n \brace k}$ but $k!{n \brace k}$. $\endgroup$ Nov 12, 2017 at 7:10
  • $\begingroup$ @Stephen, an excellent point. Thank you. $\endgroup$ Nov 12, 2017 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.