- Inclusion-exclusion principle
mathematics, the inclusion-exclusion principle (also known as the sieve principle) states that if "A"1, ..., "A""n" are finite sets, then
where |"A"| denotes the
cardinalityof the set "A". For example, taking "n" = 2, we get a special case of double counting; in words: we can count the size of the union of sets "A" and "B" by adding |"A"| and |"B"| and then subtracting the size of their intersection. The name comes from the idea that the principle is based on over-generous "inclusion", followed by compensating "exclusion". When "n" > 2 the exclusion of the pairwise intersections is (possibly) too severe, and the correct formula is as shown with alternating signs.
This formula is attributed to
Abraham de Moivre; it is sometimes also named for Joseph Sylvesteror Henri Poincaré.fact|date=October 2007
For the case of three sets "A", "B", "C" the inclusion-exclusion principle is illustrated in the graphic on the right.
Inclusion-exclusion principle in probability
probability, for events "A"1, ..., "A""n" in a probability space, the inclusion-exclusion principle becomes for "n" = 2
for "n" = 3
and in general
Wikimedia Foundation. 2010.
Look at other dictionaries:
Inclusion — For inclusion and exclusion of Wikipedia templates, see Wikipedia:Template inclusion. Inclusion may refer to: Contents 1 Metallurgy 2 Social inclusion of persons 3 Mathematics … Wikipedia
Combinatorial principles — In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used. The rule of sum, rule of product, and inclusion exclusion principle are often used for enumerative purposes.… … Wikipedia
Set (mathematics) — This article gives an introduction to what mathematicians call intuitive or naive set theory; for a more detailed account see Naive set theory. For a rigorous modern axiomatic treatment of sets, see Set theory. The intersection of two sets is… … Wikipedia
Bernoulli number — In mathematics, the Bernoulli numbers Bn are a sequence of rational numbers with deep connections to number theory. They are closely related to the values of the Riemann zeta function at negative integers. There are several conventions for… … Wikipedia
Derangement — For the psychological condition, see psychosis. Number of possible permutations and derangements of n elements. P(n) is the number of n permutations; D(n) is the number of derangements (n permutations where all of the n elements change their… … Wikipedia
Boole's inequality — In probability theory, Boole s inequality, named after George Boole, (also known as the union bound) says that for any finite or countable set of events, the probability that at least one of the events happens is no greater than the sum of the… … Wikipedia
Schuette–Nesbitt formula — In probability theory, the Schuette–Nesbitt formula is a generalization of the probabilistic version of the inclusion exclusion principle. It is named after Donald R. Schuette and Cecil J. Nesbitt. The Schuette–Nesbitt formula has practical… … Wikipedia
List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is … Wikipedia
Logical connective — This article is about connectives in classical logic. For connectors in natural languages, see discourse connective. For connectives and operators in other logics, see logical constant. For other logical symbols, see table of logic symbols. In… … Wikipedia
List of mathematics articles (I) — NOTOC Ia IA automorphism ICER Icosagon Icosahedral 120 cell Icosahedral prism Icosahedral symmetry Icosahedron Icosian Calculus Icosian game Icosidodecadodecahedron Icosidodecahedron Icositetrachoric honeycomb Icositruncated dodecadodecahedron… … Wikipedia