ILL 1990 Problem 89

Let $n$ be a positive integer. $S_1, S_2, \ldots, S_n$ are pairwise non-intersecting sets, and $S_k$ has exactly $k$ elements $(k = 1, 2, \ldots, n)$ . Define $S = S_1\cup S_2\cup\cdots \cup S_n$ . The function $f: S \to S$ maps all elements in $S_k$ to a fixed element of $S_k$ , $k = 1, 2, \ldots, n$ . Find the number of functions $g: S \to S$ satisfying $f(g(f(x))) = f(x).$