Powers of maps on finite sets

2011-05-30T18:28:25Z

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!

Answer by Gerhard Paseman for Powers of maps on finite sets

2011-06-10T23:18:03Z

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

Powers of maps on finite sets - MathOverflow

Powers of maps on finite sets

Answer by Gerhard Paseman for Powers of maps on finite sets