Number of onto functions of specific type

Question

Count the number of onto functions from $\{1,2,\ldots,10\}$ to $\{1,2,3,4\}$ such that the preimage of each element of the codomain is at least $2$.

I was choosing 4 out 10 elements and arranging them in $4!$ ways, the rest of $6$ elements can be partitioned into $S(6,4)$ ways. Taking arrangements of the partition in $4!$ ways, I get the final answer to be $C(10,4)\times4!\times S(6,4)\times4!$.

This is resulting into overcounting. I can't figure out why.

Please help me with this problem.

Thanks!

Answer 1

Why are you over counting?

Suppose \begin{align*} f^{-1}(1) & = \{1, 2\}\\ f^{-1}(2) & = \{3, 4\}\\ f^{-1}(3) & = \{5, 6\}\\ f^{-1}(4) & = \{7, 8, 9, 10\} \end{align*}

You count this function once when you choose \begin{align*} f^{-1}(1) & = 1\\ f^{-1}(2) & = 3\\ f^{-1}(3) & = 5\\ f^{-1}(4) & = 7 \end{align*} then select \begin{align*} f^{-1}(1) & = 2\\ f^{-1}(2) & = 4\\ f^{-1}(3) & = 6\\ f^{-1}(5) & = 8 \end{align*} but you also count it once when you choose \begin{align*} f^{-1}(1) & = 1\\ f^{-1}(2) & = 4\\ f^{-1}(3) & = 5\\ f^{-1}(5) & = 8 \end{align*} and then select \begin{align*} f^{-1}(1) & = 2\\ f^{-1}(2) & = 3\\ f^{-1}(3) & = 6\\ f^{-1}(5) & = 7 \end{align*} However, the order of selection does not matter.

That was not your only error: You have not accounted for the images of all ten elements in the domain.

Strategy

Since each of the four elements in the codomain must be the images of at least two elements in the domain, there are two possibilities:

• One element in the codomain is the image of four elements in the domain and each of the other elements in the codomain is the image of two elements in the domain.

• Two elements in the codomain are each the image of three elements in the domain and the remaining two elements in the codomain are each the image of two elements in the domain.

One element in the codomain is the image of four elements in the domain and each of the other elements in the codomain is the image of two elements in the domain:

• Choose which element in the codomain is the image of four elements in the domain.

• Choose which four elements in the domain map to that element of the codomain.

• Choose which two of the remaining six elements in the domain map to the smallest remaining element in the codomain.

• Choose which two of the four remaining elements in the domain map to the smaller of the two remaining elements in the codomain.

• The remaining two elements in the domain must map to the remaining element in the codomain.

Two elements in the codomain are each the image of three elements in the domain and the remaining two elements in the codomain are each the image of two elements in the domain:

• Choose which two of the four elements in the codomain are each the image of three elements in the domain.

• Choose which three elements in the domain map to the smaller of the selected elements.

• Choose which three of the remaining seven elements in the domain map to the larger of the selected elements.

• Choose which two of the remaining four elements in the domain map to the smaller of the remaining two elements in the codomain.

• The remaining two elements in the domain must map to the remaining two elements in the codomain.

Since the two cases are mutually exclusive and exhaustive, the number of surjective (onto) functions $f: \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} \to \{1, 2, 3, 4\}$ can be found by adding the results for the two cases.