容斥原理
组合数学中基本原理之一
条目
容斥原理（英文名：Principle of inclusion-exclusion[6]）又称排容原理，[1]是组合数学中的核心计数方法，用于计算多个有限集合的并集大小。其核心思想是：一些元素会同时存在于多个集合中，如果仅将这些集合的元素数量相加来求并集中元素数量会导致重复计算，因此需要通过交替加减各集合的交集来消除重复计数，从而精确求得并集的元素数量。[2]
容斥原理的最早运用可追溯至16世纪，当时瑞士数学家尼古拉·贝努利在解决错位排列问题时首次采用了这一原理。然而，那时尚未有明确的数学表述。17世纪，数学家John Venn以集合的形式提出了容斥原理的初步数学表达。随后，著名数学家康托尔在17世纪末引入集合论，将容斥原理建立在更为坚实的基础上，使其成为处理复杂计数和概率问题的重要工具。到了19世纪，英国数学家詹姆斯·约瑟夫·西尔维斯特首次提出了该定理的现代表述。[7][8]
容斥原理的证明可以采用数学归纳法或枚举法，将定理进行推广，可得到一些新 的结论。[3]容斥原理广泛地应用于数学、概率论、计算机等领域，如，在图论中，容斥原理可以用于计算满足某些性质的图的数量，或者计算不满足某些性质的图的数量。[9][10][4][5]