"Polya theory revisited"

Polya theory is about 'enumeration under symmetry'. Let X be a finite set and G be a group acting on X. This splits X into orbits and one may ask 'how many orbits are there?, What are their sizes? Is there some natural way to label the orbits?' For example, 'everybody knows' there are n^(n-2) labeled trees on n vertices, rooted at 1. The symmetric group S_(n-1) acts to give 'unlabeled trees' There are no nice formulas and the questions above are of interest. Computer scientists Goldberg and Jerrum have introduced a Markov chain, 'the Burnside Process' which allows progress but raises its own questions 'What is the automorphism group of a given tree and how can random elements of this be chosen'? Another special case is a group acting on itself by conjugation and the problem becomes one of enumerating conjugacy classes. For the symmetric group S_n the Burnside process seems to give the fastest effective way of choosing a random partition of n (!). There are quite a few examples where 'things work out' but many more open problems.