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!
 A: Here is a start on an answer.  I do not expect a nice closed-form answer.
The number of idempotent maps in the monoid of $n^n$ maps when $n > 0$ is easily seen
to be $\sum_{k=0}^{n} \binom{n}{k} k^{n-k}$, which asymptotically is
a small fraction of all the maps, but every such map is an $k$th power
for all $k > 0$.
Since for every map in $n^n$ there is a $k$th power of that map which is
idempotent, one has that the sequence $\{a_k\}$ where
$a_k$ is the number of $k$th powers of the monoid is eventually periodic,
with $a_k$ ranging from the number of idempotents to a number at most $n^n$.
The formula for $a_k$ will likely depend on the divisors of $k$, after you take
the idempotents into consideration.
If you wanted to do a literature search, I suggest Frobenius as a 
starting point.  Perhaps others will suggest better search terms.
There may be enumeration problems (perhaps in Richard Stanley's book(s)
Enumerative Combinatorics) which will answer the questions specifically for you.  To try it yourself, consider answering the more specific
question for arbitrary $n$ but $k$ limited to, say, 5.  Also, finding the period mentioned above should be routine.
Gerhard "Ask Me About System Design" Paseman, 2011.06.10
