Counting on a Rectangular Array

[snipez90]

Homework Statement

Suppose you have an a x b rectangular array of distinct integers (think of it as a matrix if you would like). Now suppose we first move across the columns and take a permutation of the entries in each column. Informally, we can imagine the integers in the array as cards, and our first step is to perform a "vertical shuffle" by "shuffling" the cards in each vertical column.

Next, we perform a "horizontal shuffle" by moving down the rows and taking a permutation of the entries in each row. Finally, we perform another "vertical shuffle", described above. Show that this procedure gives us all possible permutations of the entries in the original rectangular array.

Homework Equations

The Attempt at a Solution

I'll be happy to clarify the problem statement if needed. Anyways, I am fairly bad at counting , so I'm not sure how to approach this. The only approach I pursued for awhile was through direct counting. The number of permutations we get from permuting the entries in the entire array is (a*b)!. The first vertical shuffle gives us [(a!)]^b possible permutations of the array, while the subsequent horizontal shuffle gives [(b!)]^a possible permutations. I think these two steps do not result in any overcounting, and I think the calculations are correct. Unfortunately, the final step, which is to perform another vertical shuffle, is complicated, and I'm having trouble with even the small cases.

I'm interested in how one might approach this problem. I would be happy if the problem could be done using my approach, but I very much doubt it. Thanks in advance.

 

[Hurkyl]

My instincts say rather than count, try to write an algorithm that takes any permutation and finds a way to build it in this manner.

 

[Dick]

Right. Counting is hard, since you have two vertical shuffles. One could undo part of what the other does, so it's going to be hard to make sure the final permutations are all distinct. Here's a hint. Suppose someone tells you, "Hey, that problem is SOOO EASY. I don't even need the first vertical shuffle! Just use the horizontal shuffle to put every number into the correct (i.e. where it is supposed to wind up) column and then use the vertical shuffle to make sure every number is in the correct row." Can you explain to them why that won't work??