 output.to from Sideway
Draft for Information Only

# Content

`Probability The Inclusion-Exclusion Principle`

# Probability

## The Inclusion-Exclusion Principle

For a given 𝑁 objects, suppose that some of these objects have property 𝛼, and some do not. Let 𝑁(𝛼) denote the number having property 𝛼. Similarly, suppose that some of the objects have property 𝛽, and some do not. Let 𝑁(𝛽) denote the number having property 𝛽. If there are other properties 𝛾, 𝛿, ⋯, let 𝑁(𝛾), 𝑁(𝛿), ⋯ denote the number of objects having property 𝛾, the number having property 𝛿, ⋯.

Continuing the general analysis, let 𝑁(𝛼,𝛽) denote the number of objects having both properties 𝛼 and 𝛽. Let 𝑁(𝛼,𝛽,𝛾) denote the number of objects having the three properties 𝛼, 𝛽 and 𝛾. In the same way 𝑁(𝛼,𝛽,𝛾,𝛿) denotes the number of objects having the four properties 𝛼, 𝛽, 𝛾 and 𝛿.

Therefore, the 𝑁 objects that do not have property 𝛼 is equal to 𝑁−𝑁(𝛼). And the 𝑁 objects that do not have neither the property 𝛼 and 𝛽 is equal to 𝑁−𝑁(𝛼)−𝑁(𝛽)+𝑁(𝛼,𝛽). And the 𝑁 objects that do not have the properties 𝛼, 𝛽, and 𝛾 is equal to 𝑁−𝑁(𝛼)−𝑁(𝛽)−𝑁(𝛾)+𝑁(𝛼,𝛽)+𝑁(𝛼,𝛾)+𝑁(𝛽,𝛾)−𝑁(𝛼,𝛽,𝛾). ```Inclusion-exclusion principleThe number of objects having none of the properties 𝛼, 𝛽, 𝛾, ⋯  𝑁 −𝑁(𝛼)−𝑁(𝛽)−𝑁(𝛾)−⋯ +𝑁(𝛼,𝛽)+𝑁(𝛼,𝛾)+𝑁(𝛽,𝛾)+⋯ −𝑁(𝛼,𝛽,𝛾)−⋯ ⋮```

Consider an object, 𝑇, that has exactly 𝑗 of the properties, where 𝑗 is some positive integer. 𝑇 is counted by the term 𝑁. And −𝑁(𝛼)−𝑁(𝛽)−𝑁(𝛾)−⋯ object 𝑇 is counted 𝑗 times, or what is the same thing, 𝐶(𝑗,1) times. And +𝑁(𝛼,𝛽)+𝑁(𝛼,𝛾)+𝑁(𝛽,𝛾)+⋯ object 𝑇 is counted 𝐶(𝑗,2), because this is the number of terms with two of the 𝑗 properties of 𝑇. Similarly the numbers of terms with other combination of 𝑗 properties are 𝐶(𝑗,3), 𝐶(𝑗,4), ⋯ ```Inclusion-exclusion principleThe number of objects having none of the 𝑗 properties 1−𝐶(𝑗,1)+𝐶(𝑗,2)−𝐶(𝑗,3)+𝐶(𝑗,4)−+⋯=0```

ID: 190500012 Last Updated: 12/5/2019 Revision: 0 Ref: References

1. B. Joseph, 1978
2. Wheatstone, C., 1854
3. Stroud, K.A., 2001
4. Coolidge, J.L., 1949  Home 5

Management

HBR 3

Information

Recreation

Culture

Chinese 1097

English 337

Computer

Hardware 149

Software

Application 187

Numeric 19

Programming

Web 757

CSS 1

HTML

Knowledge Base

OS 389

MS Windows

Knowledge

Mathematics

Algebra 20

Geometry 18

Calculus 67

Engineering

Mechanical

Rigid Bodies

Statics 92

Dynamics 37

Control

Physics

Electric 10