Cyclic sieving phenomena for rooted plane trees and
tree-rooted planar maps
(57 pages)
Abstract.
We prove cyclic sieving phenomena satisfied by corner-rooted plane trees
(alias ordered trees). The sets of rooted plane trees
that we consider are: (1) all trees with n nodes;
(2) all trees with n nodes and k leaves;
(3) all trees with a given degree distribution of the nodes.
Moreover, we consider four different cyclic group actions:
(1) the root is moved to the next corner along a tour of the tree;
(2) only trees in which the root is at a leaf
are considered, and the action moves the root to the next
leaf; (3) only trees in which the root is at a non-leaf
are considered, and the action moves the root to the next
non-leaf corner;
(4) only trees in which the root is at a node of degree δ are
considered, for a fixed δ, and the action moves the root to the next
corner of this type.
We prove a cyclic sieving phenomenon for each meaningful
combination of these sets and actions.
As a bonus,
we also establish corresponding cyclic sieving phenomena
for tree-rooted planar maps.
The following versions are available:
Back to Christian Krattenthaler's
home page.