4
$\begingroup$

How many distinct functions $f : \{1, 2, 3, 4, 5 \} \to \{1, 2, 3 \}$ are there, from the set $\{1, 2, 3, 4, 5\}$ to the set $\{1, 2, 3\}$, whose range is a set of size exactly $2$?

I got $3^5$ total number of functions but don't know how to go further?

$\endgroup$
2
  • 1
    $\begingroup$ What have you tried towards solving the problem? $\endgroup$ Nov 3, 2018 at 16:30
  • 1
    $\begingroup$ I got 3^5 total number of functions but don't know how to go further? $\endgroup$
    – Daniel
    Nov 3, 2018 at 16:32

2 Answers 2

4
$\begingroup$

We first need to decide which elements comprise the function's range. There are $\binom32=3$ ways of doing so.

Then for each element in the domain of the function, we need to decide whether it maps to the smaller or larger element in that chosen range. There are $2^5=32$ ways of doing so, but two of them map all elements in the domain to only one element in the codomain, so are excluded. Thus there are 30 possible functions for each choice of range, and 90 functions in all satisfying the given conditions.

$\endgroup$
1
  • $\begingroup$ how to get from 96 to 90? $\endgroup$
    – Daniel
    Nov 19, 2018 at 12:43
4
$\begingroup$

You can choose a two element set from $\{1,2,3\}$ in $\binom 32=3$ ways, and for each such choice there exists $2^5$ many functions. But 2 of them are constant. Thus, for each two element set of the range, there are $2^5-2$ number of non constant functions. So, the total number of required functions are $3\times(2^5-2)=90.$

$\endgroup$
2
  • $\begingroup$ how to get from 96 to 90? $\endgroup$
    – Daniel
    Nov 19, 2018 at 12:43
  • 1
    $\begingroup$ For a chosen 2 element subset of $\{1,2,3\}$, for example say $\{1,3\}$, there exists $2^5$ functions $f:\{1,2,3,4,5\}\rightarrow \{1,3\}$, two of which are constant, namely $f=1$ and $f=3$. And for these constant function, the size of the range becomes 1, so we need to throw out these constant functions. Now total number of 2 element subset of $\{1,2,3\}$ is 6. Therefore we need to subtract 6 from 96. $\endgroup$
    – Surajit
    Nov 19, 2018 at 20:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .