In combinatorial mathematics, cyclic sieving is a phenomenon by which evaluating a generating function for a finite set at roots of unity counts symmetry classes of objects acted on by a cyclic group.[1]
Let C be a cyclic group generated by an element c of order n. Suppose C acts on a set X. Let X(q) be a polynomial with integer coefficients. Then the triple (X, C, X(q)) is said to exhibit the cyclic sieving phenomenon (CSP) if for all integers d, the value X(e2id/n) is the number of elements fixed by cd. In particular X(1) is the cardinality of the set X, and for that reason X(q) is regarded as a generating function for X.
\left[{n\atopk}\right]q
is the polynomial in q defined by
\left[{n\atopk}\right]q=
| |||||||||||||||
|
.
\binom{n}{k}
\{1,3\}\to\{2,4\}\to\{1,3\}
and
\{1,2\}\to\{2,3\}\to\{3,4\}\to\{1,4\}\to\{1,2\}
One can show[2] that evaluating the q-binomial coefficient when q is an nth root 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
\left[{4\atop2}\right]q=1+q+2q2+q3+q4;
evaluating this polynomial at q = 1 gives 6 (as all six subsets are fixed by the identity element of the group); evaluating it at q = −1 gives 2 (the subsets and are fixed by two applications of the group generator); and evaluating it at q = ±i gives 0 (no subsets are fixed by one or three applications of the group generator).
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 to i. A descent of a word w is any index j such that
wj>wj+1
\operatorname{maj}(w)
----
The triple
(Xn,Cn-1,
| 1 | |
| [n+1]q |
\left[{2n\atopn}\right]q)
Xn
----
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
| (X,C, | [n]!q |
| \prod(i,j)\in[hij]q |
)
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
(X,C,q-\kappa(λ)
| 2,...c,q | |
| s | |
| λ(1,q,q |
k-1))
\kappa(λ)=\sumi(i-1)λi
----
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
1,2,...c,\ell
\ell
Inck(2 x n)
2n-k
(\operatorname{Inc}k(2 x n),C2n-k,qn+\binom{k{2}}
| \left[{n-1\atopk | |
| \right] |
q\left[{2n-k\atopn-k-1}\right]q}{[n-k]q})
C2n-k
----
Let
Sλ,j
aλ,j(q)=
| \sum | |
| \sigma\inSλ,j |
q\operatorname{maj(\sigma)-\operatorname{exc}(\sigma)}
Cn
Sλ,j
Then
(Sλ,j,Cn,aλ,j(q))