# Cyclic sieving for two families of non-crossing graphs

Svetlana Poznanović¹

¹School of Mathematics, Georgia Institute of Technology, Atlanta, GA, USA

**Abstract.** We prove the cyclic sieving phenomenon for non-crossing forests and non-crossing graphs. More precisely, the cyclic group acts on these graphs naturally by rotation and we show that the orbit structure of this action is encoded by certain polynomials. Our results confirm two conjectures of Alan Guo.

**Résumé.** Nous prouvons le phénomène de crible cyclique pour les forêts et les graphes sans croisement. Plus précisément, le groupe cyclique agit sur ces graphes naturellement par rotation et nous montrons que la structure d'orbite de cette action est codée par certains polynômes. Nos résultats confirment deux conjectures de Alan Guo.

**Keywords:** cyclic sieving, non-crossing forests, non-crossing graphs

## 1 Introduction

The notion of cyclic sieving phenomenon was introduced by Reiner, Stanton, and White in [4], generalizing Stembridge's $q = -1$ phenomenon. It involves a finite set $X$, a cyclic group acting on $X$, and a polynomial $X(q) \in \mathbb{N}[q]$. The triple $(X, C, X(q))$ is said to exhibit the cyclic sieving phenomenon if for every $c \in C$ of order $d$,

$$ \#\{x \in X : c(x) = x\} = X(w_d), \qquad (1) $$

where $w_d$ is a primitive $d$-th root of unity. In other words, the evaluations of the polynomial $X(q)$ at appropriate roots of unity carry all the numerical information about the $C$-orbit structure. In particular, $X(1)$ is the cardinality of $X$. For a survey of the literature on cyclic sieving, the reader is referred to [5].

A non-crossing graph of size $n$ is a graph with vertex set $\{1, 2, \dots, n\}$ arranged in a circle whose edges are straight line segments that do not cross. See Fig. 1 for illustration. From now on every graph will be non-crossing, and for simplicity, this word will often be omitted. The number of forests of size $n$ and $k$ components is

$$ f_{n,k} = \frac{1}{2n-k} \binom{n}{k-1} \binom{3n-2k-1}{n-k}, \qquad (2) $$

while the number of graphs of size $n$ with $k$ edges is

$$ g_{n,k} = \frac{1}{n-1} \sum_{j=0}^{k} \binom{n-1}{k-j} \binom{n-1}{j+1} \binom{n-2+j}{n-2}. \qquad (3) $$
<figure><img src="image_1.png" /><figcaption>Fig. 1: A non-crossing graph of size 8 with 7 edges and a non-crossing forest of size 9 with 3 components.</figcaption></figure>

Both (2) and (3) were derived in [2]. These formulas admit natural $q$-analogues:

$$X(q) = \frac{1}{[2n-k]_q} \left[ \begin{matrix} n \\ k-1 \end{matrix} \right]_q \left[ \begin{matrix} 3n-2k-1 \\ n-k \end{matrix} \right]_q \quad (4)$$

$$Y(q) = \frac{1}{[n-1]_q} \sum_{j=0}^{n-2} \left[ \begin{matrix} n-1 \\ k-j \end{matrix} \right]_q \left[ \begin{matrix} n-1 \\ j+1 \end{matrix} \right]_q \left[ \begin{matrix} n-2+j \\ n-2 \end{matrix} \right]_q q^{j(j+n-k+2)}, \quad (5)$$

where we are using the usual notation: $[n]_q = 1 + q + \cdots + q^{n-1} = \frac{1-q^n}{1-q}$, $[n]!_q = [n]_q[n-1]_q \cdots [1]_q$, and

$$\left[ \begin{matrix} n \\ k \end{matrix} \right]_q = \frac{[n]!_q}{[k]!_q[n-k]!_q}.$$

Let the cyclic group of order $n$ act by rotation on graphs with $n$ vertices. In this paper, we prove that forests and graphs, with this action of the cyclic group and the polynomials $X(q)$ and $Y(q)$, respectively, exhibit the cyclic sieving phenomenon. Namely,

**Theorem 1.1.** Let $X$ be the set of non-crossing forests on $n$ vertices with $k$ components. If $d|n$ and $\omega_d$ is a primitive $d$-th root of unity, then the number $s_d(n, k)$ of elements of $X$ which are fixed under rotation by $\frac{2\pi}{d}$ is equal to $X(\omega_d)$.

**Theorem 1.2.** Let $Y$ be the set of non-crossing graphs on $n$ vertices with $k$ edges. If $d|n$ and $\omega_d$ is a primitive $d$-th root of unity, then the number $s_d(n, k)$ of elements of $Y$ which are fixed under rotation by $\frac{2\pi}{d}$ is equal to $Y(\omega_d)$.

This proves the conjectures from [3], where Guo proves the cyclic sieving phenomenon for non-crossing connected graphs. It should be noted that the cyclic-sieving phenomenon for trees, namely the case $k=1$ in Theorem 1.1, was first proved by Eu and Fu in [1]. The authors first prove that quadrangulations of a polygon exhibit the cyclic sieving phenomenon, where the cyclic action is cyclic rotation of the polygon, and then give a bijection between quadrangulations of a $2n$-gon and trees on $n$ vertices, which preserves the cyclic sieving phenomenon.

In the following two sections we prove Theorem 1.1 and Theorem 1.2 by treating each case separately. We follow a similar line of proof as in the case of connected graphs. As the reader can note, there are structural similarities between these families of graphs that at places require similar arguments. Despite this, none of the results implies another one and all these graphs have to be treated separately. The proof in each case seems to work out "magically" due to the fact that the corresponding generating functions
satisfy certain polynomial equations that help us simplify the expressions we obtain and apply Lagrange inversion. This note aims to highlight the similarities and the differences between the aforementioned graphs, with the hope that they would give an insight that would lead to a unifying proof.

As we have mentioned, in several places we will use Lagrange inversion to extract coefficients of certain generating functions.

**Lagrange inversion.** Let $\phi(u) \in \mathbb{Q}[[u]]$ be a formal power series with $\phi(0) \neq 0$, and let $y(z) \in \mathbb{Q}[[u]]$ satisfy $y = z\phi(y)$. Then, for an arbitrary series $\psi$, the coefficient of $z^n$ in $\psi(y)$ is given by

$$[z^n]\psi(y(z)) = \frac{1}{n}[u^{n-1}]\phi(u)^n\psi'(u).$$

Lagrange inversion may be applied to bivariate generating functions by treating the second variable as a parameter.

## 2 Non-crossing forests

The authors in [2] computed the numbers $f_{n,k}$ using Lagrange inversion. In the process, they obtained some polynomial equations related to the generating function $F(z, w) = \sum f_{n,k}z^nw^k$ which will be useful in our proofs. We state them here.

Let $T(z)$ be the generating function for non-crossing trees with respect to size. Then $T$ satisfies

$$T^3 - zT + z^2 = 0. \qquad (6)$$

Each forest can be obtained from a tree by substituting each vertex by a pair (vertex, forest). The substitution yields

$$F = 1 + T(zF) \qquad (7)$$

whereby we are counting the empty forests as well. One can use (6) to eliminate $T$, which yields

$$F^3 + (z^2 - z - 3)F^2 + (z + 3)F - 1 = 0. \qquad (8)$$

This equation admits a Lagrange form, upon setting $F = 1 + wy$,

$$y = z(1 + wy) \left( \frac{1 - \sqrt{1 - 4y}}{2y} \right), \qquad (9)$$

from which the explicit formula (2) for $f_{n,k}$ follows.

We will also use the following property of the Catalan generating function $Cat(z) = \frac{1-\sqrt{1-4z}}{2z}$, which can also be obtained using Lagrange inversion:

$$[z^m]Cat(z)^n = \frac{n}{n+m} \binom{2m+n-1}{m}. \qquad (10)$$

We will prove Theorem 1.1 by verifying the condition (1) stated in the introduction. For that, we first evaluate $X(q)$ at roots of unity. The following lemma is repeatedly used.

**Lemma 2.1.** Let $n, m_1, m_2, k$, and $d$ be positive integers. Let $\omega_d$ be a primitive $d$-th root of unity. Then
(a) The factor $[m]_q$ has a simple zero at $q = w_d$ if and only if $d|m$, $d \neq 1$.

(b) If $m_1 \equiv m_2 \mod d$, then

$$ \lim_{q \to w_d} \frac{[m_1]_q}{[m_2]_q} = \begin{cases} \frac{m_1}{m_2} & \text{if } m_1 \equiv m_2 \equiv 0 \mod d, \\ 1 & \text{if } m_1 \equiv m_2 \not\equiv 0 \mod d. \end{cases} $$

(c) (q-Lucas theorem) If $n = ad + b$ and $k = rd + s$, where $0 \ge r, s \le d-1$, then

$$ \begin{bmatrix} n \\ k \end{bmatrix}_{q=\omega_d} = \begin{pmatrix} a \\ r \end{pmatrix} \begin{bmatrix} b \\ s \end{bmatrix}_{q=\omega_d}. $$

**Proposition 2.2.** Let $d|n$ and $n' = \frac{n}{d}$. Then

