你的排列怎么尖尖的
danielqf
·
·
算法·理论
来自 gdkoi 2026 day2 E，但本蒟蒻肯定是做不出来的，本文是在讨论一个超级弱化版。
定义一个长度为 n 的排列 p 为尖尖的当且仅当
\forall 1 < i < n,(p_i-p_{i-1})(p_i-p_{i+1})>0
即所有数（头尾除外）要么比左右两边的数都要大，要么比左右两边的数都要小。
注：这里的定义和原题略有不同，没有加上“反排列”。
那么如何求长度为 n 的尖尖的排列个数？
首先如果给每对相邻的数之间填上小于号或大于号，那么小于号和大于号是交错排列的，于是我们为方便起见记 f_n 为第一个符号为小于号的方案数。
枚举 1 的位置可以得到如下递推式：
f_0=1\\
f_1=1\\
f_n=\sum_{1\le i\le n\land i\bmod2=1}\binom{n-1}{i-1}f_{i-1}f_{n-i}\quad(n\ge2)
但是 i 取奇数不方便化简，再来考虑从 n 的位置角度切入，得到一个 i 取偶数位置的式子：
f_n=\sum_{1\le i\le n\land i\bmod2=0}\binom{n-1}{i-1}f_{i-1}f_{n-i}
两式相加乘 \frac12 得：
f_n=\frac12\sum_{1\le i\le n}\binom{n-1}{i-1}f_{i-1}f_{n-i}
尝试凑出生成函数：
\frac{f_n}{(n-1)!}x^{n-1}=\frac12\sum_{1\le i\le n}\frac{f_{i-1}}{(i-1)!}x^{i-1}\frac{f_{n-i}}{(n-i)!}x^{n-i}
发呆许久后发现是求导
$$
\left(\frac{f_n}{n!}x^n\right)'=\frac{f_n}{(n-1)!}x^{n-1}
$$
然后就能凑了
$$
\hat F(x):=\sum_{i\ge0}f_ix^i\\
\hat F'(x)=\frac12(\hat F(x)^2+1)
$$
不会解这个微分方程，再度陷入停滞（顺带一提我第一次推时漏了常数项导致检查了很久）。
赛后 wolfram alpha：
求作者心理的阴影面积。