output.to from Sideway
Algebra

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

ยฉsideway

References

1. B. Joseph, 1978, University Mathematics: A Textbook for Students of Science & Engineering, Blackie & Son Limited, HongKong
2. Wheatstone, C., 1854, On the Formation of Powers from Arithmetical Progressions, Proceedings of The Royal Society of London, Vol 7, p145-151,, London
3. Stroud, K.A., 2001, Engineering Mathematics, Industrial Press, Inc, NY
4. Coolidge, J.L., 1949, The Story of The Binomial Theorem, The American Mathematical Monthly, Vol 56, No.3, Mar, pp147-157

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

Home (5)

Management

HBR (3)

Information

Recreation

Hobbies (7)

Culture

Chinese (1097)

English (336)

Reference (66)

Computer

Hardware (149)

Software

Application (187)

Digitization (24)

Numeric (19)

Programming

Web (644)

CSS (SC)

ASP.NET (SC)

HTML

Knowledge Base

Common Color (SC)

Html 401 Special (SC)

OS (389)

MS Windows

Windows10 (SC)

.NET Framework (SC)

DeskTop (7)

Knowledge

Mathematics

Formulas (8)

Number Theory (206)

Algebra (20)

Trigonometry (18)

Geometry (18)

Calculus (67)

Complex Analysis (21)

Engineering

Tables (8)

Mechanical

Mechanics (1)

Rigid Bodies

Statics (92)

Dynamics (37)

Fluid (5)

Control

Acoustics (19)

Biology (1)

Geography (1)