$$ X(\omega_d) = \begin{cases} \frac{n'-k'+1}{2n'-k'} \binom{n'}{k'-1} \binom{3n'-2k'-1}{n'-k'} & \text{if } d \ge 2 \text{ and } k' = \frac{k}{d} \in \mathbb{N}, \\ \binom{n'}{k'} \binom{3n'-2k'-2}{n'-k'-1} & \text{if } d = 2 \text{ and } k' = \frac{k+1}{2} \in \mathbb{N}, \\ 0 & \text{otherwise.} \end{cases} $$

**Proof:** If $d|k$, then by part (c) of Lemma 2.1,

$$ \begin{bmatrix} 3n - 2k - 1 \\ n - k \end{bmatrix}_{q=\omega_d} = \begin{pmatrix} 3n' - 2k' - 1 \\ n' - k' \end{pmatrix}. $$

On the other hand, both $[2n-k]_{q=\omega_d} = 0$ and $\begin{bmatrix} n \\ k-1 \end{bmatrix}_{q=\omega_d} = 0$. By examining the factors in the numerator and denominator and using parts (a) and (b) of Lemma 2.1, one gets

$$ \frac{1}{[2n-k]_{q=\omega_d}} \begin{bmatrix} n \\ k-1 \end{bmatrix}_{q=\omega_d} = \frac{n' - k' + 1}{2n' - k'} \binom{n'}{k'-1}. $$

For $d=2$ and $k$ odd, the result follows by applying the q-Lucas theorem to both q-binomial coefficients. Finally, if $d \ge 3$ and $d$ does not divide $k$, $[2n-k]_{q=\omega_d} \ne 0$, the first q binomial coefficient vanishes for $k \ne 1 \mod d$, and the second one vanishes for $k \equiv 1 \mod d$. $\square$

## 2.1 The case $d=2$ and $k$ is odd

Every centrally symmetric forest on $n$ vertices has exactly one diameter edge and is determined by the forest on one side of that diameter which necessarily has $k' + 1$ components. Denote by $\tilde{f}_{n,k}$ the number of forests on $n$ vertices with $k$ components such that the vertices 1 and $n$ are connected by an edge. Since there are $n'$ ways to choose the diameter edge, we have

$$ s_2(2n', 2k' + 1) = n' \tilde{f}_{n'+1, k'+1}. $$
**Proposition 2.3.** The number of non-crossing forests on $n$ vertices with $k$ components in which the vertices 1 and $n$ are connected by an edge is given by

$$ \tilde{f}_{n,k} = \frac{1}{n-1} \binom{n-1}{k-1} \binom{3n-2k-3}{n-k-1}. \qquad (11) $$

Consequently,

$$ s_2(2n', 2k' + 1) = \binom{n'}{k'} \binom{3n' - 2k' - 2}{n' - k' - 1}. $$

**Proof:** Removing the edge $\{1, n\}$ from such a forest would produce a forest with $k + 1$ components in which the vertices 1 and $n$ are in different components. Such a forest can be obtained from two trees by substituting each vertex except $n$ by a pair (vertex, forest). The substitution construction yields

$$ \sum \tilde{f}_{n,k} z^n w^{k+1} = \frac{(wT(zF))^2}{F}. $$

One can eliminate $T$ using (7) and then, since $F$ satisfies (8), we get

$$ \sum \tilde{f}_{n,k} z^n w^{k+1} = F^2 + (z^2 w^3 - zw^2 - 2)F + (zw^2 + 1). \qquad (12) $$

Therefore,

$$ \tilde{f}_{n,k} = [z^n w^{k+1}] F^2 + [z^{n-2} w^{k-2}] F - [z^{n-1} w^{k-1}] F - 2[z^n w^{k+1}] F. \qquad (13) $$

Only one of these coefficients needs to be computed:

$$ [z^n w^{k+1}] F^2 = [z^n w^{k+1}] (1 + wy)^2 = 2[z^n w^k]y + [z^n w^{k-1}]y^2 $$

and, using Lagrange inversion,

$$ \begin{aligned} [z^n w^{k-1}] y^2 &= \frac{1}{n} [u^{n-1} w^{k-1}] (1 + wu)^n Cat(u)^n 2u \\ &= \frac{2}{n} \binom{n}{k-1} [u^{n-k-1}] Cat(u)^n = \frac{2}{2n-k-1} \binom{n}{k-1} \binom{3n-2k-3}{n-k-1}. \end{aligned} $$

Substituting this into (13) yields

$$ \tilde{f}_{n,k} = \frac{2}{2n-k-1} \binom{n}{k-1} \binom{3n-2k-3}{n-k-1} + f_{n-2,k-2} - f_{n-1,k-1}, $$

which simplifies to (11). $\square$

## 2.2 The case $d = 2$ and $k$ is even

For each centrally symmetric forest of size $2n'$, there are well-defined vertices

$$ 1 \le v_1 < v_2 < \dots < v_m \le n', $$
<figure><img src="image_2.png" /><figcaption>Fig. 2: The vertices $v_1, \dots, v_m$ for a forest with $m = 5$.</figcaption></figure>

such that for $1 \le i \le m$, the graph on the vertices between $v_i$ and $v_{i+1}$, inclusive, is a forest with an edge between $v_i$ and $v_{i+1}$ (we define $v_{m+1}$ to be the vertex $v_1 + n'$), or possibly empty in the case when $v_{i+1} - v_i = 1$, and $v_i$ and $v_j$ are not connected by an edge if $|j - i| \ge 2$. See Fig. 2 for illustration.

Recall that $\tilde{f}_{n,n-k}$ counts forests of size $n$ and $n-k$ components, and therefore $k$ edges, which contain the edge $\{1, n\}$. Define $f_{n,k}^*$ to be

$$f_{n,k}^* = \begin{cases} 1, & \text{if } n=2, k=0 \\ \tilde{f}_{n,n-k}, & \text{otherwise.} \end{cases}$$

Then, the number $a_{n,k}$ of centrally symmetric graphs of size $2n$ and $k$ pairs of antipodal edges (where we count each diameter edge as a pair) that can be obtained by gluing together forests counted by $f_{n,k}^*$ is

$$a_{n,k} = \sum_{m=1}^{n} \sum_{k_1+\cdots+k_m=k} \sum_{1 \le v_1 < v_2 < \cdots < v_m \le n} \prod_{i} f_{v_{i+1}-v_i+1, k_i}^* \quad (14)$$

Note that not all the graphs counted by $a_{n,k}$ are forests. Namely, a cycle will be formed exactly when none of the forests we use in the gluing process is the forest with 2 vertices and no edges. The number of such graphs is

$$b_{n,k} = \sum_{m=1}^{n} \sum_{k_1+\cdots+k_m=k} \sum_{1 \le v_1 < v_2 < \cdots < v_m \le n} \prod_{i} \tilde{f}_{v_{i+1}-v_i+1, v_{i+1}-v_i+1-k_i} \quad (15)$$

Therefore,

$$s_2(2n', 2k') = a_{n',n'-k'} - b_{n',n'-k'} \quad (16)$$

and this difference indeed does not count forests with odd number of edges because they are counted by both $a_{n',n'-k'}$ and $b_{n',n'-k'}$. Let $A(z, w)$, $B(z, w)$, $\tilde{F}(z, w)$, and $F^*(z, w)$ denote the generating functions for $a_{n,k}$, $b_{n,k}$, $\tilde{f}_{n,k}$, and $f_{n,k}^*$, respectively. Then

$$F^*(z, w) = \tilde{F}(zw, \frac{1}{w}) + z^2. \quad (17)$$
As explained in [3, Lemma 4.2], (14) and (15) imply that

$$A(z, w) = z \frac{\frac{\partial}{\partial z} \left( \frac{F^*(z, w)}{z} \right)}{1 - \frac{F^*(z, w)}{z}} \quad \text{and} \quad B(z, w) = z \frac{\frac{\partial}{\partial z} \left( \frac{\tilde{F}(zw, 1/w)}{z} \right)}{1 - \frac{\tilde{F}(zw, 1/w)}{z}}.$$

Using (17), we get

$$A(zw, \frac{1}{w}) = z \frac{\frac{\partial}{\partial z} \left( \frac{\tilde{F}(z,w) + z^2 w^2}{zw} \right)}{1 - \frac{\tilde{F}(z,w) + z^2 w^2}{zw}} \quad \text{and} \quad B(zw, \frac{1}{w}) = z \frac{\frac{\partial}{\partial z} \left( \frac{\tilde{F}(z,w)}{zw} \right)}{1 - \frac{\tilde{F}(z,w)}{zw}}.$$

Solving these differential equations, we obtain

$$\sum \frac{a_{n,n-k}}{n} z^n w^k = -\log\left(1 - \frac{\tilde{F}(z,w) + z^2 w^2}{zw}\right) \quad \text{and} \\ \sum \frac{b_{n,n-k}}{n} z^n w^k = -\log\left(1 - \frac{\tilde{F}(z,w)}{zw}\right).$$

From (12) we get

$$\tilde{F} = \frac{1}{w} F^2 + (z^2 w^2 - zw - \frac{2}{w}) F + (zw + \frac{1}{w}).$$

Using this and (8), we obtain

$$\sum \frac{a_{n,n-k} - b_{n,n-k}}{n} z^n w^k = \log\left(1 - \frac{\tilde{F}}{zw}\right) - \log\left(1 - \frac{\tilde{F} + z^2 w^2}{zw}\right) = \log(F).$$

Finally, using (16) and Lagrange inversion, we have

$$s_2(2n', 2k') = n'[z^n w^k] \log(F) = \frac{n'(n'-1)(3n'-2k'-1)}{2n'-k'(k'-1)} \quad (18) \\ = \frac{n'-k'+1}{2n'-k'} \binom{n'}{k'-1} \binom{3n'-2k'-1}{n'-k'} = X(-1).$$

## 2.3 The case $d \ge 3$

Since each edge in the forest in not longer than $\frac{n}{d}$, it lies in a free orbit under the action of rotation. Therefore, if $d$ does not divide the number of edges $n-k$, which happens if and only if $d$ does not divide $k$, then in fact there are no forests with $k$ components that are fixed under rotation by $\frac{2\pi}{d}$. This agrees with the fact that in this case also $X(\omega_d) = 0$.

Consider now the case when $d|k$. Let $n' = \frac{n}{d}$ and $k' = \frac{k}{d}$. We have the following lemma.

**Lemma 2.4.** $s_d(n, k) = s_2(2n', 2k')$.

**Proof:** We construct a bijection between forests on $dn'$ vertices and $dk'$ components that are fixed under rotation by $\frac{2\pi}{d}$ and forests counted by $s_2(2n', 2k')$ in the following way. Construct a forest on $2n'$ vertices labeled 1, 2, ..., $2n'$ by drawing an edge from $i$ to $j$ for every such edge in the original graph. Moreover,
for every edge from $i$ to $(d-1)n' + j$, $1 \le i, j \le n'$ in the original graph draw an edge between $i$ and $n' + j$. See Fig. 3 for illustration. Note that if $F$ is a forest fixed by a rotation of $\frac{2\pi}{d}$, then all its edges are of length strictly less than $d$, where by length of an edge we mean the absolute difference of its endpoints. Moreover, it has a total of $d(n' - k')$ edges which form orbits of size $d$ under this action. This implies that the graph obtained by the construction described above will be a non-crossing forest with $2n'$ vertices and $2(n' - k')$ edges, i.e., $2k'$ components. It is easy to see that this map is a bijection. $\square$

<figure><img src="image_3.png" /><figcaption>**Fig. 3:** Example of the bijection for $n = 12, k = 3$, and $d = 3$. The edges $\{2, 8\}$ and $\{3, 8\}$ in the image correspond to the edges $\{2, 12\}$ and $\{3, 12\}$ in the original forest.</figcaption></figure>

Combining Lemma 2.4, (18), and Proposition 2.2 we get

$$s_d(n, k) = s_2(2n', 2k') = \frac{n' - k' + 1}{2n' - k'} \binom{n'}{k' - 1} \binom{3n' - 2k' - 1}{n' - k'} = X(\omega_d).$$

This completes the proof of Theorem 1.1.

# 3 Non-crossing graphs

Let $C(z, w)$ and $G(z, w)$ be the generating functions for connected graphs and graphs, respectively, where $z$ marks vertices and $w$ marks edges. Using a combinatorial argument, it can be shown [2] that

$$wC^3 + wC^2 - z(1 + 2w)C + z^2(1 + w) = 0.$$

Each graph can then be obtained by replacing a vertex in a non-crossing graph by a (vertex, graph). Therefore,

$$G(z, w) = 1 + C(zG(z, w), w). \qquad (19)$$

Eliminating $C$ in (19) we arrive at

$$wG^2 + ((1+w)z^2 - (1+2w)z - 2w)G + w + z(1+2w) = 0. \qquad (20)$$

This becomes amenable to Lagrange inversion upon the change of variables $G = 1+z+zy$ that transforms it into

$$y = z(1 + w) \frac{1 + y}{1 - wy}. \qquad (21)$$
**Proposition 3.1.** Let $d|n$ and $n' = \frac{n}{d}$. Then

$$ Y(\omega_d) = \begin{cases} \sum_{j=0}^{k'} \binom{n'-1}{k'-j} \binom{n'-1}{j} \binom{n'+j-2}{n'-2} & \text{if } d=2 \text{ and } k' = \frac{k}{2} \in \mathbb{N}, \\ \sum_{j=0}^{k'} \binom{n'-1}{k'-j} \binom{n'}{j+1} \binom{n'+j-1}{n'-1} & \text{if } d=2 \text{ and } k' = \frac{k+1}{2} \in \mathbb{N}, \\ \sum_{j=0}^{k'} \binom{n'}{k'-j} \binom{n'-1}{j} \binom{n'+j-1}{n'-1} & \text{if } d \ge 3 \text{ and } k' = \frac{k}{d} \in \mathbb{N}, \\ 0, & \text{otherwise.} \end{cases} $$

**Proof:** Set $j' = \lfloor \frac{j}{d} \rfloor$. In the case $d=2$, using part (c) of Lemma 2.1, one gets $\lfloor \frac{n-2+j}{n-2} \rfloor_{q=\omega_d} = \binom{n'+j'-1}{n'-1}$,

