【集合论】容斥原理 ( 复杂示例 )

容斥原理示例

个人

说英语 , 日语 , 德语 , 法语的人数

13, 5, 10, 9

同时说英语日语人数

同时说英语德语人数

同时说英语法语人数

同时说法语德语人数

说日语的人不会法语德语 ;

求只会说一种语言的人 ? 同时会说英语德语法语的人 ?

单个语言集合 :

集合表示会说英语的人的集合 ,

|A| = 13

;

集合表示会说日语的人的集合 ,

|B| = 5

;

集合表示会说德语的人的集合 ,

|C| = 10

;

集合表示会说法语的人的集合 ,

|D| = 9

;

两两相交集合 :

A cap B

集合表示会说英语日语的人的集合 ,

|A cap B| = 2

;

A cap C

集合表示会说英语德语的人的集合 ,

|A cap C| = 4

;

A cap D

集合表示会说英语法语的人的集合 ,

|A cap D| = 4

;

C cap D

集合表示会说德语法语的人的集合 ,

|C cap D| = 4

;

会说日语的人 , 既不不会说法语 , 也不会说德语 , 说明集合

与集合

C, D

都不相交 ;

|B cap C| = |B cap D| = |A cap B cap C| = |A cap B cap D| = |B cap C cap D| = |A cap B cap C cap D| = 0

总的人数是

人 :

|A cup B cup C cup D| = 24

根据容斥原理 :

|A cup B cup C cup D| =

| A | | B | | C | | D |

先将单个集合的个数相加

减去两两相交的元素个数

加上三三相交的元素个数

- |A cap B cap C cap D|

减去四个集合相交的元素个数

= 24

将上面的集合元素个数全部代入 :

|A cup B cup C cup D| =

13 5 10 9

先将单个集合的个数相加

- ( 2 4 4 0 0 4 )

减去两两相交的元素个数

( 0 0 | A cap C cap D | 0 )

加上三三相交的元素个数

- 0

减去四个集合相交的元素个数

= 24

计算后得到 :

37 - 14 | A cap C cap D | = 24

| A cap C cap D | = 1

同时会说英法德语的人

| A cap C cap D | = 1

只有

个 ;

计算只会说英语的人 :

| A | - | ( B cup C cup D ) cap A |

= |A| - | (B cap A) cup ( C cap A ) cup ( D cap A ) |

使用容斥原理 , 计算

| (B cap A) cup ( C cap A ) cup ( D cap A ) |

( |A cap B cap C cap D| )

= ( 2 4 4) - ( 0 0 1 ) ( 0 ) = 9

| A | - | ( B cup C cup D ) cap A |= |A| - | (B cap A) cup ( C cap A ) cup ( D cap A ) | = 13 - 9 = 4

只会说英语的人有

个 ;

按照上述步骤 , 计算出其它只说日语的人

个 , 只说德语的人 3 个 , 只说法语的人

个 ;

集合原理

0 人点赞

【集合论】容斥原理 ( 复杂示例 )

容斥原理 示例

容斥原理示例