1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Counting on a Rectangular Array

  1. Jun 29, 2009 #1
    1. The problem statement, all variables and given/known data
    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.

    2. Relevant equations

    3. 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.
    Last edited: Jun 29, 2009
  2. jcsd
  3. Jun 29, 2009 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
  4. Jun 30, 2009 #3


    User Avatar
    Science Advisor
    Homework Helper

    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??
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook