The principle of tolerance is a principle for most people, because this fact is too obvious (for ordinary people). Think about it, the number of elements satisfying a certain condition-the number of elements satisfying two conditions+the number of elements satisfying three conditions. . . . . Obviously right.
So most people regard it as () principle, and then they are tortured to death by cancer questioners.
So this thing needs to be proved.
In fact, the principle of inclusion and exclusion is an inversion.
Because you use at least (more) the number of schemes that meet certain conditions to derive the number of schemes that just meet certain conditions.
Let f(sta) = the number of schemes that at least (more) satisfy the sta condition (sta is a set).
Let g(sta) = the number of schemes that just meet the sta condition (sta is a set).
If at least, then f (sta) = sigmag (ista) (ista &; sta = sta)
Then g (null) = f (null)-f (1)-f (2)-f (3) ...+f (1,2)+f (2,3) ...
This is obviously a lot, right? . . . . .
g(sta)= sigma((- 1)| tmp | * f(sta | tmp)，tmp &； sta = 0)
This is the basic form of the principle of inclusion and exclusion.
The remaining strange problem is its deformation.
It can be found that the above form is 2 n, which is very inefficient. . . . . .
(In fact, it is more widely used to subtract complement sets. . . . )
But the principles of inclusion and exclusion are not here. The principle is that the total (positive or negative) contribution of each element is 1. . . . . .
Type 1:
This is the principle of inclusion and exclusion deduced by ordinary people with common sense.
Generally, problems involving and excluding principles are of this type.
In fact, there is another way to understand the above formula:
alpha(k) = sigma( C(q，k) * g(q))
Then through binomial inversion, we can get:
g(k) = sigma( (- 1)q+k * C(q，k) * alpha(k))
This is the same.
Example:
Dyeing problem
Main idea
There is an n*m grid, and you have p colors. Each grid can be unpainted or painted with a P color. Meet the following conditions
1, draw a grid for each line.
2. Draw a grid for each column.
3. Use every color.
This problem is a very typical problem of the principle of inclusion and exclusion.
There are three different conditions, but each small identical condition is equivalent to each other.
1. Let a line be drawn as a condition without grid.
2. Set a list of conditions without drawing a grid as B ..
3. Suppose a color is not drawn as a C condition.
g(a，b，c)=(- 1)a *( 1)b *( 1)c * alpha(a，b，c)
alpha(a，b，c) = C(n，a) * C(m，b) * C(p，c) * (n*m)c+ 1
The answer is to find g (0,0,0)
Example 2:
Dyeing problem
Main idea
There are 2 n sets, and each set only contains [1, n], which are different from each other. Ask how many selection methods (at least one) are available to make the intersection size of these sets k.
The last question seems understandable in the way of ordinary people, but many people will not do it if they just meet K conditions. In fact, they just want to ask for g(k).
g(k) = alpha(k) - C(k+ 1，k) * alpha(k+ 1)…
Alpha (k) = c (n, k) * (22 (n-k)- 1) (csdn cannot be used to supply power to a power supply set. . . )
In fact, the deeper essence of the principle of inclusion and exclusion is to eliminate duplication and combine the answers of a function with simple inclusion and exclusion coefficients.
Therefore, under the above circumstances, this is a common model of inclusion and exclusion principles. If it is more widely used, it is necessary to use inclusion and exclusion coefficients flexibly.
It is necessary to study different exclusion coefficient models, but these models are all based on the set exclusion principle. Whether using conditional number exclusion or set exclusion, the right answer is the last word. . . . . . .
It should be understood that the inclusion-exclusion coefficient is constructed so that each element only contributes the value it should contribute.
In the above generalized inclusion principle, every element that meets the P condition contributes to Sigma (-1) k * c (p, k)) to g(0).
The value of this formula is 1 when p=0, and 0 at other times.
Then the contribution to g(q) is the same: sigma ((- 1) k-q * c (p, k) * c (k, q)) = sigma ((- 1) k-q * c (p-q, k-q)).
This is also 1 when p=q, and 0 at other times.
This is another way to understand the principles of inclusion and exclusion.
At present, we have two methods to calculate the inclusion-exclusion coefficient. The first is to eliminate duplication directly, and the second is to construct the inclusion exclusion coefficient.