Let $A = \{1, 2, 3, 4, 5, 6, 7\}$, and let $N$ be the number of functions $f$ from set $A$ to set $A$ such that $f(f(x))$ is a constant function.

Question

Let $A = \{1, 2, 3, 4, 5, 6, 7\}$, and let $N$ be the number of functions $f$ from set $A$ to set $A$ such that $f(f(x))$ is a constant function. Find the remainder when $N$ is divided by $1000$.

Help Needed:

I am trying to understand this solution.

Define the three layers as domain $x$, codomain $f(x)$, and codomain $f(f(x))$. Each one of them is contained in the set $A$. We know that $f(f(x))$ is a constant function, or in other words, can only take on one value. So, we can start off by choosing that value $c$ in $7$ ways. So now, we choose the values that can be $f(x)$ for all those values should satisfy $f(f(x))=c$. Let's $S$ be that set of values. First things first, we must have $5$ to be part of $S$, for the $S$ is part of the domain of $x$. Since the values in $i\in S$ all satisfy $f(i) = 5$, we have $5$ to be a value that $f(x)$ can be. Now, for the elements other than $5$:

If we have $k$ elements other than $5$ that can be part of $S$, we will have $\binom{6}{k}$ ways to choose those values. There will also be $k$ ways for each of the elements in $A$ other than $5$ and those in set $S$ (for when function $f$ is applied on those values, we already know it would be $5$). There are $6-k$ elements in $A$ other than $5$ and those in set $S$. So, there should be $6^{6-k}$ ways to match the domain $x$ to the values of $f(x)$. So, summing up all possible values of $k$ ($[1,6]$), we have

$\sum_{k=1}^6 k^{6-k} = 6\cdot 1 + 15\cdot 16 + 20\cdot 27 + 15\cdot 16 + 6\cdot 5 + 1) = 1057$ Multiplying that by the original $7$ for the choice of $c$, we have $7 \cdot 1057 = 7\boxed{399}.$

I've given two days but still not able to understand. I tried using smaller set.

Any other way to solve this problem are also welcomed.

This question has been asked here Number of functions $f$ on $\{1,\cdots,7\}$ s.t. $f(f(x))$ is constant too.

New Update (15-05-2023)

Let a small set $A=\{1,2,3,4\}$

Let constant Value is $4,$ or $3,$ or $2,$ or $1$ i.e. $f(f(x))=4,\text{or} \;3, \text{or} \;2,\text{or}\; 1 \;\forall x\in A$ and middle layer contain only one element.

For example

$f(f(1))=f(4)=4, f(f(2))=f(4)=4, f(f(3))=f(4)=4, f(f(4))=f(4)=4$ $f(f(1))=f(3)=3, f(f(2))=f(3)=3, f(f(3))=f(3)=3, f(f(4))=f(3)=3$ $f(f(1))=f(2)=2, f(f(2))=f(2)=2, f(f(3))=f(2)=2, f(f(4))=f(2)=2$ $f(f(1))=f(1)=1, f(f(2))=f(1)=1, f(f(3))=f(1)=1, f(f(4))=f(1)=1$

There are four such function obtained above.

Now Let Constant value of function $f(f(x)) $ is $4$ and middle layer contains two elements.

let two elements in middle layer to be ${3,4}$

$f(f(1))=f(4)=4, f(f(2))=f(3)=4, f(f(3))=f(4)=4, f(f(4))=f(4)=4$ $f(f(1))=f(3)=4, f(f(2))=f(4)=4, f(f(3))=f(4)=4, f(f(4))=f(4)=4$ $f(f(1))=f(3)=4, f(f(2))=f(3)=4, f(f(3))=f(4)=4, f(f(4))=f(4)=4$

Now Constant value is $4$ and middle layer contains two elements let them to be ${2,4}$

$f(f(1))=f(2)=4, f(f(2))=f(4)=4, f(f(3))=f(4)=4, f(f(4))=f(4)=4$ $f(f(1))=f(4)=4, f(f(2))=f(4)=4, f(f(3))=f(2)=4, f(f(4))=f(4)=4$ $f(f(1))=f(2)=4, f(f(2))=f(4)=4, f(f(3))=f(2)=4, f(f(4))=f(4)=4$

