# Cyclic sieving phenomenon in non-crossing connected graphs

Alan Guo†

Department of Mathematics, Duke University, Durham, NC, USA

**Abstract.** A non-crossing connected graph is a connected graph on vertices arranged in a circle such that its edges do not cross. The count for such graphs can be made naturally into a $q$-binomial generating function. We prove that this generating function exhibits the cyclic sieving phenomenon, as conjectured by S.-P. Eu.

**Résumé.** Un graphe connexe dont les sommets sont disposés sur un cercle est sans croisement si ses arêtes ne se croisent pas. Nous démontrons une conjecture de S.-P. Eu affirmant que la fonction génératrice $q$-binomiale dénombrant de tels graphes exhibe le phénomène du crible cyclique.

**Keywords:** cyclic sieving phenomenon, non-crossing connected graphs, Lagrange inversion

## 1 Introduction

A non-crossing graph on a finite set $S$ is a graph with vertices indexed by $S$ arranged in a circle such that no edges cross. When we say a graph on $n$ vertices, we will mean $S = \{1, \dots, n\}$. In [3], Flajolet and Noy showed that the number $c_{n,k}$ of non-crossing connected graphs (see Figure 1) on $n$ vertices with $k$ edges, $n-1 \le k \le 2n-3$, is

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

Define

$$\begin{bmatrix} n \\ k \end{bmatrix}_q = \frac{[n]!_q}{[k]!_q [n-k]!_q}$$

where $[n]!_q = [n]_q[n-1]_q \cdots [1]_q$ and $[n]_q = 1 + q + \cdots + q^{n-1} = \frac{1-q^n}{1-q}$. The formula in (1) admits a natural $q$-analogue:

$$c(n, k; q) = \frac{1}{[n-1]_q} \begin{bmatrix} 3n-3 \\ n+k \end{bmatrix}_q \begin{bmatrix} k-1 \\ n-2 \end{bmatrix}_q. \qquad (2)$$

It is straightforward to verify that $c(n, k; q)$ is a polynomial in $q$ with nonnegative integer coefficients. The main result of this paper is the following, which was conjectured by S.-P. Eu [1].

<footnote>†alan.guo@duke.edu</footnote>
<figure><img src="image_1.png" /><figcaption>Fig. 1: A non-crossing connected graph on 12 vertices with 14 edges</figcaption></figure>

**Theorem 1.1.** Let $n \ge 1$ and $n-1 \le k \le 2n-3$, and let $X$ be the set of non-crossing connected graphs on $n$ vertices with $k$ edges. If $d \ge 1$ divides $n$ and $\omega$ is a primitive $d$-th root of unity, then

$$c(n, k; \omega) = s_d(n, k)$$

where we define

$$s_d(n, k) = \# \left\{ x \in X : x \text{ is fixed under rotation by } \frac{2\pi}{d} \right\}.$$

In [5], Reiner, Stanton, and White introduced the notion of the cyclic sieving phenomenon. A triple $(X, X(q), C)$ consisting of a finite set $X$, a polynomial $X(q) \in \mathbb{N}[q]$ satisfying $X(1) = |X|$, and a cyclic group $C$ acting on $X$ exhibits the *cyclic sieving phenomenon* if, for every $c \in C$, if $\omega$ is a primitive root of unity of the same multiplicative order as $c$, then

$$X(\omega) = \#\{x \in X : c(x) = x\}.$$

In (1), the two extreme cases, $k = n-1$ and $k = 2n-3$, correspond to non-crossing spanning trees and $n$-gon triangulations respectively. In the former case, Eu and Fu showed in [2] that quadrangulations of a polygon exhibit the cyclic sieving phenomenon, where the cyclic action is cyclic rotation of the polygon, and they showed a bijection between quadrangulations of a $2n$-gon with non-crossing spanning trees on $n$ vertices. The bijection mapping is as follows: given a non-crossing spanning tree on $n$ vertices, for each edge connecting $i$ to $j$, draw a dotted line from $2i-1$ to $2j-1$ in a $2n$-gon. Then the quadrangulation of this $2n$-gon is defined by quadrangles whose diagonals are the dotted lines; conversely, given a $2n$-gon, every quadrangle has a diagonal whose endpoints are odd numbers, so we may perform the reverse procedure to get an inverse mapping (see Figure 2). This bijection preserves the cyclic sieving phenomenon, since rotation by $\frac{2\pi}{n}$ in the tree corresponds to rotation by $\frac{\pi}{n}$ in the $2n$-gon.

