引言

学计数问题就像围城,城外的人不想进去,城里的人不想出来.

前前排提示

本文不全是多项式和生成函数.

前排提示

本文含有以下内容 :

• 入 门 失 败

• 由 难 到 难

• 无 用 科 技

• 快 速 退 役

• 弱 智 讲 解

• 不 想 证 明

• 感 性 理 解

• 丑 陋 \(\LaTeX\)

• 强 行 加 \large

• 微 小 下 标

• 视 力 受 损

• 边 学 边 写

• 长 期 拖 更

• 没 有 编 号

• 例 题 丢 失

• 不 放 代 码

• 编 号 随 意

• 不 如 去 学 二 分

• 不 如 刷 几 道 题

请对以上内容感到不适者自行 Ctrl + W.

保证不出现以下内容 :

• 排 版 壬 震 怒

• 如 蜜 传 如 蜜

• 新 华 大 辞 典

• 贴 别 人 博 客

• 入 门 即 入 土

保证对于博客中 \(100 \%\) 的和式,为有明确界限的和式.

保证对于博客中 \(100 \%\) 的 \(\LaTeX\) , 其前后有空格.

附 : 博客中出现以及未来可能会出现的题目题单一份

前置知识

咱也不知道.

目录

慢慢整.

• 引言

• 前排提示

• 目录

• 约定与图论基础

• 三元环计数

  1. 无向图三元环计数

  2. 有向图三元环计数

  3. 完全图三元环计数

  4. 竞赛图三元环计数

  5. 竞赛图三元环期望

• Prufer 序列与 Caylay 定理

• LGV 引理

• 矩阵树定理

• 二分图计数

  • sub1

  • sub2

  • sub3

• 简单图计数

  1. 有标号简单图无向计数

  2. DAG 计数

• 其他

  1. 二叉树计数

  2. 三叉树计数

• 彩蛋 : 二分图最大匹配计数

约定与图论基础

图(Garph) : 定义由点集 \(V\) 与边集 \(E\) 组成的二元组叫做图,以下令 \(G<V,E>\) 表示一个点集为 \(V\) ,边集为 \(E\) 的图. 如无特殊说明,通常认为题目中的图具有 \(n\) 个点与 \(m\) 条边.

无向图(Undirected Graph) : 每条边不标定方向.

有向图(Directed Graph) : 每条边标定方向.

边(Edge) : 一个有序或无序的二元组,例如一条从 \(u\) 连向 \(v\) 的边,记作 \((u,v)\)

完全图(Complete Graph) : 对于一个图 \(G<V,E>\) ,若 \(\forall u,v \in V(u \not= v),(u,v)\),那么这是一个完全图. 有 \(n\) 个结点的完全图记为 \(K_n\) .

竞赛图(Tournament Graph) : 对于一个完全图,将其每条边标定一个方向就得到了竞赛图.

度(Degree) : 与一个顶点 \(u\) 关联的边的条数称作该顶点的度. 记无向图一点 \(u\) 的度为 \(d_u\). 记有向图一点 \(u\) 入度(positive deg)为 \(pd_u\),出度(negative deg)为 \(nd_u\).

三元环(Three-Vertex Cycle) : 一个三元环为由三个点 \(u,v,w\) 组成的无序三元组 \(<u,v,w>\) ,且满足 \((u,v),(v,w),(w,u) \in E\) .两个三元环 \(G_1,G_2\) 不同当且仅当 \(\exists u \in G_1\) 且 \(u \not\in G_2\) .

有向无环图 : 简称 DAG.

三元环计数

主要内容 : 组合数学.

无向图三元环计数

首先三元环并不能特别多,但是 \(\mathrm{O} (n ^ 3)\) 的复杂度明显不是很好,此题正解为 \(\mathrm{O} (m \sqrt{m})\) .

首先记录每个点的度,将每条边按照如下的方式重定向 :

对于一条边 \((u,v)\) , 如果 :

• \(d_u < d_v\) 这条边从 \(v\) 连向 \(u\).

