Intuitive method of finding probability of getting an onto function from all possible functions from a set to another.

Question

The question I was dealing with is as follows:

Let sets $A$ and $B$ have $7$ and $5$ elements, respectively. If one function is selected from all possible defined functions from $A$ to $B$, what is the probability that it is onto?

Now, this is how my thought process was:

For a relation to classify as a function only an element of $A$ should possess only one image in the co-domain $B$. Thus, each element of $A$ has $5$ elements to choose as its image. Since it is a function from $A$ to $B$, two elements from $A$ mapping to the same image is allowed.

And so the total number of possible functions would be $= 5^7$

Next, to choose the number of onto functions, what I thought was: each element of $B$ must be mapped, but not to the same element. Therefore, the first element of $B$ would have $7$ options to choose from, the next one would have $6$ and so on... After every element of $B$ is mapped, there would be $2$ remaining elements in $A$ and they have to be mapped to any element of $B$ so as to become a function. Therefore, those two elements would have to choose any $2$ out of $5$ elements of $B$.

Thus the total number of possible onto functions would be =

$$(7 \cdot 6 \cdot 5 \cdot 4 \cdot 3) \cdot (5 \cdot 5) = \frac{7! \cdot 5^2}{ 2!}$$

Thus the probability required = $$\frac{\frac{7! \cdot 5^2}{2!}}{5^7}$$

But, the answer was $$\frac{7! \cdot 2}{3 \cdot 5^6}$$

Where did I go wrong?

Answer 1

Both your answer and the stated answer of $$\frac{7 \cdot 2!}{3 \cdot 5^6}$$ are incorrect.

Let sets $A$ and $B$ have $7$ and $5$ elements, respectively. If one function is selected from all possible defined functions from $A$ to $B$, what is the probability that it is onto?

You counted the number of functions correctly.

Here are two approaches to counting the number of surjective (onto) functions from a set of seven elements to a set of five elements.

Method 1: We use the Inclusion-Exclusion Principle.

There are $5^7$ functions from a set of seven elements to a set of five elements since there are $7$ elements in the codomain to which each of the $5$ elements in the domain could be mapped.

From these, we must subtract those in which fewer than five elements in the codomain are in the range. There are $\binom{5}{k}$ ways to exclude $k$ of the five elements in the codomain from the range and $(5 - k)^7$ ways to map the seven elements in the domain to the remaining $5 - k$ elements in the codomain. Thus, by the Inclusion-Exclusion Principle, the number of surjective functions from a set with seven elements to a set with five elements is \begin{align*} \sum_{k = 0}^{7} (-1)^k\binom{5}{k}(5 - k)^7 & = \binom{5}{0}5^7 - \binom{5}{1}4^7 + \binom{5}{2}3^7 - \binom{5}{3}2^7 + \binom{5}{4}1^7 - \binom{5}{5}0^7\\ & = 78625 - 81920 + 21870 - 1280 + 5 - 0\\ & = 16800 \end{align*}

Method 2: If a function from a set of seven elements to a set of elements is surjective, either one element of the codomain is the image of three elements in the domain and the others are each the image of one element of the domain or two elements in the codomain are each the image of two elements of the domain and the others are each the image of one element of the domain.

One element of the codomain is the image of three elements in the domain and each of the other four elements in the codomain is the image of one element in the domain: There are five ways to select the element in the codomain that is the image of three elements in the domain, $\binom{7}{3}$ ways to select which three elements in the domain are mapped to that element, and $4!$ ways to map the remaining four elements in the domain to the remaining four elements in the codomain in such a way that those elements of the codomain are each the image of one element of the domain. There are $$\binom{5}{1}\binom{7}{3}4!$$ such cases.

Two elements of the codomain are each the image of two elements of the domain and each of the remaining three elements in the codomain are each the image of one element of the domain: There are $\binom{7}{2}$ ways to select two elements in the codomain to each be the images of two elements of the domain. There are $\binom{7}{2}$ ways to select which two of the seven elements in the domain map to the smaller of those elements and $\binom{5}{2}$ to select which two of the remaining five elements in the domain map to the larger of those elements. The remaining three elements in the domain can be mapped to the remaining three elements in the codomain in such a way that each such element in the codomain is the image of one of those elements in $3!$ ways. Hence, there are $$\binom{5}{2}\binom{7}{2}\binom{5}{2}3!$$ such surjective functions.