$$ \begin{bmatrix} n-1 \\ j+1 \end{bmatrix}_{q=\omega_d} = \begin{cases} \binom{n'-1}{j'} & \text{if } j \text{ is even,} \\ \binom{n'-1}{j'+1} & \text{otherwise,} \end{cases} \quad \text{and} \quad \begin{bmatrix} n-1 \\ k-j \end{bmatrix}_{q=\omega_d} = \begin{cases} \binom{n'-1}{k'-j'-1} & \text{if } k \text{ is even, } j \text{ is odd} \\ \binom{n'-1}{k'-j'} & \text{otherwise.} \end{cases} $$

Summing over all $j'$ yields the first two parts of the proposition. The case $d \ge 3$ can be analyzed similarly, by evaluating each $q$-binomial coefficient separately. In both cases the summands of $Y(\omega_d)$ are nonzero only when $j \equiv 0, 1 \mod d$. If $d|k$ the resulting sum is the third part of the proposition. Otherwise, the terms pairwise cancel and the sum is zero. $\square$

## 3.1 The case $d=2$ and $k$ is odd

Similarly to the case of forests, every centrally symmetric graph with odd number of edges has exactly one diameter edge and is completely determined by the subgraph on one side of that edge. Let $\tilde{g}_{n,k}$ be the number of graphs with $n$ vertices and $k$ edges that contain the edge $\{1, n\}$. Then

