杂题记录：排列与三角函数
Published:
Alternating Permutation 计数
若一个长为 $n$ 的排列 $p$ 满足对于任意 $2 \le i \le n-1$ 都有以下两个条件中的一个：
- $p_{i-1} < p_i > p_{i+1}$
- $p_{i-1} > p_i < p_{i+1}$
则 $p$ 被称为一个 alternating permutation。
长为 $n$ 的 alternating permutation 个数记作 $Z_n$ A001250。
在 $O(n \log n)$ 的时间复杂度内求出 $Z_{1 \cdots n}$。一切运算在模 $998244353$ 下进行。
不难发现这个排列只可能是以下两种情况之一：
- $p_1 < p_2 > p_3 < \cdots$
- $p_1 > p_2 < p_3 > \cdots$
不难发现这两种的方案数相等，只要把 $1 < \cdots < n$ 的偏序反过来即可构造出双射。
WLOG，不妨设第一个是小于号。设此时的方案数为 $A_n$ A000111。
我们枚举 $1$ 填在哪里，可得
\[A_n = \sum_{i \text{ odd}} \binom {n-1} i A_i A_{n-1-i}\]枚举 $n$ 填在哪里，又可得
\[A_n = \sum_{i \text{ even}} \binom {n-1} i A_i A_{n-1-i}\]合起来
\[A_n = \frac 1 2 \sum_{i=0}^{n-1} \binom {n-1} i A_i A_{n-1-i}\]写得好看一点：
\[A_{n+1} = \begin{cases} 1 & n = 0 \\ \frac 1 2 \sum_{i=0}^n \binom n i A_i A_{n-i} & n \ge 1 \\ \end{cases}\] \[\boxed{ A_{n+1} = \frac 1 2 \left( \sum_{i=0}^n \binom n i A_i A_{n-i} + [n=0] \right) }\]（注意 $A_0 = 1$）
我们设 $A$ 的 EGF 为 $\mathbf A$，则可以表示为：
\[\mathbf A'(x) = \frac {\mathbf A(x)^2 + 1} 2\] \[\begin{aligned} \int \frac 1 {\mathbf A(x)^2 + 1} \mathbf A'(x) dx &= \int \frac 1 2 dx \\ \arctan \mathbf A(x) &= \frac x 2 + C \\ \mathbf A(x) &= \tan\left( \frac x 2 + C \right) \\ \end{aligned}\]边界 $\mathbf A(0) = A_0 = 1$，不妨取 $C = \frac \pi 4$：
\[\mathbf A(x) = \tan\left( \frac x 2 + \frac \pi 4 \right)\]做奇偶函数分解：
\[\boxed{ \mathbf A(x) = \tan x + \sec x }\]考虑到它们可以被 $e^{ix}$ 和 $e^{-ix}$ 简单表示出，因此只需要多项式求逆就行了，时间复杂度 $O(n \log n)$。
$Z$ 可以被简单地用 $A$ 表示：
\[Z_n = \begin{cases} 1 & n \in \{0, 1\} \\ 2 A_n & n \ge 2 \\ \end{cases}\]其 EGF 为（注意 OEIS 此处有误！）：
\[\mathbf Z(x) = 2 (\tan x + \sec x) - x - 1\]其它结论
由于刚才的奇偶函数拆分，我们顺便知道了 $\tan$ 和 $\sec$ 的 Maclaurin 展开：
\[\tan x = A_1 x + A_3 \frac {x^3} {3!} + A_5 \frac {x^5} {5!} + \cdots\] \[\sec x = A_0 + A_2 \frac {x^2} {2!} + A_4 \frac {x^4} {4!} + \cdots\]这么看来 $\tan$ 和 $\sec$ 真是一对苦命鸳鸯啊。
References
- OEIS
- $Z$ https://oeis.org/A001250
- $A$ https://oeis.org/A000111
- 题目来源
- OI Wiki 关于 Entringer 数的介绍