Counting and understanging commuting functions.

2010-10-13T23:21:19Z

Fix a positive integer $n$, and consider the functions from a set of size $n$ to itself. Let $cp(n)$ denote the number of ordered pairs $\langle f,g \rangle$ of these functions which commute, i.e., for which $f\circ g= g \circ f$. If we restrict $f$ and $g$ to be permutations, then the number of such pairs is well known: A053529 in the OEIS. But I cannot find any references to this more general case. Any pointers to existing work that I might be missing would be greatly appreciated. I've recently added the first 10 values of $cp(n)$ to the OEIS: A181162.

Obviously, $n^n\le cp(n)\le n^{2n}$. Also, $(cp(n)-n^n)/2$ is always an integer, since it counts the number of unordered pairs of distinct commuting functions. Nothing else seems to be as easy to prove as it should be. With some work, we can now show that $cp(n)$ is always divisible by $n$. I'm hoping that this is a new fact.

The investigation led me to the following strange fact about the symmetric group $S_n$. I'd like to know if this has been noticed before, or if it is also a new result. Fix a permutation $\sigma\in S_n$, and suppose that the size of the centralizer of $\sigma$ does not divide $(n-1)!$. (Note that it must divide $n!$, and the assumption is equivalent to saying that the size of $\sigma$'s conjugacy class is not a multiple of $n$). Represent $\sigma$ as a disjoint union of cycles. Then one of the following must hold:

There is a prime divisor $p$ of $n$ such that each of the cycles of $\sigma$ is either a fixed point or a cycle of size $p$.
$n$ is a multiple of 4 and each cycle of $\sigma$ has size 1, 2, or 4.

Case 1 includes the case of the identity function or $n/p$ cycles each of size $p$. There is just one $p$ for each $\sigma$, but each prime divisor of $n$ will occur is some case-1 permutation. Note that there can be at most three distinct cycle sizes in $\sigma$. If $n$ is prime, it is not hard to prove that the only possibilities for $\sigma$ are the identity and an $n$-cycle, but the general case seems to take a bit of work to establish.

Counting and understanging commuting functions. - MathOverflow

Counting and understanging commuting functions.