给定两个顶点集的二分图数量计算疑问

嗨，我来帮你理清这个问题～首先得明确题目里的关键前提：题目说“the two sets of vertices are V = {v₁…vₙ}, W = {w₁…wₘ}”，这意味着二分划分是固定的——我们只考虑那些以V和W作为两个顶点划分的二分图，不需要考虑其他可能的划分（比如把顶点重新分成两个集合的情况）。

接下来拆解你的思路：

• 你一开始想到的mⁿ，其实对应的是“每个V中的顶点恰好连接到W中的一个顶点”的情况（相当于从V到W的函数总数），但这只是所有可能二分图里的极小一部分——因为二分图完全允许顶点不连接任何边，或者一个V中的顶点连接多个W中的顶点，反过来也一样。
• 你提到的m!S(n,m)，这是从V到W的满射函数的数量（S(n,m)是第二类斯特林数，代表把n个元素分成m个非空子集的方式，乘以m!就是给每个子集分配一个W中顶点的排列数），对应的是“每个W中的顶点都至少被一个V中的顶点连接，且每个V中的顶点恰好连接一个W中的顶点”的情况，这同样只是特殊情况，不是全部二分图的数量。

那正确的计算方式是什么呢？
我们回到二分图的定义：在固定划分V和W的情况下，所有的边都只能在V和W之间，V内部、W内部都不能有边。那每个可能的边是“v_i和w_j之间的边”，总共有n*m条这样的潜在边。对于每条潜在边，我们有两种选择：要么存在这条边，要么不存在。

所以总的二分图数量就是2^(n*m)。

这里要注意几个点：

• 这个结果允许V或W中有孤立顶点（也就是不连接任何边的顶点），这完全符合二分图的定义——二分图只要求顶点划分成两个集合，边跨集合，没要求每个顶点都必须有边。
• 如果题目额外要求“每个顶点都至少有一条边”（也就是没有孤立顶点），那计算会复杂一些：需要用容斥原理，先算所有二分图，减去有至少一个V中顶点孤立的，减去至少一个W中顶点孤立的，再加回重复减去的部分，以此类推。公式大概是：
  sum_{a=0 to n} sum_{b=0 to m} (-1)^(a+b) * C(n,a) * C(m,b) * 2^((n-a)(m-b))
  不过看你的问题描述，题目没有提这个额外条件，所以默认是允许孤立顶点的，那基础的2^(n*m)就是正确答案。

最后再总结一下：你之前的思路都局限在“每个V顶点只连一个W顶点”的特殊情况，但二分图的边可以是任意的跨集合组合，所以要从所有可能的边子集来考虑～

备注：内容来源于stack exchange，提问作者Emmy N.