I have a 2D grid containing $$$n$$$ rows and $$$m$$$ columns. I can swap any two rows or any two columns any number of times (possibly zero). By swapping some rows or columns I can get different permutations of this grid. Lets's call permutations that can be achieved this way valid permutations. You can see that there are $$$n!m!$$$ valid permutations.
We know that each permutation can be represented as a product of $$$1$$$ or more disjoint cycles. For each integer $$$k$$$ in the range $$$[1, nm]$$$, I want to calculate the number of valid permutations that have exactly $$$k$$$ cycles. The bruteforce approach is iterating over all $$$n!m!$$$ possible permutations of the grid and counting cycles in each of them, which is a very slow solution and takes $$$O(n!m!nm)$$$ time. I want to find a more efficient solution (maybe dynamic programming or some combinatorial formula).
Constraints on $$$n$$$ and $$$m$$$ are not fixed. How to calculate this in a more efficient way?
I think this can be solved by using cycle index polynomials. Compute cycle index polynomials for the symmetric permutation groups $$$S_n$$$ and $$$S_m$$$ and then using these the cycle index polynomial for their Cartesian product $$$S_n * S_m$$$.
I have to study cycle index polynomial to understand your idea. I don't have much experience in group theory.
I can calculate cycle index polynomials of $$$S_n$$$ and $$$S_m$$$, but I don't understand how to compute cycle index polynomial of $$$S_n*S_m$$$ using cycle index polynomials of $$$S_n$$$ and $$$S_m$$$.
Can you please elaborate?