# $f : S \rightarrow S$ is called cool, if for all elements $x$ of $S ,$ $f ( f ( f ( x ) ) ) = x$

Let $$n \geq 1$$ be an integer and consider a set $$S$$ consisting of $$n$$ numbers. $$A$$

function $$f : S \rightarrow S$$ is called cool, if for all elements $$x$$ of $$S$$

$$f ( f ( f ( x ) ) ) = x$$

Let $$A _ { n }$$ be the number of cool functions $$f : S \rightarrow S$$.

$$\bullet$$ Let $$f : S \rightarrow S$$ be a cool function, and let $$x$$ be an element of $$S$$ . Prove that the set

$$\{ x , f ( x ) , f ( f ( x ) ) \}$$

has size 1 or $$3 .$$

$$\bullet$$ Let $$f : S \rightarrow S$$ be a cool function, and let $$x$$ and $$y$$ be two distinct elements of $$S$$ . Assume that $$f ( y ) = y .$$ Prove that $$f ( x ) \neq y$$

\begin{aligned} \bullet \text { Prove that for any integer } n & \geq 4 \\ A _ { n } & = A _ { n - 1 } + ( n - 1 ) ( n - 2 ) \cdot A _ { n - 3 } \end{aligned}

Hint: Let $$y$$ be the largest element in $$S$$ . Some cool functions $$f$$ have the property that $$f ( y ) = y ,$$ whereas some other cool functions $$f$$ have the property that $$f ( y ) \neq y .$$

$$\textbf{My Solutions}$$

(a)

$$Let \quad T = \left\{ x ,f ( x ) , f ( f ( x ) ) \right\}$$ have size 1

Then all three of them are the same

$$\therefore$$ let $$x = f ( x ) = f ( f ( x ) )$$

$$\Rightarrow f ( f ( f ( x ) ) ) = f ( f ( x ) ) \quad \because f ( x ) = x$$

$$= x \quad \quad \because f ( f ( x ) ) = x$$

since it meets the condition $$f ( f ( f ( x ) ) ) = x$$ Then T can have size 1

Let $$T = \left\{ x , f ( x ) , f ( f ( x ) ) \right\}$$ have size 2 Then any two of them are the same

Case 1

$$x = f ( x ) \neq f ( f ( x ) )$$

$$f ( f ( x ) ) = f ( x ) \quad \because f ( x ) = x$$

$$= x \quad$$ contradiction

case 2

$$x \neq f ( x ) = f ( f ( x ) )$$

$$f ( f ( x ) ) = f ( f ( f ( x ) ) ) \quad \because f ( x ) = f ( f ( x ) )$$

$$= x$$

$$\because$$ elements $$x$$ of $$S$$ in cool are such that $$f ( f ( f ( x ) ) ) = x$$ hence contradiction

case 3

$$f ( x ) \neq f ( f ( x ) ) = x$$

$$f ( f ( x ) ) = x = f ( f ( f ( x ) ) )$$

$$\because$$ function cool is such that all elements $$x$$ of $$S$$ are such that $$f ( f ( f ( x ) ) ) = x$$

$$f ( f ( x ) ) = f ( f ( f ( x ) ) )$$

$$f ( x ) = f ( f ( x ) ) \quad \cdot f ( a ) = f ( b ) \Rightarrow a = b$$

Then T cannot have a size of 2

Let $$T = \{ x , f ( x ) , f ( f ( x ) ) \}$$ have size 3

Then all three are different,Let

$$x \neq f ( x ) \neq f ( f ( x ) )$$

Hence $$T$$ can have a size of $$3$$

(b)

Assume that $$f ( y ) = y , x$$ and $$y$$ are distinct elements

Let $$f ( x ) = y$$

Since all elements $$x$$ of $$S$$ for the cool function adhere to to $$f ( f ( f ( x ) ) ) = x$$

$$f ( f ( f ( x ) ) ) = f ( f ( y ) ) \quad \because \quad f ( x ) = y$$

$$= f ( y ) \quad \quad \because f ( y ) = y$$

$$= y \quad \because \quad f ( y ) = y$$

