这里将会记录一些典型的计数。
图计数
无向图计数
显然，\(n\) 个点的无向图个数应该为 \(2 ^ {\binom{n}{2}}\)。
\(n\) 个点 \(m\) 条边无向图计数
不妨设 \(g(n, m)\) 表示 \(n\) 个点 \(m\) 条边的无向图个数，显然有
\[g(n, m) = \dbinom{\binom{n}{2}}{m} \]设 \(f(n, m)\) 表示 \(n\) 个点 \(m\) 条边的无向连通图个数。对于无向图，枚举 \(1\) 号点相连的连通块大小以及边数，可以得到下面等式：
\[g(n, m) = \sum_{a \le n} \sum_{b \le m} \binom{n - 1}{a - 1} g(n - a, m - b) \times f(a, b) \]将 \(f(n, m)\) 的项分离出来，我们可以得到：
\[\begin{array}{c} g(n, m) = f(n, m) +\sum \limits_{a < n} \sum\limits_{b \le m} \dbinom{n - 1}{a - 1} g(n - a, m - b) \times f(a, b)\\\\ + \sum\limits_{a \le n} \sum\limits_{b < m} \dbinom{n - 1}{a - 1} g(n - a, m - b) \times f(a, b)\\\\ - \sum\limits_{a < n} \sum\limits_{b < m} \dbinom{n - 1}{a - 1} g(n - a, m - b) \times f(a, b) \end{array} \]这个公式看起来有点繁琐，不妨设 \(\mathcal{H}(n, m, x, y)\) 表示 \(\sum\limits_{a \le n} \sum\limits_{b \le m} \dbinom{n - 1}{a - 1} g(n - a, m - b) \times f(a, b)\)，移项后不难得到：
\[f(n, m) = g(n, m) - h(n, m, n - 1, m) - h(n, m, n, m - 1) + h(n, m, n - 1, m - 1) \]复杂度达到 \(O((nm) ^ 2)\)。使用斯特林反演可以做到 \(O(n ^ 2 m)\)。
\(n\) 点无向连通图计数
和上面的思路基本相同。最暴力的思路是枚举 \(1\) 号节点所在连通块的大小。
不妨设 \(g(n)\) 表示 \(n\) 个点的 无向图 个数，\(f(i)\) 表示 \(n\) 个点的 无向连通图 个数，那么有：
\[g(n) = \sum_{i \le n} \dbinom{n - 1}{i - 1} f(i) g(n - i) \]将 \(f(n)\) 分离并移项，可以得到：
\[f(n) = g(n) - \sum_{i < n}\dbinom{n - 1}{i - 1}f(i)g(n - i) \]这个做法是 \(O(n ^ 2)\) 的。
接下来你发现，若设出 \(f, g\) 的 \(\mathbf{EGF}\) 分别为 \(\mathcal{F, G}\)，上述式子可以直接分治 NTT。这样可以做到 \(O(n \ \mathrm{polylog}(n))\) 的复杂度。
树的拓扑序计数
这里的树指的是一棵根向树。
- 使用树形 \(\text{dp}\) 求解
不妨设 \(f_u\) 表示以 \(u\) 为根的树的拓扑序计数。不妨设其有两个儿子 \(v_1, v_2\)。这里的转移不可以将 \(f_{v_1}, f_{v_2}\) 简单相乘，还应该考虑两个子树之间的错排顺序。考虑从 \(sz_{v_1} + sz_{v_2}\) 中选出 \(sz_{v_1}\) 个放在前面，其余的放在后面。那么有方程
推广到一般树，就有
\[f_{u} = (sz_u - 1)! \prod_{v \in son(u)} \dfrac{f_v}{sz_{v}!} \]时间复杂度 \(O(n)\)。
- 使用生成函数求解
不妨设 \(\mathcal{[x ^ i]F_u(x)}\) 表示 \(u\) 子树选择了 \(i\) 个节点的拓扑序方案数。\(\mathcal{F}\) 为方案数的 \(\mathbf{EGF}\)。那么有
\[\mathcal{F_u(x)} = x \prod \mathcal{F_v(x)} \]其中乘上 \(x\) 表示选择自己的方案数。
使用 NTT 即可做到 \(O(n \log n)\)。所求即为 \([x ^ n]\mathcal{F_1(x)}\)。
二叉树计数
著名的卡特兰数。不妨设 \(f(i)\) 表示 \(i\) 个点的二叉树个数。那么有递推式：
\[f(n) = \sum f(i)f(n - i - 1) \]这是卡特兰数的递推式，答案就是
\[C(n) = \dfrac{\dbinom{2n}{n}}{n + 1} \]特殊二叉树计数
CF438E The Child and Binary Tree
给定集合 \(S\)，每个节点权值需要 \(\in S\)。二叉树的权值定义为其所有节点的权值和。求权值为 \(m\) 的二叉树总数。
发现是上一道题的强化版。普通二叉树计数是这道题 \(S = \{1\}, m = n\) 的弱化版。
不妨设 \([x ^ n]f(x)\) 表示总和为 \(n\) 的满足条件的二叉树个数，\(g(x) = \sum [i \in S] x ^ i\)，则有
\[f(x) = g(x) \times f(x) \times f(x) + 1 \]其意义为：左子树方案为 \(f\)，右子树方案为 \(f\)，本身方案为 \(g\)，加上空树。
解二次方程得到
\[f(x) = \dfrac{1 + \sqrt{1 - 4g(x)}}{2g(x)} \]上多项式就可以了。如果嫌麻烦可以分子有理化一下。
竞赛图三元环计数
考虑容斥。如果是无向完全图，则三元环个数显然是 \(\dbinom{n}{3}\)。减去不合法的方案即可。
不合法的方案就是从 \(u\) 出发的两条同向边。所以总方案即为
\[\dbinom{n}{3} - \sum_u \dbinom{d_u}{2} \]球盒问题
若干个小球放进若干个盒子的方案计数。按照盒子 / 小球的限制分为
-
小球有标号 / 无标号
-
盒子有标号 / 无标号
-
每个盒子至多放一个 / 至少放一个 / 无限制
共有 \(2 \times 2 \times 3 = 12\) 种选法。故称 \(12\) 球盒。
只能掌握比较简单的。比较困难的无法掌握。
小球有标号，盒子有标号，无限制
每个小球可以在 \(m\) 个盒子中选择。所以答案为 \(m \times m \cdots \times m = m ^ n\)。
小球有标号，盒子有标号，每个盒子至少放一个
考虑容斥。强制有 \(i\) 个盒子里没有球，那么 \(n\) 个球要放进剩下 \(m - i\) 个盒子里，方案数为 \((m - i) ^ n\)。由于盒子有标号，所以还要乘以一个 \(\binom{m}{i}\)。因此总方案数就是：
\[\sum \limits_{i = 0}^{m} (-1) ^ i \binom{m}{i} (m - i) ^ n \]小球有标号，盒子有标号，每个盒子至多放一个
如果 \(n > m\) 肯定无解。假设 \(n \le m\)，那么有 \(m - n\) 个盒子是空的。选出这 \(m - n\) 个盒子，方案数为 \(\binom{m}{m - n}\)。由于小球有标号，所以还要乘以小球的排列数。答案即为：
\[n! \binom{m}{m - n} = n! \binom{m}{n} \]小球无标号，盒子有标号，每个盒子至少放一个
插板法。将 \(n\) 个小球排成一排，在 \(n - 1\) 个空里面插入 \(m - 1\) 个板子，分成 \(m\) 份。答案即为
\[\binom{n - 1}{m - 1} \]小球无标号，盒子有标号，无限制
插板法变形。将 \(n\) 个小球排成一排，在后面再加入 \(m\) 个小球，现在小球总数为 \(n + m\)。将 \(m - 1\) 个板子插到 \(n + m - 1\) 个空里，将小球分成 \(m\) 份。分完之后，再从每一组里抽走一个小球，即可将每个盒子至少放一个转化为每个盒子里放 \(\ge 0\) 个。总方案数即为：
\[\binom{n + m - 1}{m - 1} \]小球无标号，盒子有标号，每个盒子至多放一个
思路和 小球有标号，盒子有标号，每个盒子至多放一个 类似。如果 \(n > m\) 无解。然后从 \(m\) 个盒子里选出 \(n\) 个非空盒子即可。这里由于小球无标号，所以不需要乘以 \(n!\)。答案即为
\[\binom{m}{n} \]小球有标号，盒子无标号，无限制
就是 第二类斯特林数。
令 \({n \brace m}\) 表示 \(n\) 个有标号小球放进 \(m\) 个盒子（盒子非空）的方案数，则有递推
\[{n \brace m} = {n - 1 \brace m - 1} + m \times {n - 1 \brace m} \]对于该式的理解：第 \(n\) 个小球单独放一个盒子，加上和其他 \(n - 1\) 个小球放一个盒子。
可以做到 \(O(n ^ 2)\) 的递推。多项式做法已经不想懂了。
对于该题，答案即为
\[\sum_{i \le m} {n \brace i} \]小球有标号，盒子无标号，每个盒子至多放一个
能放下就是 \(1\)，否则就是 \(0\)。
小球有标号，盒子无标号，每个盒子至少放一个
和第二类斯特林数定义相同。方案即为
\[{n \brace m} \]小球无标号，盒子无标号，每个格子至多放一个
能放下就是 \(1\)，否则就是 \(0\)。
小球无标号，盒子无标号，无限制
定义“划分数” \(P(n, m)\)，表示将 \(n\) 划分成 \(m\) 个非负整数的方案数。则有
\[P(n, m) = P(n - m, m) + P(n, m - 1) \]对于这个式子的理解：显然，对于划分出来的所有数都为整数的情况，将他们全部减一，可以建立到 \(P(n - m, m)\) 的双射。对于有 \(0\) 的情况，可以看做在后面加了一个零进去，方案数为 \(P(n, m - 1)\)，加入多个零可以通过这个递归定义。
显然可以多项式，但是我已经不想学了。所以这是一个 \(O(n ^ 2)\) 的算法。
小球无标号，盒子无标号，每个盒子至少放一个
将每个盒子里先钦定一个球，然后就是上一问的做法。方案数即为
\[P(n - m, m) \] 标签：标号,典型,盒子,dbinom,sum,小球,times,计数,一些 From： https://www.cnblogs.com/LcyRegister/p/18041708