What is... cyclic sieving
What is... cyclic sieving
复制标题
什么是...循环筛分
DOI：
10.1090/noti1084
复制
发表时间：
2014
影响因子：
--
通讯作者：
J. Propp
中科院分区：
文献类型：
--
作者：
David M. Einstein;J. Propp
组合数学中的许多有限集既具有循环对称性，又具有自然生成函数。令人惊讶的是，在单位根处计算的生成函数经常计算对称类。我们称之为循环筛选现象。更精确地说，设C是一个由一个n阶元素c作用在有限集合X上生成的循环群。给定一个多项式X（q），其系数为整数，q为变量，如果对于所有整数d，由c固定的元素个数等于求值X（n），则三元组（X，X（q），C）表现出循环筛分现象（CSP），其中n = e 2π in。特别地，X（1）是X的基数，因此X（q）可以被认为是X的生成函数。在原型示例中，X是{1，2，. . .，n}，并且X（q）是著名的q-二项式系数或高斯多项式
Many finite sets in combinatorics have both cyclic symmetry and a natural generating 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 c equals the evaluation X(ζ) where ζ = e 2πi 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