Sideway
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


ยฉsideway

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

close

References

  1. B. Joseph, 1978, University Mathematics: A Textbook for Students of Science & Engineering
  2. Wheatstone, C., 1854, On the Formation of Powers from Arithmetical Progressions
  3. Stroud, K.A., 2001, Engineering Mathematics
  4. Coolidge, J.L., 1949, The Story of The Binomial Theorem
close

Latest Updated LinksValid XHTML 1.0 Transitional Valid CSS!Nu Html Checker Firefox53 Chromena IExplorerna
IMAGE

Home 5

Business

Management

HBR 3

Information

Recreation

Hobbies 8

Culture

Chinese 1097

English 339

Reference 79

Computer

Hardware 249

Software

Application 213

Digitization 32

Latex 52

Manim 205

KB 1

Numeric 19

Programming

Web 289

Unicode 504

HTML 66

CSS 65

SVG 46

ASP.NET 270

OS 429

DeskTop 7

Python 72

Knowledge

Mathematics

Formulas 8

Algebra 84

Number Theory 206

Trigonometry 31

Geometry 34

Coordinate Geometry 2

Calculus 67

Complex Analysis 21

Engineering

Tables 8

Mechanical

Mechanics 1

Rigid Bodies

Statics 92

Dynamics 37

Fluid 5

Fluid Kinematics 5

Control

Process Control 1

Acoustics 19

FiniteElement 2

Natural Sciences

Matter 1

Electric 27

Biology 1

Geography 1


Copyright © 2000-2024 Sideway . All rights reserved Disclaimers last modified on 06 September 2019