Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Inclusion–exclusion_principle> ?p ?o. }
Showing items 1 to 38 of
38
with 100 items per page.
- Inclusion–exclusion_principle abstract "In combinatorics (combinatorial mathematics), the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed aswhere 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 principle is more clearly seen in the case of three sets, which for the sets A, B and C is given by 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, i. include the cardinalities of the sets, ii. exclude the cardinalities of the pairwise intersections, iii. include the cardinalities of the triple-wise intersections, iv. exclude the cardinalities of the quadruple-wise intersections, v. include the cardinalities of the quintuple-wise intersections, vi. and 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); but 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 is an example of the sieve method extensively used in number theory and is sometimes referred to as the sieve formula, though Legendre already used a similar device in a sieve context in 1808.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 probabilites. 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 amounts to no more than the calculation of the inverse of a certain matrix. From this point of view, there is nothing mathematically interesting about the principle. However, the wide applicability of the principle makes it an extremely valuable technique in combinatorics and related areas of mathematics. As Gian-Carlo Rota put it:"One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusion–exclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem."".
- Inclusion–exclusion_principle thumbnail Venn-diagram-AB.svg?width=300.
- Inclusion–exclusion_principle wikiPageID "342684".
- Inclusion–exclusion_principle wikiPageRevisionID "594524993".
- Inclusion–exclusion_principle id "2803".
- Inclusion–exclusion_principle id "p/i050430".
- Inclusion–exclusion_principle title "Inclusion-and-exclusion principle".
- Inclusion–exclusion_principle title "principle of inclusion–exclusion".
- Inclusion–exclusion_principle subject Category:Articles_containing_proofs.
- Inclusion–exclusion_principle subject Category:Enumerative_combinatorics.
- Inclusion–exclusion_principle subject Category:Mathematical_principles.
- Inclusion–exclusion_principle subject Category:Probability_theory.
- Inclusion–exclusion_principle comment "In combinatorics (combinatorial mathematics), the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed aswhere 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).".
- Inclusion–exclusion_principle label "Inclusion–exclusion principle".
- Inclusion–exclusion_principle label "Principe d'inclusion-exclusion".
- Inclusion–exclusion_principle label "Principio de inclusión-exclusión".
- Inclusion–exclusion_principle label "Principio di inclusione ed esclusione".
- Inclusion–exclusion_principle label "Princípio da inclusão-exclusão".
- Inclusion–exclusion_principle label "Prinzip von Inklusion und Exklusion".
- Inclusion–exclusion_principle label "Zasada włączeń i wyłączeń".
- Inclusion–exclusion_principle label "Формула включений-исключений".
- Inclusion–exclusion_principle label "包除原理".
- Inclusion–exclusion_principle label "排容原理".
- Inclusion–exclusion_principle sameAs Inclusion%E2%80%93exclusion_principle.
- Inclusion–exclusion_principle sameAs Princip_inkluze_a_exkluze.
- Inclusion–exclusion_principle sameAs Prinzip_von_Inklusion_und_Exklusion.
- Inclusion–exclusion_principle sameAs Principio_de_inclusión-exclusión.
- Inclusion–exclusion_principle sameAs Bilketa_(probabilitatea).
- Inclusion–exclusion_principle sameAs Principe_d'inclusion-exclusion.
- Inclusion–exclusion_principle sameAs Principio_di_inclusione_ed_esclusione.
- Inclusion–exclusion_principle sameAs 包除原理.
- Inclusion–exclusion_principle sameAs 포함-배제의_원리.
- Inclusion–exclusion_principle sameAs Zasada_włączeń_i_wyłączeń.
- Inclusion–exclusion_principle sameAs Princípio_da_inclusão-exclusão.
- Inclusion–exclusion_principle sameAs Q849335.
- Inclusion–exclusion_principle sameAs Q849335.
- Inclusion–exclusion_principle wasDerivedFrom Inclusion–exclusion_principle?oldid=594524993.
- Inclusion–exclusion_principle depiction Venn-diagram-AB.svg.
