容斥原理
教育事业百科16 阅读
计算一集合中元素个数的定理。当S是有限集，Ai表示S中具有性质pi的元的集，则S中不具有性质p1，p2，…，pm的元素的个数由下式给出：式中■表示S中不具有性质Pi的元的集；｜Ai｜表示集Ai的元的个数。特别，m＝2，｜■1∩■2｜＝｜S｜-｜A1｜-｜A2｜＋｜A1∩A2｜，即S中不具有性质p1，p2的元的个数是S的元数减去具有性质p1的元数，减去具有性质p2的元数，但要加上同时具有p1，p2的元数。例如，1～100间不能被5、6、7任一个整除的整数个数。用A1、A2、A3分别表示被5、6、7整除的整数集，并用〔n/r〕表示整数1～n间能被整数r整除的个数，｜A1｜＝〔100/5〕20，｜A2｜＝〔100/6〕＝16，｜A3｜＝〔100/7〕＝14；而｜A1∩A2｜＝〔100/30〕＝3，｜A1∩A3｜＝〔100/35〕＝2，｜A2∩A3｜＝〔100/42〕＝2，而｜A1∩A2∩A3｜＝〔100/210〕＝0。于是｜■1∩■2∩■3｜100-（20＋16＋14）＋（3＋2＋2）-0＝100-50＋7＝57。