$$ s_2(n, k) = n' \tilde{g}_{n'+1, k'+1}. $$

**Proposition 3.2.** The number of non-crossing graphs on $n$ vertices with $k$ edges in which the vertices 1 and $n$ are connected by an edge is given by

$$ \tilde{g}_{n,k} = \frac{1}{n-1} \sum_{j=0}^{k-1} \binom{n-2}{k-j-1} \binom{n-1}{j+1} \binom{n+j-2}{n-2}. \qquad (22) $$

Consequently,

$$ s_2(2n', 2k' + 1) = Y(-1). $$

**Proof:** Let $\tilde{G}(z, w)$ be the generating function for $\tilde{g}_{n,k}$ and let $\tilde{C}(z, w)$ be the generating function for connected graphs in which 1 and $n$ are connected by a vertex. Each graph which has the edge $\{1, n\}$ can be obtained from a connected graph that has the edges $\{1, n\}$ by substituting each vertex with a pair (vertex, graph). Therefore,

$$ \tilde{G} = \frac{\tilde{C}(zG, w)}{G}. $$

The author in [3] derives the following formula for $\tilde{C}$, although not explicitly stated in this form:

$$ \tilde{C} = \frac{w}{w+1} (C^2 + C - z). $$
Using (19) we can eliminate C and we arrive at

