4
$\begingroup$

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$.

$\endgroup$
4
  • 1
    $\begingroup$ Never heard a function called "transitive," and the definition uses another non-standard term, "reduction." You are going to need to be clearer. Even the set notation is odd - if the only condition is $f\in X$ then you have only described $X$, so why not write it as $\{a,b,c,d\}\rightarrow \{a,b,c,d\}$ $\endgroup$ Commented Sep 4, 2014 at 14:24
  • $\begingroup$ @ThomasAndrews, recall that a function is a relation with the property: for all $x$ in the domain there's a unique $y$ in the codomain such that $f(x)=y$. Therefore, it's acceptable to describe a function as transitive. $\endgroup$ Commented Sep 4, 2014 at 14:29
  • $\begingroup$ I actually meant "restriction" and not "reductoin". Let me correct that. $\endgroup$ Commented Sep 4, 2014 at 14:31
  • 3
    $\begingroup$ So you are saying, if $f(x)=y$ and $f(y)=z$ then $f(x)=z$? That would mean $f(f(x))=f(x)$. $\endgroup$ Commented Sep 4, 2014 at 14:34

3 Answers 3

Reset to default
11
$\begingroup$

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$.

$\endgroup$
7
  • $\begingroup$ Yeah, I just wanted to be sure :) $\endgroup$ Commented Sep 4, 2014 at 14:43
  • 1
    $\begingroup$ "Note that the image has at least one point and that is fixed", can you explain why? $\endgroup$ Commented Sep 4, 2014 at 15:17
  • $\begingroup$ The image must have at least one point because $f(a)$ has to be something. It cannot be undefined. That something is fixed by the argument in the first paragraph above. In other words, the fact that $f(f(a))=f(a)$ is a direct consequence of the assumption that $f$ is transitive. $\endgroup$ Commented Sep 4, 2014 at 15:25
  • $\begingroup$ For the case of two fixed points, assuming they are $a$ and $b$, can't $f(c) = d$ and vice versa? Why must they be an element of $\{a, b\}$? $\endgroup$ Commented Sep 4, 2014 at 17:49
  • $\begingroup$ No if $f(c)=d$, then $d$ would be in the image, so it would have to be a fixed point too. $\endgroup$ Commented Sep 4, 2014 at 17:51
5
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Thanks for the clear answer... and a link to OEIS! $\endgroup$ Commented Sep 4, 2014 at 14:55
2
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.