Aaron Williams

Department of Mathematics and Statistics, McGill University

A solution to Wilf's sigma tau problem

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,

321, 231, 312, 123, 213, 132 is a solution for n=3 since successive permutations are obtained by applying τ, σ, σ, τ, and σ, respectively. This solution is cyclic since one more σ takes the last permutation 132 to the first 321.

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.