Let C be a cyclic group generated by an elementc of order n. Suppose Cacts on a set X. Let X be a polynomial with integer coefficients. Then the triple is said to exhibit the cyclic sieving phenomenon if for all integers d, the value X is the number of elements fixed by cd. In particular X is the cardinality of the setX, and for that reason X is regarded as a generating function for X.
Examples
The q-binomial coefficient is the polynomial in q defined by It is easily seen that its value at q = 1 is the usual binomial coefficient, so it is a generating function for the subsets of of size k. These subsets carry a natural action of the cyclic group C of order n which acts by adding 1 to each element of the set, modulo n. For example, when n = 4 and k = 2, the group orbits are and One can show that evaluating the q-binomial coefficient when q is an nthroot of unity gives the number of subsets fixed by the corresponding group element. In the example n = 4 and k = 2, the q-binomial coefficient is evaluating this polynomial at q = 1 gives 6 ; evaluating it at q = −1 gives 2 ; and evaluating it at q = ±i gives 0.
In the Reiner–Stanton–White paper, the following example is given: Let α be a composition of n, and let W be the set of all words of length n with αi letters equal toi. A descent of a wordw is any index j such that. Define the major index on words as the sum of all descents. ---- The triple exhibit a cyclic sieving phenomenon, where is the set of non-crossing -configurations of . ---- Let λ be a rectangular partition of size n, and let X be the set of standard Young tableaux of shape λ. Let C = Z/nZ act on X via promotion. Then exhibit the cyclic sieving phenomenon. Note that the polynomial is a q-analogue of the hook length formula. Furthermore, let λ be a rectangular partition of size n, and let X be the set of semi-standard Young tableaux of shape λ. Let C = Z/kZ act on X via k-promotion. Then exhibit the cyclic sieving phenomenon. Here, and sλ is the Schur polynomial. ---- An increasing tableau is a semi-standard Young tableau, where both rows and columns are strictly increasing, and the set of entries is of the form for some. Let denote the set of increasing tableau with two rows of length n, and maximal entry. Then exhibit the cyclic sieving phenomenon, where act via K-promotion. ---- Let be the set of permutations of cycle typeλ and exactly j excedances. Let, and let act on by conjugation. Then exhibit the cyclic sieving phenomenon.
