树的拓扑序计数

· · 算法·理论

复习时想起这个,想不起来怎么推的,随手翻了一篇博客结果写的狗屁不通,后在 @Rnfmabj 帮助下得出式子,遂打算专门写一篇。

首先,此处的“树拓扑序”指:对一颗有根树 T 的所有结点的排列,满足每个结点都出现在其父亲结点之后。

f_u 表示以 u 为根的子树的答案,我们首先需要想办法组合两个排列。

考虑长度为 xy 的两个有序排列在不影响原有顺序的情况下作为两个子序列构成一个新的序列的方案数,等价于在 x+y 个空中找 x 个空的方案数;对于多个排列,假设我们已经知道这些排列的总长度,那么从第一个排列开始,找到能够容纳它的空位,其方案数显然和前面一样,直接以组合数计算;之后,在总空位中减去刚才占用的空位作为剩余空位,继续进行组合数计算,以此类推。

写成式子,设这 k 个有序排列中的第 i 个有序排列长度为 x_i,总长度为 L,展开组合数式子,答案为 \prod_{i=1}^{k} \frac{(L-\sum_{j=1}^{i-1}x_j)!}{x_i!((L-\sum_{j=1}^{i}x_j)!)},其中除了最后一项外,第 i 项分母上的 (L-\sum_{j=1}^{i}x_j)! 可以和第 i+1 项上分子上的 (L-\sum_{j=1}^{(i+1)-1}x_j)! 相消,而对于最后一项即第 k 项,有 \sum_{i=1}^kx_i=L,即 (L-\sum_{j=1}^{i=k}x_j)!=0!=1,可以忽略,最终化简为 \frac{L!}{\prod_{i=1}^k(x_i!)}

回到原问题的递推,不同子树的拓扑序合并可以分解为若干个有序序列按以上规则归并后再乘以每个序列的数量之积,设 siz_u 为以 u 为根的子树大小,对应上式 \frac{L!}{\prod_{i=1}^k(x_i!)},其中 x_i=siz_v(v\in son(u)),L=siz_u-1,减一是为了保证拓扑序合法,因而结点 u 必须放在第一个位置,留给子树结点组合的空间自然要减一。

将子树本身的拓扑序考虑上,得出递推公式:f_u=(siz_u-1)!\times \prod_{v\in son(u)}\frac{f_v}{siz_v!},此时已经可以线性递推解决计数问题,但该式仍可进一步化简:

(siz_u-1)!=\frac{siz_u!}{siz_u},递推式可化为:f_u=\frac{siz_u!}{siz_u}\prod_{v\in son(u)}\frac{siz_v!\times \prod_{w\in son(w)}\frac{f_w}{siz_w!}}{siz_v\times siz_v!}=\frac{siz_u!}{siz_u}\prod_{v\in son(u)}\frac{\prod_{w\in son(w)}\frac{f_w}{siz_w!}}{siz_v},将分母的 \prod\frac{1}{siz_v} 提出去,分子继续递归下去,显然每次都能将一层儿子的 \prod\frac{1}{siz_u} 提出去后继续递归,直到叶子,此时提出分母后分子为 1

由上面的递归过程,显然可得 f_u=\frac{siz_u!}{\prod_{x\in subtree(u)}siz_x},此时可以很方便地进行换根计算或者用数据结构维护信息。