Let $A$ and $B$ be finite sets. If the number of elements in $A$ is $|A|=k$ and number of elements in $B$ is $|B|=n$ Find the number of onto functions (surjective functions) from $A$ to $B$ in terms of $n$ and $k$.
Re: Find the number of onto functions
Posted: Tue Mar 16, 2021 8:00 pm
by Mehrab4226
It will be easier to understand if we see the figure.
Screenshot 2021-03-16 at 19.52.16.png (66.67KiB)Viewed 5249 times
From $A$ there can be at most one line from each element. Because it is a figure of a function. Any element of $A$ producing more than one line will contradict the fact that it is a function.
Now, which each element of $B$ must have at least one line touching them. So if we keep them in order like $B_1,B_2,B_3,\cdots B_n$ then there should be which $n$ elements of the set $A$ must-have line with these $n$ elements of $B$, we will get $^kp_n$. This works because we can choose n elements from $A$ and join lines with $B$ in order. As a result by each permutation, we will get different onto functions. Now we have $k-n$ elements left each of which can be paired with $n$ different elements. So there should be $(k-n)\times n$ such linings.
So the total number of onto function is $^kp_n \times (k-n) \times n$ (ans)
The reasoning can be a little difficult to understand for my bad solution writing. If you find any problems please post it.
It will be easier to understand if we see the figure.
Screenshot 2021-03-16 at 19.52.16.png
From $A$ there can be at most one line from each element. Because it is a figure of a function. Any element of $A$ producing more than one line will contradict the fact that it is a function.
Now, which each element of $B$ must have at least one line touching them. So if we keep them in order like $B_1,B_2,B_3,\cdots B_n$ then there should be which $n$ elements of the set $A$ must-have line with these $n$ elements of $B$, we will get $^kp_n$. This works because we can choose n elements from $A$ and join lines with $B$ in order. As a result by each permutation, we will get different onto functions. Now we have $k-n$ elements left each of which can be paired with $n$ different elements. So there should be $(k-n)\times n$ such linings.
So the total number of onto function is $^kp_n \times (k-n) \times n$ (ans)
The reasoning can be a little difficult to understand for my bad solution writing. If you find any problems please post it.
Sorry to say, but you overcounted.
Hint :
You can use inclusion-exclusion principle, the answer contains a summation.
Re: Find the number of onto functions
Posted: Wed Mar 17, 2021 1:55 am
by Mehrab4226
Thanks, I really didn't notice the overcounting .Since You said there will be summation and principle of inclusion-exclusion, this should be it,
We first find all the functions we can make using A and B, which is $n^k$ because each element of A can be paired with any other element of B(Any ONE). To keep only the onto functions we need to subtract all the functions which is $A \to$ a proper subset of B. If we think about the subsets with $n-1$ elements, there are ${n} \choose {n-1}$ subsets and each will have $(n-1)^k$ functions. So total number of functions is ${n} \choose {n-1}$ $(n-1)^k$ So we subtract it. But we subtracted some functions more than once which are made of subsets of B with elements less than $(k-1)$. Similarly, they will be added.
We will finally get,
$n^k-{n\choose n-1}(n-1)^k+{n \choose n-1}(n-2)^k - \cdots$
which is,
$\sum_{i=0}^{n} (-1)^i{n\choose n-i}(n-i)^k$
.Since You said there will be summation and principle of inclusion-exclusion, this should be it,