Here's a simple combinatorics problem that gets me frustrated along with my attempts at an answer.
Consider the set $S=\{1,2,\ldots,2m\}$.
Find the number of...
a) Functions $f:S\rightarrow S$.
b) Functions $f:S\rightarrow S$ such that $\forall y\in S \ \exists x\in S:f(x)=y$, with m=3.
c) Functions $f:S\rightarrow S$ such that for $y\in \{2,4,6\} \ \exists x_1,x_2\in S:f(x_1)=f(x_2)=y$, with m=3.
d) Functions $f:S\rightarrow S$ such that for $y\in \{3,6\} \ \exists x_1,x_2,x_3\in S:f(x_1)=f(x_2)=f(x_3)=y$, with m=3.
a) Is fairly simple :)
For the other questions, my thoughts are these:
For b), what it says is that we need to find how many functions are onto. For $1\in S$ there are $|S|$ options for $x$. For $2\in S$ there are $|S|-1$ options, etc. So there are $|S|!$ functions with this property.
For c, if $y=1$ we have $\binom{|S|}{2}$ options, and for $y=2$ we have $\binom{|S|-2}{2}$ options, etc. Is this reasoning correct?
For d, I don't seem to be able to count...
For c) there are $2m \times (2m-1) /2 $ possibilities to map to the first element,$(2m-2) \times (2m-3) /2 $ possibilities to map to the second element, and so on. So there will be $(2m)!/2^{m}$ functions.
Similarly for d) with $ \mid S \mid =3m$ there will be $(3m)!/6^m$ functions.