How many functions $f:\left \{ a,b,c,d \right \}\rightarrow \left \{ a,b,c,d \right \}$ are also transitive relations?
Sorry if I have mistakes in my English.
I understand that $f$ is supposed to be vacuously transitive or if $$<a,b>\in f \implies <b,b>\in f $$ (because else if $ <b,c>\in f $ and $b\neq c$, then $ <a,c>\in f $, but that means that $f$ isn't a function.)
But now I have a problem counting all the options. I can do it slowly and see all the options (I counted $41$) but I'm sure that there is a more elegant way to count them.
Do you have any ideas?
G. Sassatelli has already sketched the solution in a comment. If the image is $S\subseteq[n]$ with $|S|=k$, the images of the elements in $S$ are fixed (they have to be mapped to themselves), and the remaining $n-k$ elements can independently be mapped to any of the $k$ elements in $|S|$. There are $\binom nk$ subsets with $k$ elements. Thus the number of such function is
$$ \sum_{k=0}^n\binom nkk^{n-k}\;. $$
For $n=4$, this is
$$ \binom411^3+\binom422^2+\binom433^1+\binom444^0=4\cdot1+6\cdot4+4\cdot3+1\cdot1=41\;, $$
so you counted right.