7
$\begingroup$

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!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ A102709 is for $n=5$ and doesn't have all of the cross references it should. See also A103947, A103948, A103949, and A103950. $\endgroup$
    – Douglas Zare
    Commented May 30, 2011 at 19:00
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented May 30, 2011 at 19:49
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented May 30, 2011 at 19:55
  • $\begingroup$ Gerhard, for $n=3$, the answer is exactly 10 when $m% is divisible by 6. I wrote down some small cases here: math.stackexchange.com/questions/41678/… $\endgroup$
    – Kimball
    Commented May 31, 2011 at 0:20

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you this is helpful. To write out some details underlying your assertions above: Suppose $f$ is a map, and $f^b=f^{b+d}$. Then if $a,a' \geq b$ and $a \equiv a' \mod d$, we have $f^a=f^{a'}$. If we then take $p$ to be the least common multiple of the various $d$, and $N$ sufficiently large, we have $f^N=f^{N+p}$. Therefore the $a_k$ has period (at most) $p$. Anyway I have not yet found an answer to the question as posed, but this is a good start. $\endgroup$
    – Steven Spallone
    Commented Jun 22, 2011 at 20:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .