Combinatoric algebra - Part 1

Define stationary $x \in S$ s.t. $f(x) = x$ .

$f(y) = z \implies z$ is stationary. Hence the number of stationary values of $f(x)$ is $\geq 1$ .

Assume $f(x)$ has $i$ stationary values. There are $\binom{n}{i}$ chooses for these.

The $n - i$ non-stationary numbers have $i$ chooses for their image.

Therefore there are $\binom{n}{i} i^{ n - i }$ unique functions $f(x)$ with exactly $i$ stationary values.

Summing over all possible values of $i$ :

Total $= \sum_{i = 1}^{n} \binom{n}{i} i^{ n - i }$ . (Unsure right now if this will give a nice answer).

---

For $n = 3$ :

Total $= \sum_{i = 1}^{3} \binom{3}{i} i^{ 3 - i } = \binom{3}{1} 1^{2} + \binom{3}{2} 2^{1} + \binom{3}{3} 3^{0} = 3 + 6 + 1 = 10$ .