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_kx^k}{(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{x^j}{(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}}{p^m m!}(\sum_k\binom{m}{2k}\binom{2k}{k}k!\frac{p^k}{2^k})^2 \]\(p^k\) means find a place to link two cycle.
for even
\[\prod_{p ~ even} \sum_{m ~ even} \frac{x^{pm}}{p^mm!}(\binom{m}{m/2}(m/2)!\frac{1}{2^{m/2}})^2 \]multiply to function gives the answer, though the computation is slow.
\[ \] 标签：even,frac,means,--,sum,等价,ZJOI2018,odd From： https://www.cnblogs.com/pigpigger/p/17380286.html