Hi,


Barry Cipra has rephrased my question in far superior clarity and brevity in an addendum to his answer below. I quote:


"If you number the squares of an $m×n$ grid, you can let three groups act on the numbering: arbitrary permutations of the rows, arbitrary permutations of the columns, and *cyclic* permutations of the numbers. [...]. What the OP wants,[...], is the number of orbits among the $(mn)!$ numberings of the grid under the combined action of all three groups."


For recreation you can read my original convoluted way of asking a mathematically equivalent question. I leave it for historical reasons until somebody with lots of rep removes it or tells me to do so:


Please excuse the clumsy style, I am no mathematician.


**Definition 1:**
Given a sequence $U=\{1,...,N\}$ of length N, extend it periodically to minus and plus infinity and call this $U\_{\infty}$ (e.g. if $N=2$ then $U\_{\infty}=\{...,2,1,2,1,2,1,2,...\}$).


Now I want to make sequences of pairs out of this. Basically getting two sequences as result.


**Definition 2:**
Given $N,n$ and $m$ with $N,n,m \in \mathbb{N}$, and $n m =N$, call $f$ a splitting of $N$ into $n$ and $m$ if $f$ is a bijective function $f:\{1,...,N\} \rightarrow A\times B$, where $A$ and $B$ are the sets $A=\{1,...,n\}$ and $B=\{1,..,m\}$.


**Definition 3:**
Each splitting $f$ defines an infinite sequence of pairs, denoted $f\_{\infty}$, by taking the sequence $$\{f(1),...,f(N)\}={a\_1 \choose b\_1},...,{a\_N \choose b\_N}$$ where $a\_i \in A, b\_i \in B$ and then extending this periodically to plus and minus infinity.


**Definition 4:**
Now define two splittings $f$ and $g$ equivalent if any of the two conditions hold:


