Find the number of surjective functions
Let $m \geq n > 0$. Find the number of surjective functions from $B_m =\{1, 2, \cdots , m\}$ to $B_n = \{1,2,\cdots , n\}$
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
-
- Posts:461
- Joined:Wed Dec 15, 2010 10:05 am
- Location:Dhaka
- Contact:
Re: Find the number of surjective functions
Bhaia, I don't know whether my ans. is right or wrong;But i use exclusion-inclusion to solve it.
And the ans. is:
\[n^{m}-\binom{n}{1}\left ( n-1 \right )^{m}+\binom{n}{2}(n-2)^{m}-...............+(-1)^{n-1}n\]
Please reply.
And the ans. is:
\[n^{m}-\binom{n}{1}\left ( n-1 \right )^{m}+\binom{n}{2}(n-2)^{m}-...............+(-1)^{n-1}n\]
Please reply.
You spin my head right round right round,
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
Re: Find the number of surjective functions
Please give complete solution. Your answer seems to be correct, though!
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
-
- Posts:461
- Joined:Wed Dec 15, 2010 10:05 am
- Location:Dhaka
- Contact:
Re: Find the number of surjective functions
There are \[n^{m}\] ways to make any function.
There are \[\binom{n}{1}\left ( n-1 \right )^{m}\] ways to make a function not using one element from co-domain.
There are \[\binom{n}{2}\left ( n-2 \right )^{m}\]ways to make a function not using two elements from co-domain.
In this way,
.
.
.
There are \[\binom{n}{n-1}\left ( n-n+1 \right )^{m}= n\]ways to make a function not using n-1 elements from co-domain.
Now using exclusion-inclusion method and find the number of surjective function:
\[n^{m}-\binom{n}{1}\left ( n-1 \right )^{m}+\binom{n}{2}(n-2)^{m}-...............+(-1)^{n-1}n\]
Do i have to give more explaination?
There are \[\binom{n}{1}\left ( n-1 \right )^{m}\] ways to make a function not using one element from co-domain.
There are \[\binom{n}{2}\left ( n-2 \right )^{m}\]ways to make a function not using two elements from co-domain.
In this way,
.
.
.
There are \[\binom{n}{n-1}\left ( n-n+1 \right )^{m}= n\]ways to make a function not using n-1 elements from co-domain.
Now using exclusion-inclusion method and find the number of surjective function:
\[n^{m}-\binom{n}{1}\left ( n-1 \right )^{m}+\binom{n}{2}(n-2)^{m}-...............+(-1)^{n-1}n\]
Do i have to give more explaination?
You spin my head right round right round,
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )
When you go down, when you go down down......(-$from$ "$THE$ $UGLY$ $TRUTH$" )