WHAT IS CYCLIC SIEVING?

Many finite sets in combinatorics have both cyclic symmetry and a natural gen-erating function. Surprisingly often the generating function evaluated at roots of unity counts symmetry classes. We call this the cyclic sieving phenomenon. More precisely, let C be a cyclic group generated by an element c of order n acting on a finite set X. Given a polynomial X(q) with integer coefficients in a variable q, say that the triple (X,X(q), C) exhibits the cyclic sieving phenomenon (CSP) if for all integers d, the number of elements fixed by cd equals the evaluation X(ζd) where ζ = e 2pii n. In particular, X(1) is the cardinality of X, so that X(q) can be regarded as a generating function for X. In the proto-example,X is the collection of all k-elements subsets of {1, 2,..., n}, and X(q) is the renowned q-binomial coefficient or Gaussian polynomial (1) X(q) =