容斥原理怎么证明
发布网友
发布时间：2022-05-16 21:43
共1个回答
热心网友
时间：2023-09-12 06:23
所以关于自然数的命题基本上都有数学归纳法背景.
常用的"依此类推","..."这样的写法本质上也是数学归纳法的简略形式.
要在"形式上"不用数学归纳法证明容斥原理,可以用二项式定理.
设A[1],A[2],...,A[n]是n个集合,用|S|表示集合S的元素个数,C(m,k)表示m中选k的组合数.
证明容斥原理:|A[1]∪A[2]∪...∪A[n]| = ∑{1 ≤ i ≤ n} |A[i]|-∑{1 ≤ i < j ≤ n} |A[i]∩A[j]|
+∑{1 ≤ i < j < k ≤ n} |A[i]∩A[j]∩A[k]|-...+(-1)^(n-1)·|A[1]∩A[2]∩...∩A[n]|.
对任意x ∈ A[1]∪A[2]∪...∪A[n],设A[1],A[2],...,A[n]中恰有m个集合包含x.
A[i]∩A[j]包含x当且仅当A[i]与A[j]都包含x.
因此在A[1],A[2],...,A[n]的两两之交中恰有C(m,2)个交集包含x.
在三三之交中恰有C(m,3)个集合包含x,依此类推.
可知在右端的和式中,x被计数的次数为C(m,1)-C(m,2)+C(m,3)-...+(-1)^(m-1).
而由二项式定理,有0 = (1-1)^m = 1-C(m,1)+C(m,2)-C(m,3)+...+(-1)^m.
即C(m,1)-C(m,2)+C(m,3)-...+(-1)^(m-1) = 1.
A[1]∪A[2]∪...∪A[n]中的任意元素,在右端和式中恰好被计数1次.
即证明了容斥原理.