• \(d_u > d_v\) 这条边从 \(u\) 连向 \(v\).

• \(d_u = d_v\) 这时需要一个统一的连边标准,可以选择从编号大的连向编号小的.

以上这一步使得每个点出边总是 \(\sqrt{m}\) 的水平.

然后枚举每个点 , 对于枚举到的一个点 \(u\) , \(\forall (u,v) \in E\) , 将 \(v\) 打上标记 \(u\) ,对于 \(u\) 的出边集均执行这个操作后,再次枚举 \(v\) 且枚举 \(v\) 的出边,如果存在点 \(w\) 使得 \(w\) 的标记为 \(u\) ,那么就找到了一个三元环.

P6815 [PA2009]Cakes 统计一下即可,但是图很稠密,链前会被卡常 (悲),但是 std::vector 很快 (喜).

CF985G Team Players 比赛编号985

正难则反,容斥一下.

先把所有三元组分类计数 :

• 全不合法,记为 \(x_0\)

• 至少一条边合法,记为 \(x_1\)

• 至少两条边合法,记为 \(x_2\)

• 至少三条边合法,记为 \(x_3\)

最后记所有三元环为 \(x_tot\)

那么就是求 \(x_0\) 了.

容斥一下可知 : \(x_tot - x\)

P4619 [SDOI2018]旧试题

完全不可做的奇葩反演卡常题,但是这道题确实用了三元环计数.

下辈子补上.

有向图三元环计数

按照上面的算法正常跑,在找到一个三元环时特判三边方向是否全部合法即可.

完全图三元环计数

任意选三个点就是合法三元环.

三元环个数为 \(\binom{n}{3}\) .

竞赛图三元环计数

转化为求其补集 :

发现如果是一个完全图,其三元环个数为 \(\binom{n}{3}\),考虑其中哪些是不合法的三元环即可.

三元环个数为 :

\[ \large{\binom{n}{3} - \sum^{n}_{i = 1} \binom{nd_i}{2}} \]

竞赛图三元环期望

给定点数 \(n\) , 与图中 \(m\) 条边的方向,求三元环期望个数.

依然补集转化 :

统计出入度,在上一题基础上再扣除一部分 :

令 \(ind_u\) 表示点 \(u\) 的入度.

令 \(outd_u\) 表示点 \(u\) 的出度.

那么点 \(u\) 未标定边数量表示为 : \(ud_u = n - 1 - pd_u - nd_u\)

三元环期望个数为 :

\[ \large{\binom{n}{3} - \sum^{n}_{i = 1} (\binom{nd_i}{2} + \frac{nd_i \cdot ud_i}{2} + \frac{\binom{ud_i}{2}}{4})} \]

Prufer 序列与 Caylay 定理

LGV 引理

矩阵树定理

Kirchhoff 矩阵树定理能够求解图的生成树计数问题.

二分图计数

二分图的性质真是奇妙,性质就和竞赛图一样多.

建议翻到最后看看彩蛋.

sub1

求有 \(n\) 个有标号结点,黑白染过色的二分图个数.

不同仅当颜色或者边不同.

首先枚举黑白个数然后枚举哪些边连上就行,因为只能黑连白.

个数为 :

\[\large{\sum_{i = 0}^{n}\binom{n}{i}2^{i(n - i)}} \]

sub2

求有 \(n\) 个有标号结点的联通的二分图个数.

考虑从上面拓展.因为这个图连通,那么只需指定任何一点的颜色即可确定其余所有点的颜色,那么一个连通块就是 2 种状态.

然后考虑枚举一下有多少个连通块然后每个连通块的染色方案,整一个 EGF.

令 \(F(x)\) 表示 sub1 的EGF,\(G(x)\) 表示 sub2 的EGF.

\[\large\begin{aligned} &F(x) = \sum_{n = 0}^{\infty} \frac{\sum_{i = 0}^{n}\binom{n}{i}2^{i(n - i)}x^n}{n!}\\ &F(x) = \sum_{n = 0}^{\infty} \frac{2^nG^n(x)}{n!} \end{aligned}\]

