Let's consider the following permutation,
$7, 3, 1, 2, 6, 5, 4$
Here, we find $2$ cycles:
- Starting from the first position, position $1$ has the value $7$, position $7$ has the value $4$, position $4$ has the value $2$ and so on:
$1 - 7 - 4 - 2 - 3 - 1$ - Starting from position $5$:
$6 -5 - 6$
There are $n!$ possible permutations of length $n$. It turns out that the total number of cycles in all of these permutations of length $n$ is the $n$'th term of Stirling Numbers of First Kind.
Now I am interested to know the number of cycles in all possible permutations of a 2D grid containing $n$ rows and $m$ columns. How to calculate this number? Is there any formula?
Also, how to calculate the total number of cycles in all the permutations of a 2D grid, when it is only allowed to count permutations that can be achieved by swapping any two rows or any two columns (swapping individual cells is not allowed) any number of times? Besides knowing the total number, I also want to find a formula to find the number of permutations that has $k$ cycles, where $k$ is in the range $[1,nm]$.
Example of Allowed Permutation:
Three $2$ x $2$ grids are given below, where the second one can be achieved from the first one by swapping rows at first and then swapping columns. The third grid can't be achieved from the first grid. One of the reasons is, $11$ and $12$ are in different rows in that grid, which would be impossible to achieve if we swap whole row or whole column, not individual elements. Swapping the whole row or column will only change the order of elements on that row or column, elements of that row or column won't be changed. For this reason, in the second grid, $11$ and $12$ are still in the same row.
11 12 | 22 21 | 11 22
21 22 | 12 11 | 21 12
UPD $0$: The answer to the first question is the $nm$'th term of Stirling Numbers of First Kind. You can ignore the first question and focus on the other.
UPD $1$: I calculated answers to my second question for each possible pair $(n,m)$ in the range $[1,7]$ using a C++ program. I used a bruteforce algorithm for this. I couldn't generate answers for larger $(n,m)$ because it will take a long time to calculate using the bruteforce approach. I tried to guess the formula from these numbers, but couldn't. Output of my program is here:
n \ m | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
--------------------------------------------------------------------------
1 | 1 | 3 | 11 | 50 | 274 | 1764 | 13068 |
2 | 3 | 10 | 36 | 168 | 912 | 5952 | 43824 |
3 | 11 | 36 | 138 | 636 | 3444 | 22824 | 167688 |
4 | 50 | 168 | 636 | 3024 | 16320 | 108000 | 792000 |
5 | 274 | 912 | 3444 | 16320 | 90480 | 596160 | 4370400 |
6 | 1764 | 5952 | 22824 | 108000 | 596160 | 3983040 | 29151360 |
7 | 13068 | 43824 | 167688 | 792000 | 4370400 | 29151360 | 216578880 |
UPD $2$: Using some programming, I have generated more data that helped me to find two formulas that answer parts of the question and can be the key to finding the answer:
- How many permutations of a $n$ x $m$ grid have exactly $1$ cycle?
If $GCD$ of $n$ and $m$ is greater than $1$ then the number of permutation having exactly $1$ cycle is $(n-1)!(m-1)!$. Otherwise, it is $0$, except the case where both $n$ and $m$ is equal to $1$. In that case, answer will be $1$. - How many permutations of a $1$ x $n$ grid have exactly $k$ cycles?
If the grid has $1$ row and $n$ columns then the number of permutations having $k$ cycles is the $k$'th number of the $n$'th row in triangular array of unsigned values for the Stirling numbers of the first kind.
If I can generalize the first formula for any amount of cycles or the second formula for any grid size then that will answer the whole question. Note that, I found these formulas by observing generated data. I don't have a mathematical proof for them.