提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【集合论】容斥原理 ( 包含排斥原理 | 示例 )

原理 示例 包含 集合论 排斥
2023-06-13 09:17:44 时间

文章目录

一、 容斥原理

A_1 , A_2 , \cdots , A_n

是

n

个集合 ; 则 这

n

个集合 并集的元素个数 是 :

| \bigcup_{i=1}^{n} A_i | = \sum_{i = 1}^n | A_i | - \sum_{i < j} | A_i \cap A_j | + \sum_{i < j < k} | A_i \cap A_j \cap A_k | - \cdots + ( -1 )^{n - 1} | A_1 \cap A_2 \cap \cdots \cap An |

解析 :

n

个集合进行并运算后 , 元素个数 , 通常使用 容斥原理 进行计算 ;

\sum_{i = 1}^n | A_i |

: 将每个集合中的 元素个数 相加 , 该值大于 总元素数 , 需要进行修正 ; ( 系数值

(-1)^0

)

\sum_{i < j} | A_i \cap A_j |

: 减去两两相交的元素个数 , 该值又小于 总元素数 , 继续进行修正 ; ( 系数值

(-1)^1

)

\sum_{i < j < k} | A_i \cap A_j \cap A_k |

: 加上三个集合相交的元素个数 , 该值大于 总元素数 , 继续进行修正 ; ( 系数值

(-1)^2

)

减去四个集合相交的元素个数 , 该值小于 总元素数 , 继续进行修正 ; ( 系数值

(-1)^3

)

\vdots
( -1 )^{n - 1} | A_1 \cap A_2 \cap \cdots \cap An |

: 加上

( -1 )^{n - 1}

乘以

n-1

个集合相交的元素个数 ; ( 系数值

(-1)^{n-1}

)

上述 奇数个集合 交集元素个数 前系数是 正数 , 偶数个集合 交集元素个数 前系数是 负数 ;

二、 容斥原理 示例

1

~

10000

之间 , 既不是某个整数的平方 , 又不是某个整数的立方 , 的数个数 ?

全集 :

E

集合是全集 , 是

1

到

10000

的自然数 ,

E

集合的个数

|E| = 10000

平方对应的数集合

A

:

A

集合是 某个数 的平方 对应的 某个数 集合 ,

A = \{ x \in E | x = k^2 \land k \in Z \}

,

A

集合元素个数是

|100|

;

100^2 = 10000

, 因此

A

集合的元素是

\{0, 1, 2 , \cdots , 100 \}

, 元素个数有

100

个 ;

1^2 , 2^2 , 3^3, \cdots ,100^2

都在

1

到

10000

之间 ,

101^2 = 10201

就超过

10000

了 ;

立方对应的数集合

B

:

B

集合是 某个数 的立方 对应的 某个数 集合 ,

B = \{ x \in E | x = k^3 \land k \in Z \}

,

A

集合元素个数是

|21|

;

21^3 = 9261

, 因此

B

集合的元素是

\{0, 1, 2 , \cdots , 21 \}

, 元素个数有

21

个 ;

1^3 , 2^3 , 3^3, \cdots ,21^3

都在

1

到

10000

之间 ,

22^2 = 10648

就超过

10000

了 ;

计算

A \cap B

集合的交集

C

: 元素个数 , 既是平方 , 又是立方 , 肯定是六次方的数 ,

C= \{ x \in E | x = k^6 \land k \in Z \}

,

C

集合的元素个数是

4

;

4^6 = 4096

, 因此

C

集合的元素是

\{1, 2 , 3, 4\}

, 元素个数有

4

个 ;

1^6 , 2^6 , 3^6, 4^6

都在

1

到

10000

之间 ,

5^6 = 15,625

就超过

10000

了 ;

题目可以转化成 : 集合

Z

中 , 既不属于

A

集合 , 有不属于

B

集合 的数字 ;

集合

A

与 集合

B

并集是

A \cup B

上述并集 的 绝对补集

\sim ( A \cup B )

元素个数

|\sim ( A \cup B ) |

, 就是题目中要求的结果 ;

|\sim ( A \cup B ) | = |E| - |A \cup B|

上述式子中 ,

|E| = 10000

,

|A \cup B|

值可以使用 容斥原理 进行计算 ;

|A \cup B|

两个集合并集的元素个数 , 可以使用两个集合的元素个数相加 , 然后减去两个集合交集的元素个数 ;

|A \cup B| = |A| + |B| - |A \cup B| = 100 + 21 - 4 = 117

代入总的公式 :

|\sim ( A \cup B ) | = |E| - |A \cup B| = 10000 - 117 = 9883

相关文章