本文不会停更

基础 EGF

一个数列的指数型生成函数为 \(\sum\limits_{i=0}^{\infty} \frac{a_i}{i!}x^i\)

拿出两种相同的物品（种内相同）\(i\) 个，求不同排列的方案数

\[G(x)=\sum\limits_{i=0}^{\infty}\frac{x^i}{i!} \]

\[R(x)=\sum\limits_{i=0}^{\infty}\frac{res_i}{i!}x^i \]

\[R(x)=G^2(x) \]

数学意义理解一下

例题还没有

prufer序列

序列 \(\to\) 树：每次找在 \(\{1\dots n\}\) 点集中还有的最小且没有在序列里面出现过的点和序列里面第一个点连边

树 \(\to\) 序列：当前树上度数为 \(1\) 的编号最小的点和所连的点加入序列

性质：

\((1)\) \(prufer\) 序列长度为 \(n-2\)

\((2)\) 度数为 \(d_i\) 的点在序列里面出现了 \(d_i-1\) 次

\((3)\) \(n\) 个点 \(m\) 个联通块每个大小为 \(a_i\) 的方案是：\((n^{m-2})\prod a_i\)

\((4)\) \(n\) 个点钦定 \(k\) 个点在不同的树里面的方案数是 \(k\times n^{n-k-1}\)

最后一个不会证明

序列和 \(EGF\) 的混用是数树题的常见套路

暂时留坑了