Discrete Math Homework Page --- Spring 2004

Homework Set 1 --- Due Tuesday, January 20:
  1. Is there a permutation ladder which generates the permutation "54321" from the home position "12345"?
  2. What is the least number of rungs needed in such a ladder?
  3. What is the least number of rungs needed to generate the permutation "321" from the home position "123"?
  4. In general, what is the least number of rungs needed to reverse a permutation on n elements?
  5. Prove that given any permutation on any number of objects, there is some permutation ladder whcih generates that permutation.