ZJOI2018树--等价类相关计算
发布时间 2023-05-07 22:04:40作者: pigpigger
ZJOI2018 树
- 节点 1 作为树的根。
- 对于 \(i \in [2, n]\) ，独立地从 \([1, i)\) 中等概率随机选取一个节点作为 \(i\) 的父亲。
通过上面的方法独立的随机生成 \(k\) 棵 \(n\) 个节点的有根树 \(T_1\) 至 \(T_k\) ，他们两两同构的概率是多少。
denote \(s(t)\) the ways assign number to a tree
Define a shift operator \(D_c\) by
$$
D_c(\sum_k\frac{a_kxk}{(k!)c})=\sum_k\frac{a_kx{k-1}}{((k-1)!)c})
$$
we want to know
(now the variable \(t\) always means a tree with size \(|t|\))
$$
T_k=\sum_t\frac{x{|t|}s(t)k}{(t!)^k}
$$
we have a equation
$$
D_k(T_k(x))=\prod_{t}\sum_i\frac{x{i|t|}s(t){ik}}{(|t|!){ik}(i!)k}=\exp(\sum_iT_{ik}(x^i)f_{k,i})
$$
here \(f_{k,i}\) means the i-th coefficient of
$$
\ln(\sum_j\frac{xj}{(j!)k})
$$
so it can be solved by newton iteration or other techniques in \(O(n^2)\)
## enum comb vol2 exercise 5.12
Let \(f(n)\) be the number of pairs \((u,v)\) of [n] permutations satisfying \(u^2=v^2\) find egf. of \(f\)
in fact the answer is \(\sum_i p_ix^i\) where \(p_i\) is integer partition , but I do not know how to do that.
but these kind of problem that enumerate information about equivalence class is extremely similar.
when squaring a cycle , it will remain unchanged when it is odd, and split into two when it is odd, so
for odd
$$
\prod_{p ~ odd} \sum_m\frac{x{pm}}{pm m!}(\sum_k\binom{m}{2k}\binom{2k}{k}k!\frac{pk}{2k})^2
$$
\(p^k\) means find a place to link two cycle.
for even
$$
\prod_{p ~ even} \sum_{m ~ even} \frac{x{pm}}{pmm!}(\binom{m}{m/2}(m/2)!\frac{1}{2{m/2}})2
$$
multiply to function gives the answer, though the computation is slow.
$$
$$