树的拓扑序计数

标签：aligned frac 拓扑 son 计数 end prod size

前几天模拟赛遇到的，发现叫这个。
对于一个排列 \(P\) 和一棵有根树，有多少中排列满足所有父亲位置都在儿子位置后面。
首先有一个树形 DP：

\[\begin{aligned} f_u=\prod_{v\in son_u}{size_{u,v}-1\choose size_v}f_v \end{aligned} \]

\(size_{u,v}\) 表示 \(u\) 统计到儿子 \(v\) 时的子树大小，\(size_{v}\) 表示 \(v\) 的子树大小。这个式子应该很好理解，但是这样问题不那么清晰了。
因为儿子直接是互不影响的，所以就相当于儿子随机排列，插板即可，有：

\[\begin{aligned} f_u&={size_u-1\choose size_{v_1},size_{v_2},size_{v_3},\cdots size_{v_{tot}}}\prod_{v\in son_u}f_v\\ &=\frac{(size_u-1)!}{\prod_{v\in son_u}size_v!}\prod_{v\in son_u}f_v\\ \end{aligned} \]

其实第一步就是合并成了多项式系数，考虑把 \(f_v\) 展开也是这么个形式，把\((size_u-1)!\) 改成 \(\frac{size_u!}{size_u}\) 就能直接相消了，所以最后的答案就是 \(\Large\frac{n!}{\prod_{i=1}^nsize_i}\)。

标签：aligned,frac,拓扑,son,计数,end,prod,size
From： https://www.cnblogs.com/Ishar-zdl/p/18657946