numbering the squares of a rectangular grid, was: counting sequences of pairs

Question

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.

Answer 1

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.

Answer 2

If I understand the problem correctly, the second stipulation in Definition 4, which allows arbitrary permutations of the sets $A$ and $B$, renders the infinite extensions unnecessary: All you're really doing, in effect, is labelling the boxes of an $m \times n$ grid with the numbers from 1 to $N=mn$ and then permuting the rows and columns so that the 1 is in the upper left hand corner and the top row and leftmost column are in increasing order. So you just have to count how many ways you can create such an arrangement to begin with.

If you fill out the top row first, which can be done in $N-1 \choose n-1$ ways, you'll be left with $N-n \choose m-1$ ways to fill out the leftmost column, after which the remaining $(m-1)\times(n-1)$ grid can be filled out in $[(m-1)(n-1)]!$ ways so the answer (written with $mn$ in place of $N$) would seem to be

$${mn-1 \choose n-1}{mn-n \choose m-1}[(m-1)(n-1)]!$$

inequivalent splittings. For your example, with $m=2$ and $n=3$, this gives

$${5\choose2}{3\choose1}2! = 60$$

Does that agree with what you get? (Also, is there a reason you require $N$ to be even? There's nothing here that depends on it.)

Added 6/10/12: The OP has (very politely) pointed out that I did not understand the problem correctly, and also that I managed to find an unnecessarily complicated form for the irrelevant answer that I did give, which would have been much better given as

$$(mn)!\over m!n!$$

Added 6/11/12: Let me try to make precise just how badly I misunderstood the OP's problem. If you number the squares of an $m \times 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. I managed to overlook the third of these groups by confusing it with the cyclic permutations of the rows and columns. What the OP wants, I believe, is the number of orbits among the $(mn)!$ numberings of the grid under the combined action of all three groups.