|Monday, February 13th, 2012||4pm-5pm||Burnside 1205|
The symmetric group S(n) can be generated by two simple operations: A rotation σ = (1 2 ... n), and a swap τ = (1 2). In 1975, Herb Wilf (1931-2012) asked if a stronger result holds: Can S(n) can be sequenced "so that each is obtained from its predecessor" by σ or τ? For example,
Don Knuth rates Wilf's problem as the second most difficult open problem in his new volume of The Art of Computer Programming, and states that solutions may not be of practical value due to their complexity. In this talk we solve the sigma tau problem by constructing a cyclic solution when n is odd, and a non-cyclic solution when n is even. (This is best possible, since a campanological result by Rankin and Swan proves there are no cyclic solutions when n is even.) The construction leads to a simple algorithm that creates each successive permutation in O(1) amortized time.