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

Question

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$

contradiction

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)

Answer 1

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