专栏文章

你的排列怎么尖尖的

ddanielqf
算法·理论参与者 8已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@mjyjumfq
此快照首次捕获于
2026/01/04 01:01
2 个月前
此快照最后确认于
2026/02/19 01:23
14 小时前
查看原文
来自 gdkoi 2026 day2 E，但本蒟蒻肯定是做不出来的，本文是在讨论一个超级弱化版。
定义一个长度为 nn 的排列 pp 为尖尖的当且仅当
∀1<i<n,(pi−pi−1)(pi−pi+1)>0\forall 1 < i < n,(p_i-p_{i-1})(p_i-p_{i+1})>0
即所有数（头尾除外）要么比左右两边的数都要大，要么比左右两边的数都要小。
注：这里的定义和原题略有不同，没有加上“反排列”。
那么如何求长度为 nn 的尖尖的排列个数？
首先如果给每对相邻的数之间填上小于号或大于号，那么小于号和大于号是交错排列的，于是我们为方便起见记 fnf_n 为第一个符号为小于号的方案数。
枚举 1 的位置可以得到如下递推式：
f0=1f1=1fn=∑1≤i≤n∧i mod 2=1(n−1i−1)fi−1fn−i(n≥2)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)
但是 ii 取奇数不方便化简，再来考虑从 nn 的位置角度切入，得到一个 ii 取偶数位置的式子：
fn=∑1≤i≤n∧i mod 2=0(n−1i−1)fi−1fn−if_n=\sum_{1\le i\le n\land i\bmod2=0}\binom{n-1}{i-1}f_{i-1}f_{n-i}
两式相加乘 12\frac12 得：
fn=12∑1≤i≤n(n−1i−1)fi−1fn−if_n=\frac12\sum_{1\le i\le n}\binom{n-1}{i-1}f_{i-1}f_{n-i}
尝试凑出生成函数：
fn(n−1)!xn−1=12∑1≤i≤nfi−1(i−1)!xi−1fn−i(n−i)!xn−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}
fnf_n 与 (n−1)!(n-1)! 不齐，陷入停滞。
发呆许久后发现是求导
(fnn!xn)′=fn(n−1)!xn−1\left(\frac{f_n}{n!}x^n\right)'=\frac{f_n}{(n-1)!}x^{n-1}
然后就能凑了
F^(x):=∑i≥0fixiF^′(x)=12(F^(x)2+1)\hat F(x):=\sum_{i\ge0}f_ix^i\\ \hat F'(x)=\frac12(\hat F(x)^2+1)
不会解这个微分方程，再度陷入停滞（顺带一提我第一次推时漏了常数项导致检查了很久）。
赛后 wolfram alpha：
求作者心理的阴影面积。

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...