P12394 「RiOI-6」神曲 / 组合意义证明 最后更新于 2025-05-01 21:44:23

赛时想法。字母记号与题面的不同，令 $n$ 为区间个数，$m$ 为值域。 ---- 考虑设 $l_{n+1}=0,r_{n+1}=\infty$ 并将所有区间按包含关系建出一棵儿子有顺序的树。写出这棵树的括号序，显然对于任意的 $u$，都需要满足两个 $u$ 中间的所有数都比它小。考虑这个括号序能对应多少个区间序列，这就相当于我们在要括号序里面插入 $m$ 个 $0$，并且对于在原树上为叶子的 $u$（也就是在括号序里两个 $u$ 相邻），它们中间必须至少有一个 $0$。 我们先把叶子要求的一个 $0$ 塞进去，之后就可以当它们不存在。设叶子个数为 $k$ 则剩下的 $m-k$ 个 $0$ 可以随便塞。 现在我们需要求儿子有序，每个点的所有儿子都小于自己，且有 $n+1$ 个点 $k$ 个叶子的树的个数 $f_{n,k}$。结论是这就是二阶欧拉数 $\left<\left<\begin{matrix}n\\k-1\end{matrix}\right>\right>$！ ---- 容易通过它们有相同的递推式来证明这一点：二阶欧拉数的递推式可以使用与欧拉数相同的插入法推出。考虑将树写成括号序并按点的编号从大到小插入，新插入的点 $u$ 一定是叶子因此在括号序中相邻，如果插入在原来的叶子对应的两个 $v$ 中间叶子数不变否则加一，于是我们有 $f_{n,k}=(2n-k)f_{n-1,k-1}+kf_{n-1,k}$，这就是 $$\left<\left<\begin{matrix}n\\k-1\end{matrix}\right>\right>=(2n-1-(k-1))\left<\left<\begin{matrix}n-1\\k-2\end{matrix}\right>\right>+(k-1+1)\left<\left<\begin{matrix}n-1\\k-1\end{matrix}\right>\right>$$。 直接构造双射还是太困难了，我想了两个小时不会这个双射。期待组合意义大神来补充这个双射。 ---- 枚举叶子的个数，我们可以通过一个[具有组合意义的联系二阶欧拉数与斯特林数的恒等式](https://www.luogu.com.cn/article/5hvv0usl)得到： $${n+m\brace (n+m)-n}=\sum_k\left<\left<\begin{matrix}n\\k\end{matrix}\right>\right>\binom{m-k-1+2n}{2n}$$ 这样就完成了对结论的证明。 ---- 如果儿子无序则答案是欧拉数 $\left<\begin{matrix}n\\k-1\end{matrix}\right>$。对树 DFS 并钦定每次先搜最小的未走过的儿子，此时 DFS 序每个上升与最后一个数都对应一个儿子。