Find the number of onto functions

For discussing Olympiad Level Combinatorics problems
User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
Find the number of onto functions

Unread post by Anindya Biswas » Tue Mar 16, 2021 3:36 pm

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$.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Find the number of onto functions

Unread post by Mehrab4226 » Tue Mar 16, 2021 8:00 pm

It will be easier to understand if we see the figure.
Screenshot 2021-03-16 at 19.52.16.png
Screenshot 2021-03-16 at 19.52.16.png (66.67KiB)Viewed 4189 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.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Find the number of onto functions

Unread post by Anindya Biswas » Tue Mar 16, 2021 8:48 pm

Mehrab4226 wrote:
Tue Mar 16, 2021 8:00 pm
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. :oops:
Hint :
You can use inclusion-exclusion principle, the answer contains a summation.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Find the number of onto functions

Unread post by Mehrab4226 » Wed Mar 17, 2021 1:55 am

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$
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Post Reply