Combinatoric question on preimage of a function Got stuck on the following combinatoric question. Will be glad for any suggestions.

Find the number of functions $f:\{1,2,3,4\} \rightarrow \{1,2,3,4\}$ so that for all $1\le i\le4$, $f^{-1}(\{i\})≠\{i\}$ .

(i.e. Find the number of these functions in which the pre-image of a subset with a single member is different from the set containing that member.)

Now, finding the number of injective functions that fulfill this is pretty easy (it's called the number of "derangements" of a set and is the number of injective functions with no fixed point, equal in this case to 9) but there are so many other possibilities that checking them all, seems to be too tedious.
For example a partly injective function such as $f(1)=2 ,\ f(2)=2, \ f(3)=1, \ f(4)=3$ fulfills the condition in spite of $2$ being a fixed point, since the pre-image of $2$ is $\{1,2\}$ which is different from $\{2\}$.
 A: If the function were injective or surjective, and thus bijective, you would indeed be talking about a specific class of permutations called derangements.  There are $!4$ such derangements.
Since you are not restricting yourself to injective or surjective functions, we can consider all $4^4$ possible functions here.  Since the numbers are so small, we can proceed directly by cases.

*

*No fixed points:  for each $i$ we have $3$ choices for $f(i)$ to be such that $f(i)\neq i$.  There are $3^4$ such functions here.


*Exactly one fixed point: Pick which one value was fixed.  From there, in order to prevent the preimage of that point being exactly that point alone, it must be the case that for each of the other points we did not avoid mapping to it.  There are $3^3$ functions with only $1$ as a fixed point, $2^3$ of which did not map any other elements to $1$ as well, making the total number of functions with exactly one fixed point $4\cdot (3^3-2^3)$


*Exactly two fixed points: Pick which two values were fixed.  Due to the small number of available elements, we note that it must be the case that each of the two remaining elements are mapped one each to the chosen values.  There are $\binom{4}{2}\cdot 2$ such functions.
This gives a total of $$3^4+4\cdot (3^3-2^3)+\binom{4}{2}\cdot 2$$
I do not as of yet see a convenient way to approach the general problem were we to consider $\{1,2,3,\dots,n\}$ in place of merely $\{1,2,3,4\}$ as our set in question
A: You can use the inclusion-exclusion principle. Let $A_i$ denote the set of functions $f:\{1,..,n\}\to \{1,...,n\}$ s.t. $f^{-1} (i) \neq \{i\}$. Then what you are interested in is $$ | \bigcap_i A_i |= n^n - | \bigcup_i A_i^c |. $$
According to the InEx principle
$$ |\bigcup_i A_i^c | = \sum_{k=1}^n (-1)^{k-1} S_k, $$
where
$$ S_k = \sum_{ i_1<\ldots < i_k} | \bigcap_{j=1}^k A_{i_j}^c| .$$
The set $ A_i^c$ consists of fcts satisfying $f^{-1} (i) = \{i \}$. Now for fixed $i_1<...<i_k$ $$ |\bigcap_j A_{i_j}^c| = (n-k)^{n-k} ,$$
hence $$|\bigcap_i A_i | = \sum_{k=0}^n (-1)^k  \binom{n}{k} (n-k)^{n-k} .$$
The last term of the sum ($k=n$) is actually just 1, since it corresponds to the identity fct.
