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

Question

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<c<b<d.$$

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 $$

Answer 1

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.