1. they produce the same infinite
sequence $f\_{\infty} = g\_{\infty}$
(this gets rid of cyclic
permutations like ($(a\_n,b\_n)
 \rightarrow (a\_{n+1
 \;\text{mod}\;N},b\_{n+1
 \;\text{mod}\;N})$).
2. if $f\_{\infty}$ can be obtained from
$g\_{\infty}$ by renaming the
elements in $A$ or $B$ or both.1.


For example, take $N=6$, $A= \{1,2\}, B=\{1,2,3\}$, and define $f$ such that $f\_{\infty}$ is as follows (I will only write one period): $$...{1 \choose 1},{1 \choose 2},{1 \choose 3},{2 \choose 1},{2 \choose 2},{2 \choose 3}...$$


This would be equivalent to 
$$...{2 \choose 2},{1 \choose 3},{1 \choose 1},{1 \choose 2},{2 \choose 3},{2 \choose 1}...$$
because the latter can be obtained from the former by renaming the elements of set $B$ like $\{1\rightarrow 3,2\rightarrow 1,3\rightarrow 2\}$ and then putting the last pair first.


Now I would like to know, how many non-equivalent splittings are there?


**Examples:**


As suggested by comments below, here two simple examples to make it more clear and maybe help intuition:


$n=1$ such that $N=m$: 


There is only one distinctive splitting, as every $g\_{\infty}$ can be obtained from an arbitrary $f\_{\infty}$ by renaming the elements in $B$.


$N=4,n=2$ such that $m=2$ as well: 


The $N$ elements in $A \times B$ can be put into a sequence in $N!$ ways, or in other words there are $N!$ splittings. So here there are $24$ already! If we use the method suggested by Barry Cipra in his answer below to sort out those splittings that are equivalent by the renaming of elements within $A$ or $B$, then we are left with $6$ sequences. The $2 \times 2$ grids for these 6 (the requirement is the 1 in top left corner, and increasing numbers in top row and leftmost column) are:


1 2 | 1 2 | 1 3 | 1 3 | 1 4 | 1 4  

3 4 | 4 3 | 2 4 | 4 2 | 2 3 | 3 2


the sequences corresponding to these are (cartesian coordinate style, the number in the grid element corresponds to the slot in the sequence):


$${1 \choose 2},{2 \choose 2},{1 \choose 1},{2 \choose 1}$$
$${1 \choose 2},{2 \choose 2},{2 \choose 1},{1 \choose 1}$$
$${1 \choose 2},{1 \choose 1},{2 \choose 2},{2 \choose 1}$$
$${1 \choose 2},{2 \choose 1},{2 \choose 2},{1 \choose 1}$$
$${1 \choose 2},{1 \choose 1},{2 \choose 1},{2 \choose 2}$$
$${1 \choose 2},{2 \choose 1},{1 \choose 1},{2 \choose 2}$$


But of those the first and the last, the second and the fifth and the third and the first are equivalent due to cyclic permutation and the right renaming within $A$ or $B$. Note that only a cyclic permutation itself is not enough. Also, it just happens that those equivalent here are the "time-reversals" of each other... 


So we end up with three non-equivalent splittings in this case.



numbering the squares of a rectangular grid, was: counting sequences of pairs 
This is not a finished answer and I’m not even sure it can lead to a result, but I’ll post it anyway in case someone finds it helpful.


The standard way of counting orbits is using Burnside’s lemma: if a finite group $G$ acts on a set $X$, the number of orbits is
$$\DeclareMathOperator\fix{Fix}\DeclareMathOperator\N{N}\DeclareMathOperator\lcm{lcm}\frac1{|G|}\sum\_{g\in G}|\fix(g)|=\sum\_{i=1}^t\frac{|\fix(g\_i)|}{|\N\_G(g\_i)|},$$
where $\fix(g)$ is the set of elements of $X$ fixed by $g$, $\N\_G(g)$ is the normalizer of $g$ in $G$, and $g\_1,\dots,g\_t$ are representants of conjugacy classes of $G$.


In our case, $G\simeq S\_m\times S\_n\times C\_{mn}$. I will write elements of $G$ as $g=(\pi,\rho,k)$, where $\pi\in S\_m$ is a permutation of rows, $\rho\in S\_n$ is a permutation of columns, and $k\in C\_{mn}$ is a cyclic shift of numbers by $k$ positions.


The conjugacy class of $g$ is determined by the cycle structure of $\pi$, $\rho$, and $k$.


The permutation $k\in C\_{mn}$ consists of $d=\gcd(k,mn)$ cycles of length $mn/d$.


If $\pi$ has cycles of lengths $a\_1,\dots,a\_r$, and $\rho$ has cycles of lengths $b\_1,\dots,b\_s$ ($\sum\_ia\_i=m$, $\sum\_jb\_j=n$), then for each $i,j$, the combined permutation has $\gcd(a\_i,b\_j)$ cycles of length $\lcm(a\_i,b\_j)$.


If a grid is fixed by $g$, then the cycle structures of $k$ and $(\pi,\rho)$ have to match, and any such grid is uniquely determined by an assignement of numbers $1,\dots,d$ so that each of the $d$ cycles of $(\pi,\rho)$ contains one grid position with such a number. Thus:
$$|\fix(g)|=\begin{cases}\left(\frac{mn}d\right)^dd!,&\text{if }\forall i,j\\:\lcm(a\_i,b\_j)=mn/d,\\\\[1em]
0&\text{otherwise.}\end{cases}$$
Now, what remains is to count the number of permutations with the same cycle structure (this is straightforward combinatorics) and to evaluate the resulting sum (which is bound to be messy). I wouldn’t expect a closed formula to come out, but maybe one could get some asymptotic estimates, or something that would be easier to evaluate than brute force counting for purposes of computer simulation.


**Example:**


Let me do the $n=m=2$ case. It is somewhat trivialized since there is at most one permutation of any given cycle structure. The breakup is like this (I’m only listing cases where $\fix(g)\ne\varnothing$:


$$\begin{array}{|c|c|c|c|c|}
\hline
d&a\_1,\dots,a\_r&b\_1,\dots,b\_s&\text{# of }g&|\fix(g)|\\\\
\hline
4&1,1&1,1&1&24\\\\
2&1,1&2&1&8\\\\
2&2&1,1&1&8\\\\
2&2&2&1&8\\\\
\hline
&&&\text{total}&48\\\\
\hline
\end{array}$$


Since $|G|=2\times2\times4=16$, we get $48/16=3$ orbits.


The case $m=2$, $n=3$ is more illustrative:


$$\begin{array}{|c|c|c|c|c|c|}
\hline
d&|\fix(g)|&a\_1,\dots,a\_r&b\_1,\dots,b\_s&\text{# of }g&\text{contribution}\\\\
\hline
6&720&1,1&1,1,1&1&720\\\\
3&48&2&1,1,1&1&48\\\\
3&48&2&1,2&3&144\\\\
2&18&1,1&3&4&72\\\\
1&6&2&3&4&24\\\\
\hline
&&&&\text{total}&1008\\\\
\hline
\end{array}$$


$|G|=2\times6\times6=72$, hence we have $1008/72=14$ orbits.