Now Constant value is $4$ and middle layer contains two elements let them to be ${1,4}$

$f(f(1))=f(4)=4, f(f(2))=f(1)=4, f(f(3))=f(1)=4, f(f(4))=f(4)=4$ $f(f(1))=f(4)=4, f(f(2))=f(4)=4, f(f(3))=f(1)=4, f(f(4))=f(4)=4$ $f(f(1))=f(4)=4, f(f(2))=f(4)=4, f(f(3))=f(4)=4, f(f(4))=f(4)=4$

Similarly if Constant element is $1,$ or $2,$ or $(3)$

total of such function are Thirty-Six

Now Overall function will $40$

Answer 1

Let $X$ be a non-empty set and let $f:X\to X$ be a function such that $f(f (x))=c$ for some $c\in X$.

We can describe this situation also by stating that:$$\text{im} f\subseteq f^{-1}\left(\{c\}\right)$$

Here $c=f(x)$ for some $x$ so that $f(c)=f(f(x))=c$.

So $c$ can be recognized as a fixed point of $f$ and evidently it is unique in having this property.

We discern $3$ disjoint and covering subsets of $X$:

• $A=\{c\}$
• $B=f^{-1}\left(\{c\}\right)-\{c\}$
• $C=X-f^{-1}\left(\{c\}\right)$

If we construct such function $f$ then it must be kept in mind that elements of $C$ must be mapped to elements of $B$. This forces us to exclude the case where $C\neq\varnothing$ and $B=\varnothing$.

Next to that there are no obstacles. We can just choose the sets $A$ and $B$. Then $C$ is determined and finally for every $x\in C$ we can choose some $y\in B$ for being the element with $f(x)=y$.

Doing this construction for a set that has $n>1$ elements we find:$$n\times\sum_{k=1}^{n-1}\binom{n-1}{k}k^{n-1-k}$$possibilities.

Here the absence of $k=0$ corresponds with leaving out "non-possibility" where $C\neq\varnothing$ and $B=\varnothing$.

---

addendum (concerning update of question)

Let it be that $f:\{1,2,3,4\}\to\{1,2,3,4\}$ such that $f(f(i))=4$ for every $i\in\{1,2,3,4\}$

We discern the following possibilities:

• $|f^{-1}(\{4\})|=4$ gives $1$ possibility.
• $|f^{-1}(\{4\})|=3$ gives $6$ possibilities.
• $|f^{-1}(\{4\})|=2$ gives $3$ possibilities.
• $|f^{-1}(\{4\})|=1$ gives $0$ possibilities.

The first bullet corresponds with $f(1)=f(2)=f(3)=f(4)=4$

An example for the second bullet: $f(1)=f(2)=f(4)=4$ and $f(3)=1$

An example for the third bullet: $f(1)=f(4)=4$ and $f(2)=f(3)=1$

So in total there are $6+3+1+0=10$ possibilities if the function $f\circ f$ takes value $4$ and that gives $40$ possibilities for a constant $f\circ f$.

Check yourself.

Answer 2

Combinatorially speaking, an "endofunction" or a function from S to itself is a set of cycles of rooted trees. This happens because an element a and its successors a, f(f), f(f(a)),... make a sequence that contains a nonperiodic part followed by a cyclic one.

In the problem above, c is not contain in a larger cycle than 1, $f(c) = c$. If the length is 2 and we have (d,c), then f(f(d)) = d. For larger cycles, f(f(c)) does not fall on c.

What we have now is a rooted tree with 7 nodes and depth maximum 2, since all elements are conected with the root c.

To simplify, we can disregard the c layer and we remain with 6 items forming a set of pointed sets, having the species (or class) description as

$Ens(X.Ens(X))$ with the e.g.f $exp(x.exp(x))$.

It remaind to pick up the coefficient of $ { x^6 \over 6! } = 1057$.