首页 > 代码库 > 组合数学及其应用——容斥原理
组合数学及其应用——容斥原理
容斥原理在集合论、概率论、组合数学中都常常出现,它是下面一个结论的推广。
这是因为,我们分别减|A|、|B|的时候,把|AB|减掉了两次,因此这里应该再加一次。
它的推广形式就是容斥定理。
在给出证明之前,我们很有必要充分的理解一下这个公式的内涵。我们基于S集合上的一系列离散元素上讨论不满足m个性质的对象(元素)个数。我们假想某一种性质的具体表现为:一根丝带,圈住了满足这一条性质的所有元素(本质上就是画Venn图),现在我们想要求的就是没有被特定的m条丝带圈出的元素个数。
这个定理再利用德摩根律能够做出等价变化,它在计数、反演公式等方面发挥着重要作用。
组合数学及其应用——容斥原理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。