3
$\begingroup$

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)

$\endgroup$
5
  • 2
    $\begingroup$ It seems that something is missing between "Prove that the set" and "has size 1 or 3". Probably $T = $ as in a). $\endgroup$
    – Paul Frost
    Feb 8, 2019 at 8:30
  • $\begingroup$ thanks it was , T= $\{ x , f ( x ) , f ( f ( x ) ) \}$ $\endgroup$ Feb 8, 2019 at 8:44
  • $\begingroup$ 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$. $\endgroup$
    – Paul Frost
    Feb 8, 2019 at 8:44
  • $\begingroup$ Your proof of (b) is correct. $\endgroup$
    – Paul Frost
    Feb 8, 2019 at 8:48
  • $\begingroup$ Thank you for the clarification on (a) and (b) $\endgroup$ Feb 8, 2019 at 8:54

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.