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$
  • 1
    $\begingroup$ What have you tried towards solving the problem? $\endgroup$ – Parcly Taxel Nov 3 '18 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 '18 at 16:32
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$
  • $\begingroup$ how to get from 96 to 90? $\endgroup$ – Daniel Nov 19 '18 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$
  • $\begingroup$ how to get from 96 to 90? $\endgroup$ – Daniel Nov 19 '18 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 '18 at 20:25

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.