Monday, February 13th, 2012 | 4pm-5pm | Burnside 1205 |

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,

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.