When applying twice changes nothing

331 functions

Classify every component as a fixed singleton or an oriented pair, then sum over the number of pairs.

1. If y is in the image, write y = f(x). Then f(y) = f(f(x)) = f(x) = y, so every image point is fixed.
2. Each fixed point is already one of its own preimages. The cap of two allows at most one additional element to map to it, so the functional graph consists only of fixed singletons and oriented pairs.
3. With p oriented pairs, choose their 2p elements, partition them into pairs, and choose the fixed endpoint of every pair. The orientation choices cancel the 2^p denominator from unordered pairing, leaving 6!/((6 - 2p)!p!).
4. For p = 0, 1, 2, 3 the counts are 1, 30, 180, and 120. Their sum is 331.

Condition on whether one labelled element is a singleton or belongs to an oriented pair.

1. Use the structural lemma above and let Aₙ count decompositions of n labelled elements into fixed singletons and oriented pairs.
2. A distinguished element can be a singleton, leaving Aₙ₋₁ possibilities.
3. Otherwise choose its partner in n - 1 ways and choose the fixed endpoint in 2 ways, leaving Aₙ₋₂ possibilities. Hence Aₙ = Aₙ₋₁ + 2(n - 1)Aₙ₋₂, with A₀ = A₁ = 1.
4. Successive values are 3, 7, 25, 81, and finally A₆ = 81 + 10·25 = 331.

Let S = {1, 2, 3, 4, 5, 6}. A function f: S → S satisfies both of the following conditions: (1) f(f(x)) = f(x) for every x in S; (2) for every y in S, at most two elements x in S satisfy f(x) = y. How many such functions f are there?

집합 S = {1, 2, 3, 4, 5, 6}에서 S로 가는 함수 f가 다음 두 조건을 모두 만족한다. (1) 모든 x ∈ S에 대하여 f(f(x)) = f(x)이다. (2) 각 y ∈ S에 대하여 f(x) = y를 만족하는 x ∈ S는 많아야 2개이다. 이러한 함수 f의 개수를 구하여라.