Xrfgtjtk

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 nright]_q $$

Let $defncm{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 $yequiv x+ipmod{2n}$ for some $0le 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 $iin S$, and is an arrow $leftarrow$ pointing counterclockwise if $inotin 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.