3
$\begingroup$

This is based on the question at here

I want to know how many onto functions are there from set $A={1,2,3,4,5}$ to set $B={a,b,c}$.

This is how I did it: First i tried to find the functions which are not onto
case 1: All in A maps to a single element of B
There are 3 ways for this

case2:
When mappings are made for only two elements in range.
First we have to select 2 out of 3 elements.That can be done in $3\choose 2$$=3$ways.
Consider mappings to only (a,b).
Number of ways when only one item maps to a=5
Number of ways when only two items maps to a=$5\choose 2$
Number of ways when only three items maps to a=$5\choose 3$

Number of ways when only four items maps to a=$5\choose 4$
Total mappings only to (a,b)=30.
Hence in case 2 total non onto mappings are$=30*3=90$

By case1 and case2 Total non onto mappings are $90+3=93$

Therefore onto mappings are $3^5=93=150$

My question is in the given answer mappings for case2 is obtained as , there are 2^5 = 32 possible functions, so we have 3*32 = 96 functions here that aren't onto.

What's wrong with my method?
Can someone please tell me where I have done wrong?

$\endgroup$
  • $\begingroup$ possible duplicate of Calculating the total number of surjective functions $\endgroup$ – hardmath Dec 30 '14 at 14:30
  • $\begingroup$ @hardmath No, this is a question about why a particular method miscounts. $\endgroup$ – user147263 Dec 30 '14 at 17:29
  • $\begingroup$ As both answers show, your answer is correct (and the reference has an error). $\endgroup$ – user84413 Dec 30 '14 at 22:06
3
$\begingroup$

$2^5$ also counts the maps with only one element in the image. When you then multiply by $3$ you double count the functions that send only to one element.

For example the function $f_a$ (that sends everything to $a$). Is counted in the case $(a,b)$ and $(a,c)$. Since there are $3$ such functions we have to subtract $3$ to the outcome and we get $96-3=93$ which you had before.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

I'll consider $\{1,2,3\}$ instead of $\{a,b,c\}$ (it's easier for the notation)

For $i\in\{1,2,3\}$, let $A_i$ denote the set of all function $f:\{1,...,5\}\to\{1,2,3\}\backslash \{i\}$. A function $f:\{1,...,5\}\to\{1,2,3\}$ is onto if it doesn't belong to $\bigcup_{i=1}^3 A_i$. By inclusion exclusion formula, $$\left|\bigcup_{i=1}^3 A_i\right|=\sum_{\emptyset\neq I\subset \{1,2,3\}}(-1)^{|I|-1}\left|\bigcap_{i\in I}A_i\right|$$ For any non-emptyset, $I\subset \{1,2,3\}$, $$\left|\bigcap_{i\in I}A_i\right|=(3-|I|)^5,$$ because $\bigcap_{i\in I}A_i$ is the set of all function $f:\{1,...,5\}\to\{1,2,3\}\backslash I$. Therefore, $$\left|\bigcup_{i=1}^3 A_i\right|=\sum_{\emptyset\neq I\subset \{1,2,3\}}(-1)^{|I|-1}(3-|I|)^5=\sum_{i=1}^3(-1)^{i-1}\binom{3}{i}(3-i)^5.$$

We conclude that the number of onto function is $$3^5-\left|\bigcup_{i=1}^3 A_i\right|=\sum_{i=0}^3(-1)^i\binom{3}{i}(3-i)^5=...$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.