当前位置：网站首页>[set theory] inclusion exclusion principle (including examples of exclusion principle)

[set theory] inclusion exclusion principle (including examples of exclusion principle)

2022-07-03 04:09:00 【Programmer community】

List of articles

One 、 Principle of tolerance and exclusion
Two 、 Principle of tolerance and exclusion Example

One 、 Principle of tolerance and exclusion

⋯

A_1 , A_2 , \cdots , A_n

$A_{1}, A_{2}, \dots, A_{n}$ yes

$n$ A collection of ; be this

$n$ A collection of Number of elements in union yes :

∣

⋃

∣

∑

∣

−

∑

∣

∩

∣

∑

∣

∩

∣

−

⋯

(

−

)

−

∣

∩

⋯

∩

∣

| \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 |

$∣ i = 1 ⋃ n A_{i} ∣ = i = 1 \sum n ∣ A_{i} ∣ - i < j \sum ∣ A_{i} \cap A_{j} ∣ + i < j < k \sum ∣ A_{i} \cap A_{j} \cap A_{k} ∣ - \dots + (- 1)^{n - 1} ∣ A_{1} \cap A_{2} \cap \dots \cap A n ∣$

analysis :

$n$ After the union operation of sets , Element number , Usually use Principle of tolerance and exclusion Calculate ;

∑

∣

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

$\sum_{i = 1}^{n} ∣ A_{i} ∣$ : In each set Element number Add up , The value is greater than Total elements , Need to be corrected ; ( Coefficient value

(

−

)

(-1)^0

$(- 1)^{0}$ )

∑

∣

∩

∣

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

$\sum_{i < j} ∣ A_{i} \cap A_{j} ∣$ : Subtract the number of intersecting elements , This value is less than Total elements , Continue to make corrections ; ( Coefficient value

(

−

)

(-1)^1

$(- 1)^{1}$ )

∑

∣

∩

∣

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

$\sum_{i < j < k} ∣ A_{i} \cap A_{j} \cap A_{k} ∣$ : Add the number of elements intersected by the three sets , The value is greater than Total elements , Continue to make corrections ; ( Coefficient value

(

−

)

(-1)^2

$(- 1)^{2}$ )

Subtract the number of elements intersected by the four sets , The value is less than Total elements , Continue to make corrections ; ( Coefficient value

(

−

)

(-1)^3

$(- 1)^{3}$ )

⋮

\vdots

$⋮$

(

−

)

−

∣

∩

⋯

∩

∣

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

$(- 1)^{n - 1} ∣ A_{1} \cap A_{2} \cap \dots \cap A n ∣$ : add

(

−

)

−

( -1 )^{n - 1}

$(- 1)^{n - 1}$ multiply

−

n-1

$n - 1$ The number of elements intersected by sets ; ( Coefficient value

(

−

)

−

(-1)^{n-1}

$(- 1)^{n - 1}$ )

Above Odd sets Number of intersection elements The former coefficient is Positive numbers , Even number of sets Number of intersection elements The former coefficient is negative ;

Two 、 Principle of tolerance and exclusion Example

$1$ ~

10000

$10000$ Between , It is neither the square of an integer , It's not the cube of an integer , Number of ?

The complete :

$E$ A set is a complete set , yes

$1$ To

10000

$10000$ The natural number of ,

$E$ The number of sets

∣

10000

|E| = 10000

$∣ E ∣ = 10000$

The set of numbers corresponding to square

$A$ :

$A$ A set is Some number The square of Corresponding Some number aggregate ,

{

∈

∣

∧

∈

}

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

$A = {x \in E ∣ x = k^{2} \land k \in Z}$ ,

$A$ The number of set elements is

∣

100

∣

|100|

$∣ 100 ∣$ ;

10000

100^2 = 10000

$10 0^{2} = 10000$ , therefore

$A$ The elements of the set are

{

⋯

100

}

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

${0, 1, 2, \dots, 100}$ , The number of elements is

100

$100$ individual ;

⋯

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

$1^{2}, 2^{2}, 3^{3}, \dots, 10 0^{2}$ All in

$1$ To

10000

$10000$ Between ,

10201

101^2 = 10201

$10 1^{2} = 10201$ More than

10000

$10000$ 了 ;

The set of numbers corresponding to the cube

$B$ :

$B$ A set is Some number The cube of Corresponding Some number aggregate ,

{

∈

∣

∧

∈

}

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

$B = {x \in E ∣ x = k^{3} \land k \in Z}$ ,

$A$ The number of set elements is

∣

|21|

$∣ 21 ∣$ ;

9261

21^3 = 9261

$2 1^{3} = 9261$ , therefore

$B$ The elements of the set are

{

⋯

}

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

${0, 1, 2, \dots, 21}$ , The number of elements is

$21$ individual ;

⋯

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

$1^{3}, 2^{3}, 3^{3}, \dots, 2 1^{3}$ All in

$1$ To

10000

$10000$ Between ,

10648

22^2 = 10648

$2 2^{2} = 10648$ More than

10000

$10000$ 了 ;

Calculation

∩

A \cap B

$A \cap B$ Intersection of sets

$C$ : Element number , Is square , It's cubic again , It must be a number to the power of six ,

{

∈

∣

∧

∈

}

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

$C = {x \in E ∣ x = k^{6} \land k \in Z}$ ,

$C$ The number of elements in the set is

$4$ ;

4096

4^6 = 4096

$4^{6} = 4096$ , therefore

$C$ The elements of the set are

{

}

\{1, 2 , 3, 4\}

${1, 2, 3, 4}$ , The number of elements is

$4$ individual ;

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

$1^{6}, 2^{6}, 3^{6}, 4^{6}$ All in

$1$ To

10000

$10000$ Between ,

625

5^6 = 15,625

$5^{6} = 15, 625$ More than

10000

$10000$ 了 ;

The title can be translated into : aggregate

$Z$ in , Neither belong to

$A$ aggregate , Have not belong to

$B$ aggregate The number of ;

aggregate

$A$ And aggregate

$B$ Union is

∪

A \cup B

$A \cup B$

The above union Of Absolute complement

∼

(

∪

)

\sim ( A \cup B )

$\sim (A \cup B)$ Element number

∣

∼

(

∪

)

∣

|\sim ( A \cup B ) |

$∣ \sim (A \cup B) ∣$ , It is the result required in the title ;

∣

∼

(

∪

)

∣

−

∣

∪

∣

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

$∣ \sim (A \cup B) ∣ = ∣ E ∣ - ∣ A \cup B ∣$

In the above formula ,

∣

10000

|E| = 10000

$∣ E ∣ = 10000$ ,

∣

∪

∣

|A \cup B|

$∣ A \cup B ∣$ Value can be used Principle of tolerance and exclusion Calculate ;

∣

∪

∣

|A \cup B|

$∣ A \cup B ∣$ The number of elements of the union of two sets , You can add the number of elements of two sets , Then subtract the number of elements of the intersection of two sets ;

∣

∪

∣

−

∣

∪

∣

100

−

117

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

$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cup B ∣ = 100 + 21 - 4 = 117$