# How many distinct functions $f : \{1, 2, 3, 4, 5 \} \to \{1, 2, 3 \}$ are there?

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?

• What have you tried towards solving the problem? – Parcly Taxel Nov 3 '18 at 16:30
• I got 3^5 total number of functions but don't know how to go further? – Daniel Nov 3 '18 at 16:32

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.
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.$$
• 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. – Surajit Nov 19 '18 at 20:25