Past exam of the mathematics course of the University of Cambridge / 2023 / ia / Paper 4 / 7D (Numbers & Sets)

Induction shows that every iterate $f^n$ is injective. Applying $f$ repeatedly givesIf $f^k(X)=f^{k+1}(X)$, applying $f$ inductively gives equality with every later image. Set $A=f^k(X)$. Then $f(A)=A$, so the restriction $f:A\to A$ is surjective, and it remains injective; hence it is bijective.

The relation preserves the equality pattern among positions. The identity permutation gives reflexivity, inverses give symmetry, and compositions give transitivity.

For $W_3$, representatives are the restricted-growth wordswhen $n=1$, $n=2$, and $n\ge 3$, respectively. Here digits denote distinct symbols, and each displayed word represents one class.

For $W_4$ with $n=3$, the fourteen classes have representativesThe cyclic subgroup $F$ gives finer classes than all of $P_4$. For example, $x_1{x}_1{x}_2$ and $x_1{x}_1{x}_3$ have the same equality pattern and are equivalent under $P_4$, but no power of the four-cycle fixes $x_1$ while sending $x_2$ to $x_3$. Thus the two equivalence-class decompositions of $W_3$ differ.