容斥原理
组合数学中基本原理之一
条目
历史版本
容斥原理（英文名：Principle of inclusion-exclusion[6]）又称排容原理，[1]定义为：在进行计数时，确保没有重复和遗漏是非常重要的。为了避免重叠部分被重复计算，人们研究出了一种新的计数方法。这种方法的基本思想是首先不考虑重叠的情况，先计算包含在某内容中的所有对象的数量，然后再将重复计算的数量排斥出去，以确保计算的结果既没有遗漏又没有重复。这种计数方法被称为容斥原理。[2]
容斥原理的最早运用可追溯至16世纪，当时瑞士数学家尼古拉·贝努利在解决错位排列问题时首次采用了这一原理。然而，那时尚未有明确的数学表述。17世纪，数学家John Venn以集合的形式提出了容斥原理的初步数学表达。随后，著名数学家康托尔在17世纪末引入集合论，将容斥原理建立在更为坚实的基础上，使其成为处理复杂计数和概率问题的重要工具。到了19世纪，英国数学家詹姆斯·约瑟夫·西尔维斯特首次提出了该定理的现代表述。[7][8]
容斥原理的证明可以采用数学归纳法或枚举法，将定理进行推广，可得到一些新的结论。[3]容斥原理广泛地应用于数学、概率论、计算机等领域，如，在图论中，容斥原理可以用于计算满足某些性质的图的数量，或者计算不满足某些性质的图的数量。[9][10][4][5]