Metraipolis › archive › dc_559bfbe6ed2e

Inclusion–exclusion principle — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-06T16:30:38.148Z
SHA-256 of the archived text: 2120a95110344dea40041ed464e2c66a5006ff8c28f2e7bffff71606a6f30ac4
Stable URL of this page: https://metraipolis.com/documento/dc_559bfbe6ed2e

How to cite

Inclusion–exclusion principle — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_559bfbe6ed2e (Metraipolis archive dc_559bfbe6ed2e, sha256 2120a95110344dea40041ed464e2c66a5006ff8c28f2e7bffff71606a6f30ac4)

BibTeX

@misc{dc559bfbe6ed2e,
  title = {Inclusion–exclusion principle — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_559bfbe6ed2e; sha256 2120a95110344dea40041ed464e2c66a5006ff8c28f2e7bffff71606a6f30ac4},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In combinatorics, the inclusion–exclusion principle (commonly referred to as PIE) is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as | A ∪ B | = | A | + | B | − | A ∩ B | {\displaystyle |A\cup B|=|A|+|B|-|A\cap B|} where A and B are two finite sets and |S| indicates the cardinality of a set S (which may be considered as the number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The double-counted elements are those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection. The inclusion-exclusion principle, being a generalization of the two-set case, is perhaps more clearly seen in the case of three sets, which for the sets A, B and C is given by | A ∪ B ∪ C | = | A | + | B | + | C | − | A ∩ B | − | A ∩ C | − | B ∩ C | + | A ∩ B ∩ C | {\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|} This formula can be verified by counting how many times each region in the Venn diagram figure is included in the right-hand side of the formula. In this case, when removing the contributions of over-counted elements, the number of elements in the mutual intersection of the three sets has been subtracted too often, so must be added back in to get the correct total. Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of n sets: Include the cardinalities of the sets. Exclude the cardinalities of the pairwise intersections. Include the cardinalities of the triple-wise intersections. Exclude the cardinalities of the quadruple-wise intersections. Include the cardinalities of the quintuple-wise intersections. Continue, until the cardinality of the n-tuple-wise intersection is included (if n is odd) or excluded (n even). The name comes from the idea that the principle is based on over-generous inclusion, followed by compensating exclusion. This concept is attributed to Abraham de Moivre (1718), although it first appears in a paper of Daniel da Silva (1854) and later in a paper by J. J. Sylvester (1883). Sometimes the principle is referred to as the formula of Da Silva or Sylvester, due to these publications. The principle can be viewed as an example of the sieve method extensively used in number theory and is sometimes referred to as the sieve formula. As finite probabilities are computed as counts relative to the cardinality of the probability space, the formulas for the principle of inclusion–exclusion remain valid when the cardinalities of the sets are replaced by finite probabilities. More generally, both versions of the principle can be put under the common umbrella of measure theory. In a very abstract setting, the principle of inclusion–exclusion can be expressed as the calcul

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Probability theory»).
Fonte: Wikipedia in inglese, voce «Inclusion–exclusion principle» — https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
Wikidata Q849335 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q849335
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1369587686, consultata il 2026-10-06T15:17:36.692Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: e9f92065081148349248c46d0d86163a4751a317537d45915303070e042723e5