然后因为 :

\[\large \sum_{n = 0}^{\infty} c^n\frac{x^n}{n!} = e^{cx} \]

那么 :

\[\large F(x) = e^{2G(x)} \]

那么多项式对数函数求 \(\frac{1}{2}\ln F(x)\) 即可.

sub3

求有 \(n\) 个有标号结点的二分图个数.

考虑

简单图计数

有标号简单图无向计数

首先考虑可行的所有边,显然,为 \(\frac{n(n - 1)}{2}\) 条.

每条边都可以选或者不选,乘法原理可知,数量为 :

\[ \large{2^{\frac{n(n - 1)}{2}}} \]

DAG 计数

其他

这一部分就是想到哪写到哪了.

二叉树计数

求 \(n\) 个点的二叉树有几种形态.

著名的卡特兰数.

\[\large{C_n = \frac{\binom{2n}{n}}{n + 1}} \]

证明 : 令 \(f(x)\) 表示 有 \(x\) 个点的二叉树的不同形态个数.

那么通过枚举根节点左右子树分别有多少个结点可得以下递推式 :

\[f(x) = \sum^{x - 1}_{i = 0} f(i) \cdot f(n - i - 1) \]

做其 \(\mathrm{OGF}\) 得到 :

\[F(x) = \sum^{\infty}_{ n = 0} f(n)x^n \]

那么对于 \(F(x) \cdot F(x)\) , 其 \(x^n\) 项的系数为 \(f(n + 1)\), 那么对于 \(x \cdot F(x) \cdot F(x)\) , 其 \(x^n\) 项的系数为 \(f(n)\) .

列出等式如下 :

\[x \cdot F(x) \cdot F(x) = F(x) \]

解方程求得 :

\[F(x) = \frac{1 - \sqrt{1 - 4x}}{2x} \]

然后直接泰勒展开日过去得到通项.

\(↑\) 没学过,换一个.

单独考虑 \(\sqrt{1 - 4x}\) 这一部分,对其做广义二项式展开.

根据 :

\[(1 + x)^\alpha = \sum^{\infty}_{k = 0} \binom{\alpha}{k} x^k \]

有 :

\[\begin{aligned} \sqrt{1 - 4x} &= (1 - 4x)^{\frac{1}{2}}\\ &= \sum_{k = 0}^{\infty} \binom{\frac{1}{2}}{k} (-4x)^k\\ &= 1 + \sum_{k = 1}^{\infty} \frac{(\frac{1}{2})(-\frac{1}{2})(-\frac{3}{2})\cdots (\frac{3 - 2k}{2})}{k!} (-4x)^k \\ &= 1 + \sum_{k = 1}^{\infty} (-1)^{n - 1} \frac{1 \times 3 \times 5 \cdots \times (2k - 3)}{2^k k!} (-4x)^k \\ &= 1 - 2 \sum_{k = 1}^{\infty} \frac{(2k - 2)!}{k!(k - 1)!} x^k \\ \end{aligned}\]

然后代入原式 :

\[F(x) = \sum_{n = 0}^{\infty} \frac{\binom{2n}{n}}{n + 1} x^n \]

即可得到通项.

三叉树计数

希望 \(\mathrm{\color{black}{L}\color{red}{ast\_Order}}\) 能看到这个.

求 \(n\) 个点的三叉树有几种形态.

OEIS链接

\[\large{T_n = \frac{\binom{3n}{n}}{2n+1}} \]

彩蛋 : 二分图最大匹配计数

没有这种算法,这是一个 \(\mathrm{\# P-Complete}\) 问题,乐.

也就是对于一个 \(\mathrm{P}\) 类问题,如果从求解转化为求解的个数,那这就是一个 \(\mathrm{\# P}\) 问题(sharp - P problem).

众所周知网络流是 \(\mathrm{P}\) 问题,于是二分图最大匹配自然也是.