In the latter case, Reiner, Stanton, and White showed in [5] that polygon dissections of a polygon exhibit the cyclic sieving phenomenon where the cyclic action is also rotation. In particular, triangulations acted upon by rotations exhibit the cyclic sieving phenomenon. These results inspired Eu to conjecture Theorem 1.1, which we prove in the following sections. The case $d=1$ in Theorem 1.1 follows from (1).
<figure><img src="image_2.png" /><figcaption>Fig. 2: Bijection between a spanning tree on a 5 vertices and a quadrangulation of a 10-gon.</figcaption></figure>

We therefore consider the following three cases: $d = 2$ and $k$ is odd, $d = 2$ and $k$ is even, and $d \ge 3$. The majority of the work is done in the proofs of the case where $d = 2$, and we show that the case where $d \ge 3$ reduces to this case.

## 2 Lagrange Inversion Theorem

In the following sections, we will use the Lagrange Inversion Theorem to extract coefficients of certain generating functions. If $\phi(z) \in \mathbb{Q}[[z]]$, then we define $[z^n]\phi(z)$ to be the coefficient of $z^n$ in $\phi(z)$.

**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}[[z]]$ satisfy $y = z\phi(y)$. Then, for an arbitrary series $\psi$, the coefficient of $z^n$ in $\phi(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.

We begin by illustrating how Flajolet and Noy used Lagrange inversion to find (1). Let $C(z, w)$ be the generating function for $c_{n,k}$, that is,

$$C(z, w) = \sum_{n,k} c_{n,k} z^n w^k.$$

Then it can be shown using a combinatorial argument that $C$ satisfies

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

Setting $C = z + zy$, this becomes

$$wz(1 + y)^3 = y(1 - wy)$$

which can be put in the Lagrange form

$$y = z \frac{w(1 + y)^3}{1 - wy}. \qquad (3)$$
The result (1) then follows upon application of Lagrange inversion on $y$. We will in fact use this same function $y$ multiple times in our proofs.

### 3 The case where $d = 2$ and $k$ is odd

In this section, we prove that Theorem 1.1 holds when $d = 2$ and $k$ is odd. Recall that $d$ divides $n$, so $n$ must be even in this case. The case where $n = 2$ is trivial since there is only 1 non-crossing connected graph on 2 vertices, so we may assume that $n > 2$. For this section, define $n' = \frac{n}{2}$ and $k' = \frac{k+1}{2}$. It is a straightforward computation to verify that

$$c(n, k; -1) = \binom{3n' - 2}{n' + k' - 1} \binom{k' - 1}{n' - 1}. \qquad (4)$$

The goal of this section is to show that $s_2(n, k) = c(n, k, -1)$, and we do this by showing that both sides satisfy the same recurrence and initial conditions.

Recall that $c_{n,k} = |X|$. Define $d_{n,k}$ to be the number of non-crossing graphs on $\{1, \dots, n\}$ with $k$ edges and exactly two connected components such that 1 and $n$ are in different components.

**Lemma 3.1.** With $d_{n,k}$ defined above, we have

$$d_{n,k} = \frac{2}{n-2} \binom{3n-5}{n+k} \binom{k-1}{n-3}.$$

*Proof.* Let $D(z, w) = \sum d_{n,k} z^n w^k$ and let $C(z, w) = \sum c_{n,k} z^n w^k$. Since $d_{n,k}$ counts graphs with two connected components, which are each counted by $c_{n,k}$, we therefore have $D = C^2$. To find the coefficient of $z^n w^k$, we use Lagrange inversion. Recall from (3) that $y = z^{\frac{w(1+y)^3}{1-wy}}$. But $D = C^2 = z^2 + z^2(y^2+2y)$. Therefore

$$[z^n w^k]D = [z^{n-2} w^k]y^2 + 2[z^{n-2} w^k]y.$$

Computing each of these separately, we have

$$\begin{align*} [z^{n-2} w^k] y &= \frac{1}{n-2} [u^{n-3} w^k] \frac{w^{n-2} (1+u)^{3n-6}}{(1-uw)^{n-2}} \\ &= \frac{1}{n-2} \binom{3n-6}{n+k-1} \binom{k-1}{n-3} \end{align*}$$

and

$$\begin{align*} [z^{n-2} w^k] y^2 &= \frac{2}{n-2} [u^{n-4} w^k] \frac{w^{n-2} (1+u)^{3n-6}}{(1-uw)^{n-2}} \\ &= \frac{2}{n-2} \binom{3n-6}{n+k} \binom{k-1}{n-3}. \end{align*}$$

The result then follows from Pascal's identity. $\square$

<figure><img src="image_3.png" /></figure>

We define some more notation. Define

$$f_{n,k} = \#\{x \in X : x \text{ has an edge from 1 to } n\}.$$
**Lemma 3.2.** With $f_{n,k}$ defined as above, we have

$$s_2(n, k) = n' \cdot f_{n'+1, k'}.$$

*Proof.* Given a centrally symmetric graph with an odd number of edges, exactly one of the edges must be a diameter. There are $n'$ choices for the diameter. Once a diameter has been fixed, the remaining $k-1$ edges are determined by the $k' - 1$ edges on either side of the diameter. Without loss of generality, assume

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** The bijection between centrally symmetric $n$-vertex, $k$-edge graph with fixed diameter and $(\frac{n}{2} + 1)$-vertex, $\frac{k+1}{2}$-edge graph with edge between 1 and $\frac{n}{2} + 1$.</figcaption></figure>

the diameter has endpoints 1 and $n' + 1$. Then we have a bijection (see Figure 3) between the graphs we wish to count and graphs on $\{1, \dots, n' + 1\}$ with $k'$ edges including the edge from 1 to $n' + 1$. This is counted by $f_{n'+1,k'}$. $\square$

**Lemma 3.3.** The sequence $f_{n,k}$ satisfies the recurrence

$$f_{n,k} + f_{n,k+1} = c_{n,k} + d_{n,k}$$

with the base case

$$f_{n,2n-3} = c_{n,2n-3} = \frac{1}{n-1} \binom{2n-4}{n-2}.$$

*Proof.* The base case follows from the fact that every triangulation must contain the edge from 1 to $n$. Now consider a non-crossing connected graph with $k+1$ edges on $\{1, \dots, n\}$ with the edge 1 to $n$. We have two cases. When we remove this edge, either the remaining graph is connected or not. If the remaining graph is connected, then we have a non-crossing connected graph with $k$ edges without the edge from 1 to $n$. This is counted by $c_{n,k} - f_{n,k}$. If the remaining graph is not connected, then there are exactly two connected components, and 1 and $n$ lie in separate components. This is counted by $d_{n,k}$. Hence

$$f_{n,k+1} = c_{n,k} + d_{n,k} - f_{n,k}.$$

$\square$
As a corollary to this lemma, it follows that one has the recurrence

$$s_2(2n-2, 2k-1) + s_2(2n-2, 2k+1) = (n-1)c_{n,k} + (n-1)d_{n,k} \quad (5)$$

with base case

$$s_2(2n-2, 4n-7) = (n-1)c_{n,2n-3} = \binom{2n-4}{n-2}.$$

To show that $c(n, k; -1) = s_2(n, k)$ for even $n$ and odd $k$ or, equivalently, $c(2n - 2, 2k - 1; -1) = s_2(2n - 2, 2k - 1)$ for any positive integers $n > 2$ and $n - 1 \le k \le 2n - 3$, it suffices to show that $c(2n - 2, 2k - 1; -1)$ satisfies the same recurrence (5) as $s_2(2n - 2, 2k - 1)$. The base case is immediate:

$$c(2n - 2, 4n - 7; -1) = \binom{3n - 5}{3n - 5} \binom{2n - 4}{n - 2} = \binom{2n - 4}{n - 2}.$$

We now show that $c(2n - 2, 2k - 1; -1)$ satisfies the recurrence relation as well, which completes the proof that the theorem holds for $d = 2$ and odd $k$.

**Proposition 3.4.** $c(2n - 2, 2k - 1; -1)$ satisfies

$$c(2n - 2, 2k - 1; -1) + c(2n - 2, 2k + 1; -1) = (n - 1)c_{n,k} + (n - 1)d_{n,k}.$$

*Proof.* From (4), we see that all we need to verify is

$$\binom{3n-5}{n+k-2} \binom{k-1}{n-2} + \binom{3n-5}{n+k-1} \binom{k}{n-2} = \binom{3n-3}{n+k} \binom{k-1}{n-2} + \frac{2n-2}{n-2} \binom{3n-5}{n+k} \binom{k-1}{n-3},$$

which we leave as a straightforward exercise for the reader. $\square$

# 4 The case where $d = 2$ and $k$ is even

In this section, we prove that Theorem 1.1 holds when $d = 2$ and $k$ is even. As in the previous case, it is again a straightforward computation to verify that

$$c(n, k; -1) = \binom{\frac{3n-4}{2}}{\frac{n+k}{2}} \binom{\frac{k-2}{2}}{\frac{n-2}{2}}.$$

Let $a_{2n,k}$ denote the number of non-crossing connected graphs with $2n$ vertices and $k$ pairs of antipodal edges, where a diameter counts as one pair. When counting $a_{2n,k}$, we have two cases. In one case, there is a diameter, and in the second case, there is not. This gives us the sum

$$a_{2n,k} = s_2(2n, 2k-1) + s_2(2n, 2k) = c(2n, 2k-1; -1) + s_2(2n, 2k).$$

where the second equality follows from our results in the previous section. Our goal in this section is to show that $s_2(2n, 2k) = c(2n, 2k; -1)$, so it suffices to show that

$$a_{2n,k} = c(2n, 2k-1; -1) + c(2n, 2k; -1) = \binom{3n-1}{n+k} \binom{k-1}{n-1}. \quad (6)$$

Let $F$ be the generating function for $f_{n,k}$, i.e. $F(z, w) = \sum f_{n,k} z^n w^k$. Similarly, let $A(z, w) = \sum a_{2n,k} z^n w^k$. Our strategy in this section is to use the Lagrange Inversion Theorem on $A(z, w)$ to obtain (6).
**Lemma 4.1.**

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

where $v_{m+1} = v_1 + n$.

*Proof.* Consider a non-crossing connected graph with $2n$ vertices and $k$ pairs of antipodal edges. There exists a unique positive integer $m$ such that the center of the $2n$-gon lies inside a $2m$-gon formed by edges of the graph and such that no other edges lie inside the $2m$-gon. This $m$ is at most $n$. Now, exactly $m$ of the vertices of this $2m$-gon, call them $v_1 < \cdots < v_m$, lie in the set $\{1, \dots, n\}$ due to the antipodal condition on the edges. All edges not used in the $2m$-gon lie outside of it (see Figure 4). The $(m+1)$-th

<figure><img src="image_5.png" /><figcaption>**Fig. 4:** A graph with an inner $2m$-gon, where $m = 4$.</figcaption></figure>

vertex is antipodal to $v_1$, hence $v_{m+1} = v_1 + n$. For each $i$, there is an edge from $v_i$ to $v_{i+1}$ and $k_i - 1$ other edges on the vertices $\{v_i, v_i + 1, \dots, v_{i+1}\}$, such that $k_1 + \cdots + k_m = k$. Such a graph is counted by $f_{v_{i+1}-v_i+1, k_i}$. Thus we get the corresponding sum. $\square$

**Lemma 4.2.** With A and F as defined above, we have

$$\frac{A}{z} = \frac{\partial(F/z)/\partial z}{1 - F/z}.$$

*Proof.* We show that

$$a_{2n,k} = \sum_{m=1}^{n} \sum_{k_1+\cdots+k_m=k} \sum_{n_1+\cdots+n_m=n+m} (n_m-1)f_{n_m,k_m} \prod_{i=1}^{m-1} f_{n_i,k_i}.$$

In the sum in the previous lemma, the term $\prod_{i=1}^{m} f_{v_{i+1}-v_i+1, k_i}$ is counted multiple times with the product written in this order. We show that it is counted exactly $n + v_1 - v_m$ times. Consider any $m$-element
subset {$v_1, \dots, v_m$} $\subseteq$ {$1, \dots, n$} with $v_1 < \dots < v_m$. For $j = 1, \dots, v_1 - 1$, this subset yields the same summand as {$v_1 - j, \dots, v_m - j$}. Therefore, we can identify any subset {$v_1, \dots, v_m$} with {$1, \dots, v_m - v_1 + 1$}. There are exactly $n + v_1 - v_m$ subsets corresponding to this one, each with largest element $v_m - v_1 + 1, v_m - v_1 + 2, \dots, n$. This proves the sum identity above.

For the equality of generating functions, we insert variables into the above identity:

$$a_{2n,k} z^n w^k = \frac{1}{z^{m-2}} \sum_{m=1}^{n} \sum_{k_1+\dots+k_m=k} \sum_{n_1+\dots+n_m=n+m} (n_m-1) f_{n_m,k_m} z^{n_m-2} w^{k_m} \prod_{i=1}^{m-1} f_{n_i,k_i} z^{n_i} w^{k_i} \quad (7)$$

We note that

$$\frac{\partial(F/z)}{\partial z} = \sum_{n,k} (n-1) f_{n,k} z^{n-2} w^k$$

so, summing over all $n$ and $k$ in (7), we get

$$A = \frac{\partial(F/z)}{\partial z} \left( z + F + \frac{F^2}{z} + \frac{F^3}{z^2} + \dots \right) = z \frac{\partial(F/z)}{\partial z} \left( \frac{1}{1-F/z} \right). \quad \square$$

**Proposition 4.3.**

$$a_{2n,k} = \binom{3n-1}{n+k} \binom{k-1}{n-1}.$$

*Proof.* Let $H = F/z$ and let $C$ be the generating function for $c_{n,k}$ as in the previous section and let $C = z + zy$. From the recurrence $f_{n,k} + f_{n,k+1} = d_{n,k} + c_{n,k}$, $n \ge 2$, and $f_{1,k} = 0$, we have

$$\left(1 + \frac{1}{w}\right) F = D + C - z = z^2(1 + y)^2 + zy.$$

Therefore, after some substitution and simplification, applying the identity in (3), we get

$$1 - H = \frac{1}{1 + y}.$$

From

$$\frac{A}{z} = \frac{\partial H / \partial z}{1 - H}$$

we get

$$\int \frac{A}{z} dz = \int \frac{dH}{1 - H}$$

or equivalently

$$\sum_{n,k} \frac{1}{n} a_{2n,k} z^n w^k = - \log(1 - H) = \log(1 + y).$$
By the Lagrange inversion formula,

$$ 
\begin{aligned}
\frac{1}{n} a_{2n,k} &= [z^n w^k] \int \frac{A}{z} dz \\
&= [z^n w^k] \log(1+y) \\
&= \frac{1}{n} [u^{n-1} w^k] \frac{w^n (1+u)^{3n}}{(1-uw)^n} \frac{1}{1+u} \\
&= \frac{1}{n} \binom{3n-1}{n+k} \binom{k-1}{n-1}
\end{aligned}
$$

whence our desired result.

<figure><img src="image_6.png" /></figure>

Comparing with (6) shows that Theorem 1.1 holds when $d = 2$ and $k$ is even.

# 5 The case where $d \ge 3$

Finally, in this section, we prove that Theorem 1.1 holds when $d \ge 3$. For this section, define $n'' = \frac{n}{d}$ and $k'' = \frac{k}{d}$. Again, it is a straightforward computation to verify that if $d|k$, then

$$ c(n, k; \omega) = \binom{3n'' - 1}{n'' + k''} \binom{k'' - 1}{n'' - 1}. $$

**Lemma 5.1.** If $d \ge 3$ does not divide $k$, then $c(n, k; \omega) = 0$, where $\omega$ is a primitive $d$-th root of unity.

If $d$ does not divide $k$, then in fact there are no graphs with $k$ edges that are fixed under rotation by $\frac{2\pi}{d}$, since each edge lies in a free orbit under the action of rotation. We henceforth assume that $d|k$.

**Lemma 5.2.**

$$ s_d(n, k) = n'' \cdot f_{n''+1, k''} + s_2(2n'', 2k''). $$

*Proof.* For a non-crossing connected graph on $\{1, \dots, n\}$ fixed under rotation by $\frac{2\pi}{d}$, then there are two cases: either the edges form a central $d$-gon or not. In the former case, every edge is purely determined by the edges on the first $n'' + 1$ vertices. In fact, there is bijection between such graphs and non-crossing connected graphs on $n'' + 1$ vertices with the edge from 1 to $n'' + 1$. There are $f_{n''+1, k''}$ such graphs, and there are $n''$ possible $d$-gons. In the latter case, the edges are determined by edges on the first $2n''$ vertices. We construct a bijection between such graphs and centrally symmetric non-crossing connected graphs on $2n''$ vertices with $2k''$ edges as follows (see Figure 5): Going around clockwise in the graph, label the first $m$ vertices $1_1, 2_1, \dots, n_1''$, label the next set of vertices $1_2, 2_2, \dots, n_2''$, and so on. Construct a non-crossing graph with $2n''$ vertices labeled $1_1, 2_1, \dots, n_1'', 1_2, 2_2, \dots, n_2''$. For each edge from $i$ to $j$ in the original graph, we put an edge with the same endpoints in the new graph. Finally, if there is an edge from some $i_2$ to some $j_3$, we put an edge from $i_2$ to $j_1$ in the new graph. This new graph therefore has $2k''$ edges. It is straightforward to check that this is a bijection. $\square$

**Proposition 5.3.** For $d \ge 3$ and $\omega$ a primitive $d$-th root of unity,

$$ c(n, k; \omega) = s_d(n, k). $$
<figure><img src="image_7.png" /><figcaption>Fig. 5: The bijective construction when $(n, k, d) = (12, 12, 3)$</figcaption></figure>

*Proof.* This follows by the previous lemma and our results from the case where $d = 2$, after applying Pascal's rule. □

This completes the proof of Theorem 1.1.

## Acknowledgements

This paper is extracted nearly verbatim from parts of [4]. This research was carried out in a summer REU at the University of Minnesota, mentored by Vic Reiner and Dennis Stanton, and financially supported by NSF grant DMS-1001933. The author thanks Vic Reiner and Dennis Stanton for introducing him to this fascinating problem, as well as for their guidance, support, and countless insightful comments and suggestions. The author also thanks Jia Huang for carefully reading drafts of this paper and for his helpful suggestions.

## References

[1] S.-P. Eu, personal communication to V. Reiner and D. Stanton, April 2006.

[2] S.-P. Eu, T.-S. Fu, The cyclic sieving phenomenon for faces of generalized cluster complexes, *Adv. in Appl. Math.* **40** (2008), no. 3, 350–376.

[3] P. Flajolet, M. Noy, Analytic combinatorics of non-crossing configurations, *Discrete Mathematics* **204** (1999), no. 1-3, 203–229.

[4] A. Guo, Cyclic sieving phenomenon in non-crossing connected graphs, *Electronic Journal of Combinatorics* **18**, (2011), #P9.

[5] V. Reiner, D. Stanton, D. White, The cyclic sieving phenomenon, *J. Combin. Theory Ser. A* **108** (2004), 17–50.