求容斥定理的英文简介

求容斥定理的英文简介
求容斥定理的英文简介

求容斥定理的英文简介

inclusion-exclusion formula 

Sk

Let A1, A1, …, An be n sets in a universe U of N elements.  Let: 

S1 = |A1| + |A2| + …+ |An|

S2 = |A1 A2| + |A1 A3| + …+ |An-1 An|, i.e., the size of all AiAj for i  j.

Sk = |A1 A2 …Ak| + |A1 A2 …Ak+1| + …+ |An-k+1 An-k+2 … An-1An|, i.e., the sizes of all k-ary intersections of the sets.

How many terms are there in S1 , S2 , Sn , Sk?

A formula for the # of elements in none of the sets is:

| A1 A2 …An | = N - S1 + S2 - S3 + …+(-1)n Sn 

Proof

We show that the formula counts each element in: 

none of the sets once

1 or more of the sets a net of 0 times.

Case: An element that is in none.

Such an element is added once in the 1st term: N

Since this element is in none of the Ais, it is in none of the Si, thus is counted a net of 1 time. 

Case: An element is in exactly 1 of the Ais.

It is added once in the 1st term, N. 

It is subtracted once in S1.  

It is in no other term, thus is counted a net of 0.

Case: An element is in exactly 2 of the Ais.

It is added once in the 1st term, N. 

It is subtracted twice in S1. 

It is added once in S2.  

It is in no other term, thus is counted a net of 0 times.

Case: An element is in exactly k of the Ais.

It is added once in the 1st term, N. 

It is subtracted C(k, 1) times in S1. 

It is added C(k,2) times in S2.  

It is subtracted C(k,3) times in S3.  . . .

An element in exactly k sets cannot be in any intersection of more than k of the Ais.

The net count for such an element is:

This binomial sum equals (1 + x)k, for x = -1.

Thus, its value is exactly 0.

In general, the formula counts elements in 1 or more of the sets exactly 0 times.

|A1 + A2 +. . .+ An| = S1 - S2 + S3 - S1 - ...+ (-1)n-1Sn.

Proof:

A1 + A2 +. . .+ An = U -  A1 A2 …An 

Thus, a count is: 

   N - [N - S1 + S2 - S3 + …+(-1)n Sn]

   = S1 - S2 + S3 - S1 - ...+ (-1)n-1Sn. 

To use inclusion-exclusion to count the elements of a set that has: 

property 1 and property 2 and … and property n

 Define: 

A1 as the set of elements that do not have property 1

A2 as the set of elements that do not have property 2

etc.

Then, A1 A2 …An is the set of all elements that have property 1 and property 2 and … and property n.

To use inclusion-exclusion to count the elements of a set that has: 

property 1 or property 2 or … or property n

 Define: 

A1 as the set of elements that have property 1

A2 as the set of elements that have property 2, etc.

Then, A1 + A2 +. . .+ An is the set of all elements that have property 1 or property 2 or … or property n. 

最后的公式应该在中间三行空行处