Skip to main content
added 578 characters in body
Source Link
Barry Cipra
  • 5.4k
  • 1
  • 33
  • 29

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.

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!$$

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.

correction
Source Link
Barry Cipra
  • 5.4k
  • 1
  • 33
  • 29

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!$$

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.)

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!$$

Source Link
Barry Cipra
  • 5.4k
  • 1
  • 33
  • 29

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.)