Therefore, there are $$\binom{5}{1}\binom{7}{3}4! + \binom{5}{2}\binom{7}{2}\binom{5}{2}3! = 4200 + 12600 = 16800$$ surjective functions from a set of seven elements to a set of five elements.

Thus, the probability that a randomly selected function from a set of seven elements to a set of five elements is surjective is $$\frac{16800}{5^7}$$

Where did I go wrong?

Look at the cases in method 2.

You counted each surjective function in which one element of the codomain is the image of three elements in the domain three times, once for each way of designating one of those three elements as the one that is mapped to that element.

You counted each surjective function in which two elements of the codomain is the image of two elements in the domain four times, once for each of the two ways you could designated one of the two elements in the domain that maps to each such element in the codomain as the one that maps to that element of the codomain.

Notice that $$3 \cdot \binom{5}{1}\binom{7}{3}4! + 2^2 \cdot \binom{5}{2}\binom{7}{2}\binom{5}{2}3! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 5^2$$

Answer 2

I agree with N. F. Taussig, of course. Here is my breakdown:

• Each element in the co-domain $B$ must have a non-empty pre-image in $A$
• Hence $A$ can be grouped into 5 distinct non-empty pre-images

So as a more general approach, the question then becomes:

• In how many ways can $n$ elements be divided into $k$ non-empty subsets?

To answer this more generally, let $\begin{bmatrix}n\\k\end{bmatrix}$ denote the number of ways to divide $n$ elements into $k$ non-empty subsets. Then we can deduce recursive rules from this:

• If the first $n-1$ elements already form $k$ non-empty subsets, the $n$-th element can then go in any of those $k$ subsets
• Otherwise the first $n-1$ elements have to form $k-1$ non-empty subsets, and the $n$-th element forms a subset on its own (a singleton)

This leads to the following recurrence relation: $$ \begin{bmatrix}n\\k\end{bmatrix}= \begin{bmatrix}n-1\\k\end{bmatrix}\cdot k+ \begin{bmatrix}n-1\\k-1\end{bmatrix} $$ One could possibly reach a closed form based on this, but here is a table of values: $$ \begin{array}{|r|rrrrrrr|} \hline &1&2&3&4&5&6&7\\ \hline 1&1&1&1&1&1&1&1\\ 2&&1&3&7&15&31&63\\ 3&&&1&6&25&90&301\\ 4&&&&1&10&65&350\\ 5&&&&&1&15&\color{blue}{140}\\ 6&&&&&&1&21\\ 7&&&&&&&1\\ \hline \end{array} $$ And the number highlighted in blue is the figure: $$ \begin{bmatrix}7\\5\end{bmatrix}=140 $$ which tells us that the $7$ elements of $A$ can be divided into $5$ non-empty pre-images in $140$ ways. Since we can permute the $5$ elements of $A$ these pre-images map to, we get a total of: $$ 140\cdot 5!=16800 $$ maps from $A$ to $B$ that are onto. Just as N. F. Taussig showed using two other approaches.

---

UPDATE: I found the numbers in The On-Line Encyclopedia of Integer Sequences, and if understand it correctly there is no closed formula for them.

Answer 3

Here's another way of working it out.You've got 7 elements in set A and 5 elements in set B.Since an onto function is our requirement,it's absolutely necessary that your required function is many-one as well(in your case).We have two choices,either only one element of our codomain is mapped to thrice,or two of them(of our codomain) are mapped to twice each. For the first case, There are 5 ways to select your element that you want to be mapped to thrice, and there are 7!/3! ways of arranging the elements properly in order to get an onto function.(3! is for the repetition).So ways=(5×7!)/3! For our second case, There are 5C2 ways to select your elements you want to be mapped to two times each,and there are 7!/(2!×2!) ways for completing the formalities!(2!×2! arises due to the repition of two elements).Thus we have ways=(5C2×7!)/(2!×2!). When added,it results to 16800, and it's a trivial matter hence to find your probability. Good day!