# Computing fixpoints of noncrossing matchings of $2n$ points under rotation.

For a definition of the cyclic sieving phenomena, see "The cyclic sieving phenomenon: a survey", by B. Sagan.

A matching of $$[2n] = \{1,2,\dots, 2n \}$$ is a graph with vertex set $$[2n]$$ and with $$n$$ non-incident edges. A matching is noncrossing if there are no edges $$ab$$ and $$cd$$ such that

$$a

We denote the set of noncrossing matchings on $$2n$$ points by $$\text{NCM}(2n)$$

The cyclic group of order $$2n$$ has a natural group action on $$\text{NCM}(2n)$$ by rotation, see the picture from Sagan's survey: rotation of noncrossing matchings.

I have seen several sources saying that the triple $$(\text{NCM}(2n), C_{2n}, \text{Cat}_n(q))$$ exhibits the cyclic sieving phenomena but I have not seen a proof of this fact anywhere. I know how to evaluate $$\text{Cat}_n(q)$$ in $$2n$$:th roots of unity but I cannot figure out how to compute the fixpoints of $$\text{NCM}(2n)$$ under some rotation.

Either an explanation of how to compute the fixpoints under some rotation or a link to some proof of this fact would be much appreciated!

EDIT: As was pointed out in the comments, the $$q$$-Catalan numbers can refer to more than one family of polynomials. The one that we are using, in this case, is indeed

$$\text{Cat}_n(q)=\frac{1}{[1+n]_q}\left[2n \atop n\right]_q$$

• Based on mathoverflow.net/questions/128891/…, there are multiple $q$-analogs of the Catalan numbers, so can you define $\text{Cat}_n(q)$? – Mike Earnest Sep 11 '18 at 15:08
• @MikeEarnest In this case $\text{Cat}_n(q) = \frac{1}{[n+1]_q} \left[2n \atop n\right]_q$. – Misha Lavrov Sep 11 '18 at 15:12

Let $\def\ncm{\operatorname{NCM}}\ncm_k$ be the set of noncrossing matchings on $[2n]$ which are invariant under rotation by $k$. Whenever $k<2n$ is a divisor of $2n$, I claim that $$|\!\ncm_k(2n)|=\binom{k}{k/2}.$$

Consider a $k$-rotationally invariant noncrossing partition. An important initial observation is that every element is matched to one which is less than $k$ places to its right or less than $k$ places to its left. We will say that a the left endpoint of a matched pair $(x,y)$ is $x$ if $y\equiv x+i\pmod{2n}$ for some $0\le i <k$. We will in fact show that for every subset $S$ of $[k]$ of size $k/2$, there is exactly one element of $\ncm_k(2n)$ where every element in $S$ is a left endpoint.

Here is the correspondence between subsets of $k$ of size $k/2$ and $\ncm_k(2n)$. Given such a subset, $S$, consider a circle of $k$ symbols, where the $i^{th}$ symbol is an arrow $\rightarrow$ pointing clockwise if $i\in S$, and is an arrow $\leftarrow$ pointing counterclockwise if $i\notin S$. There will exist a $\rightarrow$ which is followed clockwise by a $\leftarrow$, so that the arrows are pointing to each other. If the $\rightarrow$ is the $i^{th}$ symbol, then $i$ and $i+1$ are matched to each other (and therefore, $i+mk$ is matched to $i+1+mk$ for all $m$). Now, delete these matching arrows to make a smaller circle, and repeat this process until all elements of $[k]$ (and therefore of $[2n]$) are matched.

Here is an example when $k=12$ and $S=\{1,4,5,9,10,12\}$.

Circular arrow drawing:

$\begin{array}{cccccc} 1& & 2 & 3 & &4 \\ & \nearrow &\leftarrow & \leftarrow & \searrow & \\ 12 & \uparrow & & & \downarrow & 5\\ 11 & \downarrow & & & \uparrow & 6\\ & \nwarrow &\leftarrow & \rightarrow & \nearrow & \\ 10& & 9 & 8 & &7 \end{array}$

Resulting matching:

─────────────────────┐  ┌──────────
──────┐  ┌────────┐  │  │        ┌
┌──┐  │  │  ┌──┐  │  │  │   ┌──┐ │
1  2  3  4  5  6  7  8  9  10 11 12


The above picture must be extended periodically to all of $[2n]$, by placing $2n/12$ copies in a circle. Note that $12$ is matched to $12+3=15$ and $9$ is matched to $8+12=20$, while $3$ is matched to $2n$ and $8$ is matched to $2n-3$.

I leave it to you to verify that this construction is does indeed uniquely represent each element of $\ncm_k(2n)$ as a subset of $k/2$ elements of $[k]$, and that this count agrees with $\text{Cat}_n(\omega)$ where $\omega$ is an appropriate root of unity.

• Nice! This does however not work when $k$ is odd. But this can only happen when $n=k$ is odd, in which case there must be a diagonal $D$ between some point $i$ and $i+n$. We can choose $D$ in $k$ ways and the edges in $\text{Cat}_n$ ways, since $D$ cuts the remaining points into two halves and choosing one halve determines the other. We thus obtain $k \cdot \text{Cat}_n=\binom{k}{\frac{k+1}{2}} = \text{Cat}_n(-1)$. – Joakim Uhlin Sep 11 '18 at 20:10