$$ \tilde{G} = \frac{w}{w+1} (G-1-z) = \frac{zwy}{w+1}. \qquad (23) $$

From here using Lagrange Inversion, one obtains the formula (22). □

## 3.2 The case $d = 2$ and $k$ is even

Let $d_{n,k}$ denote the number of centrally symmetric graphs with $2n$ vertices and $k$ pairs of antipodal edges, where each diameter edge is again counted as a pair.

**Lemma 3.3.**

$$ d_{n,k} = \sum_{j=0}^{k} \binom{n}{k-j} \binom{n-1}{j} \binom{n+j-1}{n-1}. \qquad (24) $$

**Proof:** For each graph counted by $d_{n,k}$ there is a unique subset of vertices $1 \le v_1 < \dots < v_m \le n$, such that the graph on the vertices between $v_i$ and $v_{i+1}$, inclusive, has an edge between $v_i$ and $v_{i+1}$ (we define $v_{m+1}$ to be the vertex $v_1 + n'$), or is possibly empty in the case when $v_{i+1} - v_i = 1$, and $v_i$ and $v_j$ are not connected by an edge if $|j - i| \ge 2$. Set

$$ g_{n,k}^* = \begin{cases} 1, & \text{if } n=2, k=0, \\ \tilde{g}_{n,k}, & \text{otherwise.} \end{cases} $$

Then, from the argument above, we have

$$ d_{n,k} = \sum_{m=1}^{n} \sum_{k_1+\dots+k_m=k} \sum_{1 \le v_1 < v_2 < \dots < v_m \le n} \prod_{i=1}^{n} g_{v_{i+1}-v_i+1, k_i}^*, \qquad (25) $$

and, consequently,

$$ \sum d_{n,k} z^n w^k = z \frac{\frac{\partial}{\partial z} \left( \frac{\tilde{G} + z^2}{z} \right)}{1 - \frac{\tilde{G} + z^2}{z}}. $$

Dividing both sides by $z$ and integrating yields

$$ \sum \frac{d_{n,k}}{n} z^n w^k = - \log \left( 1 - \frac{\tilde{G} + z^2}{z} \right) = \log(1 + y). $$

The last equality follows from (21) and (23). Extracting the coefficients of $\log(1 + y)$ yields (24). □

On the other hand, $d_{n,k} = s_2(2n, 2k-1) + s_2(2n, 2k)$. This can be used to compute $s_2(2n, 2k)$:

$$ \begin{align*} s_2(2n, 2k) &= d_{n,k} - s_2(2n, 2k-1) \\ &= \sum_{j=0}^{k} \binom{n}{k-j} \binom{n-1}{j} \binom{n+j-1}{n-1} - \sum_{j=0}^{k-1} \binom{n-1}{k-j-1} \binom{n}{j+1} \binom{n+j-1}{n-1} \\ &= \sum_{j=0}^{k} \binom{n-1}{k-j} \binom{n-1}{j} \binom{n+j-2}{n-2}. \end{align*} $$
The last equality follows by comparing the coefficients in front of $a^{n-1}b^k$ on both sides of the identity

$$ \frac{(1+a)^{n-1}(1+b)^n}{(1-ab)^n} - \frac{b(1+a)^n(1+b)^{n-1}}{(1-ab)^n} = \frac{(1+a)^{n-1}(1+b)^{n-1}}{(1-ab)^{n-1}}. $$

This completes the proof of $s_2(2n, 2k) = Y(-1)$.

### 3.3 The case $d \ge 3$

Consider first the case when $d$ does not divide $k$. Again every edge lies in a free orbit under the action of rotation. Therefore, there are no graphs with $k$ edges that are fixed under rotation by $\frac{2\pi}{d}$. This agrees with the fact that in this case also $Y(\omega_d) = 0$.

Suppose now that $d|k$. Note that the edges of each graph counted by $s_d(n, k)$ are no longer than $d$. Those graphs that have no edges of length $d$ are in bijection with centrally symmetric graphs on $2n'$ vertices and $2k'$ edges via a map defined as in the proof of Lemma 2.4. On the other hand, the same map takes the graphs that have edges of length $d$ (those edges form a regular $n'$-gon) to centrally symmetric graphs on $2n'$ vertices and $2k' - 1$ edges. So,

$$ \begin{aligned} s_d(n, k) &= s_2(2n', 2k') + s_2(2n', 2k' - 1) \\ &= \sum_{j=0}^{k'} \binom{n' - 1}{k' - j} \binom{n' - 1}{j} \binom{n' + j - 2}{n' - 2} + \sum_{j=0}^{k' - 1} \binom{n' - 1}{k' - j - 1} \binom{n' - 1}{j + 1} \binom{n' + j - 1}{n' - 1} \\ &= \sum_{j=0}^{k'} \binom{n' - 1}{k' - j} \binom{n' - 1}{j} \binom{n' + j - 1}{n' - 1} = Y(\omega_d). \end{aligned} $$

This completes the proof of Theorem 1.2.

## 4 Final remarks

Recall that the definition of the cyclic sieving phenomenon asks for polynomials with nonnegative integer coefficients. For completeness, here we prove that our functions $X(q)$ and $Y(q)$ indeed have that property.

**Proposition 4.1.** $X(q), Y(q) \in \mathbb{N}[q]$.

**Proof:** To show that $X(q) \in \mathbb{Q}$, it suffices to show that $X(q)$ is a polynomial in $q$. Since all the roots of the numerator and the denominator of $X(q)$ are roots of unity, this follows from the fact that for each $d$-th primitive root of unity $\omega_d$, the order of the zero at $q = \omega_d$ is no smaller in the numerator than in the denominator. Namely, consider the expansion

$$ X(q) = \underbrace{\overbrace{[n]_q \cdots [n-k+2]_q}^{A}}_{C} \overbrace{\underbrace{[3n-2k-1]_q \cdots [2n-2k+1]_q}_{D}}^{B}. $$

The denominator has zero at $q = \omega_d$ with multiplicity $\lfloor \frac{k-1}{d} \rfloor + \lfloor \frac{n-k}{d} \rfloor$. A, and B have zero at $q = \omega_d$ with multiplicities at least $\lfloor \frac{k-1}{d} \rfloor$ and $\lfloor \frac{n-k-1}{d} \rfloor$, respectively. If $d$ does not divide $(n-k)$ then $\lfloor \frac{n-k-1}{d} \rfloor =$
$\lfloor \frac{n-k}{d} \rfloor$ and we are done. If $d$ divides $(n-k)$ but not $n$, then in fact $B$ has zero of order $\lfloor \frac{n-k}{d} \rfloor$. In the last case, when $d$ divides both $(n-k)$ and $n$, $A$ has in fact zeroof order $\lfloor \frac{k-1}{d} \rfloor = \lfloor \frac{k-1}{d} \rfloor + 1$.

It is well known that the $q$-binomial coefficients are polynomials with symmetric unimodal nonnegative integer coefficients. Hence, so is the product

$$ \begin{bmatrix} n \\ k-1 \end{bmatrix}_q \begin{bmatrix} 3n-2k-1 \\ n-k \end{bmatrix}_q. $$

The fact that $X(q) \in \mathbb{N}[q]$ now follows from [4, Proposition 10.1]. Similarly, one can show that each summand of $Y(q)$ is a polynomial with nonnegative integer coefficients. Namely, consider the expansion of the $j$-th term in the sum of $Y(q)$:

$$ \underbrace{\underbrace{\begin{bmatrix} n-1 \end{bmatrix}_q \cdots \begin{bmatrix} n-k+j \end{bmatrix}_q \begin{bmatrix} n-2-j \end{bmatrix}_q \cdots \begin{bmatrix} j+2 \end{bmatrix}_q}_{C} \underbrace{\underbrace{\begin{bmatrix} k-j \end{bmatrix}_q \cdots \begin{bmatrix} 1 \end{bmatrix}_q \begin{bmatrix} j \end{bmatrix}_q \cdots \begin{bmatrix} 1 \end{bmatrix}_q \begin{bmatrix} n-j-2 \end{bmatrix}_q \cdots \begin{bmatrix} 1 \end{bmatrix}_q}_{D} \underbrace{\underbrace{\begin{bmatrix} n \end{bmatrix}_q \begin{bmatrix} 3n-2k-1 \end{bmatrix}_q}_{E}}_{q} q^{j(j+n-k+2)}. $$

The denominator has zero at $q = \omega_d$ of order $\lfloor \frac{k-j}{d} \rfloor + \lfloor \frac{j}{d} \rfloor + \lfloor \frac{n-j-2}{d} \rfloor$, while the numerator has zero of order at least $\lfloor \frac{k-j}{d} \rfloor + \lfloor \frac{n-3}{d} \rfloor$. Note $\lfloor \frac{n-3}{d} \rfloor \ge \lfloor \frac{j}{d} \rfloor + \lfloor \frac{n-j-2}{d} \rfloor$ unless $d$ divides both $j$ and $(n-j-2)$. But in this case, $B$ has in fact a zero of order $\lfloor \frac{n-3}{d} \rfloor = \lfloor \frac{j}{d} \rfloor + \lfloor \frac{n-j-2}{d} \rfloor$. This proves that each summand in $Y(q)$ is in $\mathbb{Q}(q)$. The fact that it is in $\mathbb{N}[q]$ follows the same way as for $X(q)$. $\square$

Given that the polynomials $X(q)$ and $Y(q)$ are natural $q$-analogues of the cardinalities of the corresponding sets, a natural question to ask is whether they are generating functions for some statistics defined on these sets. To the best of the author's knowledge, such statistics have not been discovered. As suggested by Sagan [5, Section 12.3], if found, they could lead to a purely combinatorial proof of the cyclic sieving phenomenon.

## References

[1] S.-P. Eu and T.-S. Fu. The cyclic sieving phenomenon for faces of generalized cluster complexes. *Adv. in Appl. Math.*, 40:350–376, 2008.

[2] P. Flajolet and M. Noy. Analytic combinatorics of non-crossing configurations. *Discrete Math.*, 204:203–229, 1999.

[3] A. Guo. Cyclic sieving phenomenon in non-crossing connected graphs. *Electron. J. Combin.*, 18(1):P9, 2011.

[4] V. Reiner, D. Stanton, and Denis White. The cyclic sieving phenomenon. *J. Combin. Theory Ser. A*, 108:17–50, 2004.

[5] B. Sagan. The cyclic sieving phenomenon: a survey. *arXiv:1008.0790*, 2010.