Polynomials and the art of counting: some instances of the Cyclic Sieving Phenomenon

Gaiffi, Giovanni ; Iraci, Alessandro

Matematica, cultura e società, Série 1, Tome 2 (2017) no. 2, pp. 225-238

Résumé

One of the many fascinating aspects of Enumerative Combinatorics is that it often finds contacts between different areas of mathematics, and reveals unsuspected relations. The Cyclic Sieving Phenomenon (CSP), introduced by Reiner, Stanton and White in 2004, is a recent chapter in this field. The purpose of this paper is to give a short and elementary introduction to the CSP by some examples. The gist of the story is that one starts from a set equipped with a cyclic group action, and finds a natural way to associate a polynomial to this set, with the following `magic' property: if one evaluates this polynomial at some suitable roots of 1, one gets nonnegative integers that enumerate the fixed points of the group action. In our examples many interesting combinatorial objects will come into play, like triangulations and dissections of regular polygons, noncrossing partitions, parenthesizations of lists and rooted ordered plane trees.