3

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?

Eyan
  • 103
  • Notice that "vacuous transitivity" is a bit sketchy for functions, since for all $x$ there must be some pair $(x,y)\in f$. I suggest the following idea: the condition you said is equivalent to $$f|{\operatorname{im}(f)}=\operatorname{id}{\operatorname{im}(f)}$$ i.e. $f$ being the identity on its image. So, the idea is: select a subset $S$ to be the image of $f$ and count all the functions $\widehat f: X\setminus S\to S$ (recall that there is exactly one function $\emptyset \to X$). Sum over the subsets $S\subseteq X$ and you'll get the desired number. –  Jun 14 '16 at 18:47

1 Answers1

1

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.

joriki
  • 238,052