Standard Solution & Scoring Details.

$f(x)=Cat_x=\dfrac{C_{2x}^x}{x+1}$，证明如下。（10 分）

设 $G=\{V,E\}$ 是一棵基环树，$V=\{1,2,\ldots,n\}$（$n$ 个结点），$E=\{i \to a_i|i \in V\}$（$i$ 号结点向 $a_i$ 号结点连边）。（20 分）

很明显，$G$ 应该有且只有一个环，并且这个环是自环。（30 分）

由于 $a_i\ge a_{i+1}$，对于满足前两个条件的 $\{a_n\}$，环的长度一定不大于 $2$，并且 $G$ 中一定有环。（40 分）

因此，只需要排除 $a_i=j,a_j=i\ (i \ne j)$ 的情况即可。（50 分）

设 $b_i=a_i-i$，则 $b_i>b_{i+1}$，$|b_i| \le n-1$，且存在 $x$ 使得 $b_x=0$，不存在 $x \ne y$ 使得 $b_x=y-x,b_y=x-y$。（60 分）

我们可以用一个 deque 构造 $\{b_n\}$：

• 先放入 $0$。
• 对于每个 $1 \le n-1$，讨论：
  • 是否在 deque 头部放入 $i$。
  • 是否在 deque 尾部放入 $-i$。
  • 如果都放入，是否会出现 $x \ne y$ 使得 $b_x=y-x,b_y=x-y$。（70 分）

设讨论 $i$ 轮后 deque 中共有 $j-1$ 个数。

我们发现：

• $i=0$ 时 $j=i=0$；
• $i=n-1$ 时 $j=i=n-1$；
• $i=j$ 时，如果第 $i+1$ 轮放入两个数，就会出现 $x \ne y$ 使得 $b_x=y-x,b_y=x-y$，因此最多只能放入一个数，该轮结束后 $i \ge j$；
• $i>j\ (i-1 \ge j)$ 时，第 $i+1$ 轮最多只能放入两个数该轮结束后 $i \ge j$。

综上，每轮结束后都有 $i \ge j$。（80 分）

设 $x=i-j$，$y$ 为 deque 中正数的个数与负数的个数之差，并且 $x,y$ 确定了一个二维平面上的点 $A(x,y)$，那么：

• $A$ 的初始坐标为 $(0,0)$；
• $n-1$ 轮讨论后 $A$ 的 $x$ 坐标仍为 $0$；
• 在任何一个时刻，$A$ 的 $x$ 坐标不小于 $0$；
• 每经过一轮讨论后，$A$ 的位移有四种情况：
  • $(x,y) \to (x-1,y)$；（向左）
  • $(x,y) \to (x+1,y)$；（向右）
  • $(x,y) \to (x,y+1)$；（向上）
  • $(x,y) \to (x,y-1)$；（向下）（90 分）

观察发现，$A$ 的 $n-1$ 次位移可以与 $n$ 个元素的入栈出栈操作序列（$2n$ 次操作）一一对应：

• 第一次操作一定是入栈；
• 最后一次操作一定是出栈；
• 剩下的 $2n-2$ 次操作中，一次位移对应两次操作：
  • 向右：入栈，入栈；
  • 向左：出栈，出栈；
  • 向上：入栈，出栈；
  • 向下：出栈，入栈。

很明显，$n$ 个元素的入栈出栈操作序列共有 $Cat_n=\dfrac{C_{2n}^n}{n+1}$ 个，故 $f(x)=Cat_x=\dfrac{C_{2x}^x}{x+1}$，命题得证。（100 分）