What is the Product of the Orders of all Elements in a Symmetric Group?

Question

I need to determine the product of all element orders in a symmetric group size $N$. For example, if my group is size $N = 3$, then the answer would be $$1(123) * 2(132) * 2(321) * 2(213) * 3(312) * 3(231) = 72$$ The end result should be calculated mod $1000000009$. Obviously this number gets very big, and I was wondering if the mod could somehow help reduce the calculations. Memoization and caching results are also a possible method I have thought of. Thank you.

Answer 1

A much faster way than multiplying the orders of all the elements as you check each one is to loop over all cycle types. The cycle type of an element of $S_n$ is a partition of $n$, that is a nonincreasing list of positive integers whose sum is $n$. This represents the length of the cycles in a decomposition of the element into disjoint cycles. The order of an element of cycle type $\lambda=(\lambda_1,\ldots,\lambda_k)$ is the least common multiple of $\lambda_1,\ldots,\lambda_k$. This gives you the order $o_\lambda$. Then you just need to know the number of elements of cycle type $\lambda$, which the non-accepted answer tells you here:

Calculating quantity of elements of a specific cycle-type in alternating and symmetric groups.

That answer treats the cycle type in opposite order, i.e. it treats it as a nondecreasing sequence of integers. Given that number of elements $m$, you multiply by $o_\lambda^m$ to account for cycle type $\lambda$. To speed things up, you can do exponentiation by squaring.