How many functions are transitive? Let the set of all functions defined as: $\left\{a,b,c,d\right\} \rightarrow \{a,b,c,d\}$
How many functions are transitive?  
I've been told to use the fact that a function is transitive iff "it's restriction to it's image is the identity function on it's image".
I'm not so sure I understood the hint. The answer should be $41$, though I understood I may prove it for an arbitrary $n$ and then solve it for $n=4$.
 A: Let $S=\{a,b,c,d\}$. Let $T$ be the image of $f$. Then $f(t)=t$ for all $t\in T$, and $f:S\setminus T\to T$ can be anything.
There are $$|T|^{|S\setminus T|}$$ such functions for each $T$. So it depends only on the size of $T$, we'd have:
$$\sum_{\emptyset\neq T\subseteq S} |T|^{|S\setminus T|}=\sum_{t=1}^4 \binom{4}{t}t^{4-t}=4\cdot1^3+6\cdot2^2+4\cdot3^1+1\cdot4^0=41$$
When $S$ has $n$ elements, this is OEIS sequence A000248.
The general formula for $|S|=n$ would be:
$$\sum_{t=0}^n \binom{n}{t} t^{n-t}$$
Note that when $n>0$, $t=0$ contributes zero, but including $t=0$ gives the value $1$ for $n=0$, since $0^0=1$.
A: There is some subset on which it is the identity function, and all elements not in that subset are mapped into that subset.  That subset cannot be empty because some elements are mapped to members of it.
So first choose one of the $15$ subsets to be the image.  Then one must choose where to map the other elements.  The number of ways to do that depends on the size of the chosen set.
So either


*

*The image is $\{a,b,c,d\}$ and then we're done; or

*The image has three members; there are four ways to choose that set of three, and then there are three ways to choose where to map the non-member; and $4\times3=12$; or

*The image has two members; there are six ways to choose which set of two; there are four ways to choose where to map the non-members; and $6\times 4 = 24$; or

*The image has one member; there are four ways to choose which one; and there is only one way to choose where to map the non-members; and $4\times1=4$.


So the total is $1+12+24+4=41$.
A: This is unusual terminology, but legitimate. We usually talk about a relation being transitive, meaning that $aRb,bRc$ implies $aRc$. If we take $R$ to be the relation which has $aRf(a)$, then it will be transitive if $aRf(a)$ and $f(a)Rb$ implies $aRb$. But since $f()$ is a function that means $b$ must equal $f(a)$. In other words, the point $f(a)$ which belongs to the image of $f()$ is fixed.
That explains the terminology. Answering the question requires careful counting. Let us count functions with 1,2,3,4 fixed points. Note that the image has at least one point and that is fixed, so those are the only possibilities.
Taking the easiest first, suppose it has 4 fixed points. There is only one such function, it has $f(a)=a,f(b)=b,f(c)=c,f(d)=d$.
Suppose there is one fixed point. That means the image has only one point. So there are just 4 such functions. For example, $f(a)=f(b)=f(c)=f(d)=a$.
Now suppose there are three fixed points. Suppose they are $a,b,c$. That gives us $f(a),f(b),f(c)$. There are now three choices for $f(d)$, it can be either $a,b$ or $c$. So that gives us a total of $4\times 3=12$ functions with 3 fixed points.
Finally, consider two fixed points. We can choose the 2 in 6 ways. Suppose they are $a,b$. Now there are two choices for each of $f(c),f(d)$ - they can each be $a$ or $b$. So that is 24 functions with 2 fixed points. 
Adding $\large 4+ 1 + 12 + 24=41$. 