Since $$f ( f ( f ( x ) ) ) = x$$ this implies $$x=y$$ but we stated that $$x$$ and $$y$$ are distinct elements hence contradiction $$\Rightarrow f ( x ) \neq y$$

(c)

Not sure how to do this one

TL;DR

I'm not sure if (a) is 100% correct

confident with (b)

Very lost on (c)

• It seems that something is missing between "Prove that the set" and "has size 1 or 3". Probably $T =$ as in a). Feb 8, 2019 at 8:30
• thanks it was , T= $\{ x , f ( x ) , f ( f ( x ) ) \}$ Feb 8, 2019 at 8:44
• In (a) it suffices to consider the case that $T$ has size $2$ and to show that this produces a contradiction. Then automatically $T$ must have size $1$ or $3$. Feb 8, 2019 at 8:44
• Your proof of (b) is correct. Feb 8, 2019 at 8:48
• Thank you for the clarification on (a) and (b) Feb 8, 2019 at 8:54

Your proofs of (a) and (b) are correct. For (a) it suffices to show that the assumption "size of $$T$$ is $$2$$" leads to a contradiction which shortens the proof.

Next we show that $$f$$ is injective. Let $$f(x) = f(y)$$. Then $$x = f(f(f(x))) = f(f(f(y))) = y$$.

Therefore, since $$A$$ is finite, all cool functions are bijections.

Fix any element $$y$$ of $$S$$ (e.g. the largest). For a cool $$f$$ let $$T(f) = \{ y ,f(y), f(f(y)) \}$$ and $$S(f) = S \setminus T(f)$$. We clearly have $$f(T(f)) = T(f)$$, hence also $$f(S(f)) = S(f)$$ because $$f$$ is a bijection. The restrictions $$f' : S(f) \to S(f)$$ and $$f'' : T(f) \to T(f)$$ of $$f$$ are obviously cool.

Let us count the cool functions such that $$f(y)= y$$. In this case $$T(f)$$ has one element and $$S(f)$$ has $$n-1$$ elements. The restriction $$f'$$ of $$f$$ to $$S(f)$$ is cool, and there are $$A_{n-1}$$ of these functions.

Let us count the cool functions such that $$f(y) \ne y$$. Then $$T(f)$$ has three elements and $$S(f)$$ has $$n-3$$ elements. Consider all sets $$R \subset S$$ containing $$y$$ and having $$3$$ elements. There are $$\binom{n-1}{2} = (n-1)(n-2)/2$$ of these sets. For each such $$R$$ there are two cool (bijections!) $$f'' : R \to R$$ such that $$f''(y) \ne y$$. On $$S \setminus R$$ we find $$A_{n-3}$$ cool functions. This gives you $$(n-1)(n-2)A_{n-3}$$ cool functions.

Observation:

That $$f(T(f)) = T(f)$$ is obvious. The injectivity of cool functions is more general than property (b). Once we know that cool functions are bijections, we see that $$T(f)$$ cannot have two elements because on a two-element set there are only two bijections, the identity for which $$T(id)$$ is a singleton and the function exchanging the two points which is not cool.

The general idea for the recursion formula for $$A_n$$ is this:

For each $$r$$ consider all sets $$R$$ containing $$y$$ and having $$r$$ elements. There are $$\binom{n-1}{r}$$ such sets. Let $$B_r$$ be the number of cool functions $$g : R \to R$$ such that $$T(g) = R$$ (note that $$B_r$$ only depends on the number of elements of $$R$$). We have $$B_1 = 1, B_2 = 0, B_3 = 2$$ and $$B_r = 0$$ for $$r > 3$$. For each $$R$$ there are $$B_r A_{n-r}$$ cool functions $$f$$ such that $$T(f) = R$$. This gives $$\binom{n-1}{r}B_r A_{n-r}$$ cool functions. Summing these numbers over $$r$$ gives $$A_n$$.

This method can be generalized to other types of functions, e.g. $$m$$-cool functions which have the property $$x_m = x$$ where $$x_0 = x$$ and $$x_{i+1} = f(x_i)$$.