# Powers of maps on finite sets

Let $X_n$ be a set with $n$ elements. Write $F(X_n,X_n)$ for the set of maps from $X_n$ to itself. It is a monoid under the operation of composition. Let $m$ be a positive integer. How many maps in $F(X_n,X_n)$ are $m$th powers of other maps? In other words, how big is the image of the function which takes each map to its $m$th power? I am curious if there is a nice formula.

Note: This is entry A102709 at the Encyclopedia of Integer Sequences. However they don't seem to have a general formula.

Thanks!

-
A102709 is for $n=5$ and doesn't have all of the cross references it should. See also A103947, A103948, A103949, and A103950. – Douglas Zare May 30 '11 at 19:00
I imagine idempotency and conjugation play a big role in doing the calculations. In their studies on hyperidentitites, Denecke and Schweigert spent some time on this monoid in the late 80's and early 90's. I think they rediscovered some results of Frobenius in doing this. You might add their names to whatever computer literature search you are doing. They may not have answered this question, but have come mighty close to it. Gerhard "Ask Me About System Design" Paseman, 2011.05.30 – Gerhard Paseman May 30 '11 at 19:49
Even looking at the cases n=1 and 2 may be instructive. For n=1, all maps are idempotent (f(f())=f()) and thus are mth powers for any m. For m=2, 3 maps are idempotent and one satisfies f^3=f, so the answer alternates between 3 and 4 for even and odd m. n=3 shows some more complexity, but one can easily recognize at least 10 of the 27 maps being idempotent, so the number of mth powers is at least 10. Gerhard "Ask Me About System Design" Paseman, 2011.05.30 – Gerhard Paseman May 30 '11 at 19:55