Inclusion–exclusion principle (original) (raw)
Inkluziveco-ekskluda principo estas regulo de kombinatoriko, kiu ebligas kalkuli nombrojn de elementoj de kunaĵo de aroj. Aŭtoro probable estas eĉ iufoje estas nomata el nomoj de matematistoj kaj
| Property | Value | ||||||
|---|---|---|---|---|---|---|---|
| dbo:abstract | En combinatòria, el principi d'inclusió-exclusió permet expressar el nombre d'elements (o cardinal) d'una unió finita de conjunts finits en funció del nombre d'elements d'aquests conjunts i de les seves interseccions. Es tradueix directament en termes de probabilitats. S'atribueix al matemàtic Abraham De Moivre, tot i que va ser formulat per primera vegada pel matemàtic portuguès Daniel Augusto da Silva (1814-1878) i va ser generalitzat per Camille Jordan, i es coneix també (ell o la seva versió probabilista) sota el nom de fórmula del garbell de Poincaré, fórmula de Poincaré, o fórmula del garbell. (ca) Princip inkluze a exkluze popisuje vztah mezi velikostí sjednocení nějakých množin a velikostmi všech možných průniků těchto množin. Představme si úlohu, máme čísla 1 až 1000, kolik z nich je dělitelných dvěma nebo třemi? (jsou to 2, 3, 4, 6, 8, 9, 10 ...) Můžeme vzít sudá čísla (500) a přičíst k ním násobky trojky (333), ale pozor – čísla 6 nebo 12 jsme započítali dvakrát! Princip inkluze a exkluze nám říká, že počet prvků ve sjednocení dvou množin je součet počtu prvků v každé z nich, minus počet prvků, které jsou v obou. . Tedy výsledek = počet čísel dělitelných dvěma (500) + počet čísel dělitelných třemi (333) – počet čísel dělitelných šesti (166) = 667. Podobně pro 3 množiny A, B a C, . Obecně, každý soubor konečných množin platí (cs) Das Prinzip von Inklusion und Exklusion (auch Prinzip der Einschließung und Ausschließung oder Einschluss-Ausschluss-Verfahren) ist eine zur Bestimmung der Mächtigkeit einer Menge hilfreiche Technik. Sie findet vor allem in der Kombinatorik, der Zahlentheorie und der Stochastik Anwendung. Das Prinzip drückt dazu die Kardinalität einer Ursprungsmenge durch die Kardinalitäten ihrer Teilmengen aus. Diese sind in aller Regel einfacher zu bestimmen. Namensgebend ist dabei das Vorgehen, bei dem zunächst durch die Summe der Größen nicht notwendigerweise disjunkter Teilmengen die Größe von von oben abgeschätzt wird (Inklusion), anschließend jedoch durch die Subtraktion der Größe des gemeinsamen Schnittes der Teilmengen dies wieder zu korrigieren versucht wird (Exklusion). (de) Inkluziveco-ekskluda principo estas regulo de kombinatoriko, kiu ebligas kalkuli nombrojn de elementoj de kunaĵo de aroj. Aŭtoro probable estas eĉ iufoje estas nomata el nomoj de matematistoj kaj (eo) En combinatoria, el principio de inclusión-exclusión (conocido también como principio de la criba) permite calcular el cardinal de la unión de varios conjuntos, mediante los cardinales de cada uno de ellos y todas sus posibles intersecciones. Si A1, ..., An son conjuntos finitos entonces: donde |A | denota el cardinal de A. Una escritura más rigurosa pero menos legible es: Tomando n=2 tenemos un caso de doble conteo, podemos hallar el tamaño de la unión de dos conjuntos A y B sumando | A | y | B | y restando el tamaño de su intersección. El nombre proviene de la idea en la que el principio se basa: una muy generosa inclusión seguida de una compensadora exclusión. Si n>2 la exclusión de las parejas de intersecciones es (tal vez) demasiado rigurosa y la fórmula correcta es como se muestra, con signos alternados. Esta fórmula se atribuye a Abraham de Moivre aunque a veces se la asocia con o Henri Poincaré. El gráfico de la derecha ilustra el caso de tres conjuntos A, B y C. Pero no se puede utilizar en ciertas veces. (es) Hainbat gertakizunen bilketak bilketan barneratzen diren gertakizunetako bat gutxienez gertatzea adierazten du. Gertakizunak (edo) ikurraren bitartez lotuz adierazten da bilketa. Bilketa baten probabilitatea kalkulatzeko erregela ezberdina da gertakizunak bateragarriak diren edo ez. Bateragarritasun kontzeptuari buruz gehiago jakiteko, ikus Gertakizun. (eu) In combinatorics, a branch of 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 as where A and B are two finite sets and | S |
| dbo:thumbnail | wiki-commons:Special:FilePath/Венов_дијаграм.svg?width=300 | ||||||
| dbo:wikiPageExternalLink | http://www.crcpress.com/product/isbn/9781420082609 | ||||||
| dbo:wikiPageID | 342684 (xsd:integer) | ||||||
| dbo:wikiPageLength | 38576 (xsd:nonNegativeInteger) | ||||||
| dbo:wikiPageRevisionID | 1118939661 (xsd:integer) | ||||||
| dbo:wikiPageWikiLink | dbr:Probability_space dbr:Rook_(chess) dbr:Element_(mathematics) dbr:J._J._Sylvester dbr:Binomial_coefficient dbr:Binomial_theorem dbr:De_Morgan's_law dbc:Enumerative_combinatorics dbr:Perfect_matching dbr:Permutation dbr:De_Morgan's_laws dbr:Derangement dbr:Incidence_algebra dbr:Random_permutation_statistics dbc:Articles_containing_proofs dbr:Mathematics dbr:Measurable dbr:Measure_theory dbr:Chromatic_polynomial dbr:Function_(mathematics) dbr:Gian-Carlo_Rota dbr:Multiset dbr:Möbius_inversion_formula dbr:SIAM_Journal_on_Computing dbr:Arithmetic_function dbr:Sieve_of_Eratosthenes dbr:Combination dbr:Combinatorics dbr:Measure_space dbc:Mathematical_principles dbc:Probability_theory dbr:Abraham_de_Moivre dbr:Daniel_da_Silva_(mathematician) dbr:Expected_value dbr:Finite_set dbr:Number_theory dbr:Partially_ordered_set dbr:Partition_of_a_set dbr:Cardinality dbr:Checkerboard dbr:Family_of_sets dbr:Even_and_odd_numbers dbr:Probability dbr:Intersection_(set_theory) dbr:Taylor_series dbr:Nearest_integer_function dbr:Prime_number dbr:Bijection dbr:Bipartite_graph dbr:Surjective_function dbr:Coefficient dbr:Boole's_inequality dbr:Positive_integer dbr:Positive_number dbr:Square-free_integer dbr:Indicator_function dbr:Natural_number dbr:Negative_number dbr:Ordered_set dbr:Set_(mathematics) dbr:Sieve_theory dbr:Union_(set_theory) dbr:Venn_diagram dbr:Viggo_Brun dbr:Universal_set dbr:Image_(mathematics) dbr:Stirling_numbers_of_the_second_kind dbr:Sides_of_an_equation dbr:Subset dbr:Springer-Verlag dbr:Falling_factorial dbr:Independent_and_identically_distributed dbr:Relatively_prime dbr:Lebesgue_integral dbr:Prime_factorization dbr:Generating_polynomial dbr:Subfactorial dbr:Without_any_loss_of_generality dbr:File:Inclusion-exclusion-3sets.png dbr:File:Inclusion-exclusion.svg dbr:File:Венов_дијаграм.svg | ||||||
| dbp:id | 2803 (xsd:integer) p/i050430 (en) | ||||||
| dbp:proof | Substitute on the right hand side of . Notice that appears once on both sides of . So we must show that for all with , the terms cancel out on the right hand side of . For that purpose, take a fixed such that and take an arbitrary fixed such that . Notice that must be a set for each positive or negative appearance of on the right hand side of that is obtained by way of the multiset such that . Now each appearance of on the right hand side of that is obtained by way of such that is a set that contains cancels out with the one that is obtained by way of the corresponding such that is a set that does not contain . This gives the desired result. (en) | ||||||
| dbp:title | Proof of (en) Inclusion-and-exclusion principle (en) principle of inclusion–exclusion (en) | ||||||
| dbp:wikiPageUsesTemplate | dbt:Springer dbt:Annotated_link dbt:Citation dbt:Main dbt:Math dbt:Mvar dbt:NumBlk dbt:Reflist dbt:See_also dbt:Short_description dbt:EquationRef dbt:Math_proof dbt:Proof dbt:Closed-closed dbt:EquationNote dbt:PlanetMath_attribution | ||||||
| dct:subject | dbc:Enumerative_combinatorics dbc:Articles_containing_proofs dbc:Mathematical_principles dbc:Probability_theory | ||||||
| rdf:type | owl:Thing yago:WikicatMathematicalPrinciples yago:Abstraction100002137 yago:Cognition100023271 yago:Content105809192 yago:Generalization105913275 yago:Idea105833840 yago:Principle105913538 yago:PsychologicalFeature100023100 | ||||||
| rdfs:comment | Inkluziveco-ekskluda principo estas regulo de kombinatoriko, kiu ebligas kalkuli nombrojn de elementoj de kunaĵo de aroj. Aŭtoro probable estas eĉ iufoje estas nomata el nomoj de matematistoj kaj (eo) Hainbat gertakizunen bilketak bilketan barneratzen diren gertakizunetako bat gutxienez gertatzea adierazten du. Gertakizunak (edo) ikurraren bitartez lotuz adierazten da bilketa. Bilketa baten probabilitatea kalkulatzeko erregela ezberdina da gertakizunak bateragarriak diren edo ez. Bateragarritasun kontzeptuari buruz gehiago jakiteko, ikus Gertakizun. (eu) En combinatoire, le principe d’inclusion-exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d'une réunion finie d'ensembles finis en fonction du nombre d'éléments de ces ensembles et de leurs intersections. Il se généralise en termes de probabilités. Il est attribué au mathématicien Abraham de Moivre, et connu également (lui ou sa version probabiliste) sous le nom de formule du crible de Poincaré, formule de Poincaré, ou formule du crible. (fr) 조합론에서 포함배제의 원리(包含排除의原理, 영어: inclusion–exclusion principle)는 유한 집합의 합집합의 원소 개수를 세는 기법이다. 조합론에서 널리 쓰이는 근본적인 기법이며, 이에 대하여 조합론자 잔카를로 로타는 다음과 같이 평했다. (ko) O Princípio da Inclusão-Exclusão (PIE) é uma generalização de um dos princípios básicos de contagem, o princípio aditivo. Este princípio está interessado na obtenção de uma fórmula para contar o número de elementos que pertencem a união de vários conjuntos não necessariamente excludentes ou disjuntos. O princípio funciona basicamente somando-se e subtraindo-se correções à uma estimativa até que se chegue no valor desejado. Na sua forma mais simples calcula a cardinalidade da união de dois conjuntos A e B, no qual a intersecção entre A e B dá-se um conjunto vazio. (pt) I kombinatoriken ger principen om inklusion/exklusion ett sätt att räkna antalet element i en union av flera mängder. Principen är av stor nytta i många kombinatoriska problem, där man genom att införa rätt mängder kan reducera problemet till att beräkna antalet element i en union; se nedan. Pricipen säger att om är ändliga mängder så gäller att: där är antalet element i mängden . (sv) Zasada włączeń i wyłączeń – reguła kombinatoryczna, pozwalająca na określenie liczby elementów skończonej sumy mnogościowej skończonych zbiorów. Autorstwo zasady przypisywane jest zazwyczaj Abrahamowi de Moivre, chociaż bywa nazywana od nazwisk matematyków, Jamesa Josepha Sylvestera oraz Henriego Poincaré. (pl) 容斥原理又称排容原理，在組合數學裏，其說明若, ..., 為有限集，則 其中表示的基數。例如在兩個集的情況時，我們可以通過將和相加，再減去其交集的基數，而得到其并集的基數。 (zh) En combinatòria, el principi d'inclusió-exclusió permet expressar el nombre d'elements (o cardinal) d'una unió finita de conjunts finits en funció del nombre d'elements d'aquests conjunts i de les seves interseccions. Es tradueix directament en termes de probabilitats. (ca) Princip inkluze a exkluze popisuje vztah mezi velikostí sjednocení nějakých množin a velikostmi všech možných průniků těchto množin. Představme si úlohu, máme čísla 1 až 1000, kolik z nich je dělitelných dvěma nebo třemi? (jsou to 2, 3, 4, 6, 8, 9, 10 ...) Můžeme vzít sudá čísla (500) a přičíst k ním násobky trojky (333), ale pozor – čísla 6 nebo 12 jsme započítali dvakrát! Princip inkluze a exkluze nám říká, že počet prvků ve sjednocení dvou množin je součet počtu prvků v každé z nich, minus počet prvků, které jsou v obou. . Podobně pro 3 množiny A, B a C, . (cs) Das Prinzip von Inklusion und Exklusion (auch Prinzip der Einschließung und Ausschließung oder Einschluss-Ausschluss-Verfahren) ist eine zur Bestimmung der Mächtigkeit einer Menge hilfreiche Technik. Sie findet vor allem in der Kombinatorik, der Zahlentheorie und der Stochastik Anwendung. (de) En combinatoria, el principio de inclusión-exclusión (conocido también como principio de la criba) permite calcular el cardinal de la unión de varios conjuntos, mediante los cardinales de cada uno de ellos y todas sus posibles intersecciones. Si A1, ..., An son conjuntos finitos entonces: donde |A | denota el cardinal de A. Una escritura más rigurosa pero menos legible es: Esta fórmula se atribuye a Abraham de Moivre aunque a veces se la asocia con o Henri Poincaré. El gráfico de la derecha ilustra el caso de tres conjuntos A, B y C. Pero no se puede utilizar en ciertas veces. (es) In combinatorics, a branch of 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 as 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 Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of n sets: (en) 包除原理（ほうじょげんり、英: Inclusion-exclusion principle, principle of inclusion and exclusion, Principle of inclusion-exclusion, PIE）あるいは包含と排除の原理とは、数え上げ組合せ論における基本的な結果のひとつ。特別な場合には「有限集合 A と B の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 | A | と | B | を足しあわせた後、それらの共通部分に属する元の数 | A ∩ B |
| rdfs:label | Principi d'inclusió-exclusió (ca) Princip inkluze a exkluze (cs) Prinzip von Inklusion und Exklusion (de) Inkluziveco-ekskluda principo (eo) Principio de inclusión-exclusión (es) Bilketa (probabilitatea) (eu) Inclusion–exclusion principle (en) Principe d'inclusion-exclusion (fr) Principio di inclusione-esclusione (it) 포함배제의 원리 (ko) 包除原理 (ja) Principe van inclusie en exclusie (nl) Zasada włączeń i wyłączeń (pl) Princípio da inclusão-exclusão (pt) Формула включений-исключений (ru) Principen om inklusion/exklusion (sv) Формула включень-виключень (uk) 排容原理 (zh) | ||||||
| rdfs:seeAlso | dbr:Bonferroni_inequalities | ||||||
| owl:sameAs | freebase:Inclusion–exclusion principle wikidata:Inclusion–exclusion principle http://am.dbpedia.org/resource/ወጋኝ_አግላይ_መርህ dbpedia-ca:Inclusion–exclusion principle dbpedia-cs:Inclusion–exclusion principle dbpedia-de:Inclusion–exclusion principle dbpedia-eo:Inclusion–exclusion principle dbpedia-es:Inclusion–exclusion principle dbpedia-eu:Inclusion–exclusion principle dbpedia-fa:Inclusion–exclusion principle dbpedia-fi:Inclusion–exclusion principle dbpedia-fr:Inclusion–exclusion principle dbpedia-he:Inclusion–exclusion principle dbpedia-hu:Inclusion–exclusion principle dbpedia-it:Inclusion–exclusion principle dbpedia-ja:Inclusion–exclusion principle dbpedia-ko:Inclusion–exclusion principle dbpedia-nl:Inclusion–exclusion principle dbpedia-pl:Inclusion–exclusion principle dbpedia-pt:Inclusion–exclusion principle dbpedia-ru:Inclusion–exclusion principle dbpedia-sk:Inclusion–exclusion principle dbpedia-sl:Inclusion–exclusion principle dbpedia-sr:Inclusion–exclusion principle dbpedia-sv:Inclusion–exclusion principle dbpedia-th:Inclusion–exclusion principle dbpedia-uk:Inclusion–exclusion principle http://ur.dbpedia.org/resource/اصول_شمول_استشنا dbpedia-zh:Inclusion–exclusion principle https://global.dbpedia.org/id/516Pq | ||||||
| prov:wasDerivedFrom | wikipedia-en:Inclusion–exclusion_principle?oldid=1118939661&ns=0 | ||||||
| foaf:depiction | wiki-commons:Special:FilePath/Inclusion-exclusion-3sets.png wiki-commons:Special:FilePath/Inclusion-exclusion.svg wiki-commons:Special:FilePath/Венов_дијаграм.svg | ||||||
| foaf:isPrimaryTopicOf | wikipedia-en:Inclusion–exclusion_principle | ||||||
| is dbo:knownFor of | dbr:Abraham_de_Moivre | ||||||
| is dbo:wikiPageDisambiguates of | dbr:Exclusion_principle dbr:Inclusion | ||||||
| is dbo:wikiPageRedirects of | dbr:Principle_of_inclusion_and_exclusion dbr:Inclusion-exclusion_principle dbr:Inclusion-Exclusion_formula dbr:Inclusion-Exclusion_principle dbr:Inclusion-exclusion dbr:Inclusion-exclusion_theorem dbr:Inclusion_exclusion dbr:Inclusion_exclusion_principle dbr:Inclusion_exclusion_theorem dbr:Inclusion–exclusion dbr:Sieve_principle dbr:Sifting_argument dbr:Principle_Of_Inclusion_and_Exclusion dbr:Principle_of_Inclusion_and_Exclusion dbr:Principle_of_inclusion-exclusion dbr:Principle_of_inclusion-exclusion_proof dbr:Principle_of_inclusion_exclusion dbr:Diluted_inclusion-exclusion_principle dbr:Diluted_inclusion–exclusion_principle dbr:Exclusion-inclusion dbr:Exclusion-inclusion_principle | ||||||
| is dbo:wikiPageWikiLink of | dbr:Prime-counting_function dbr:Schuette–Nesbitt_formula dbr:Enumerative_combinatorics dbr:Ménage_problem dbr:Bernoulli_number dbr:Derangement dbr:Double_counting_(proof_technique) dbr:List_of_probability_topics dbr:Sieve_method dbr:Computing_the_permanent dbr:Möbius_inversion_formula dbr:Content_(measure_theory) dbr:Corestriction dbr:Sauer–Shelah_lemma dbr:Combinatorial_principles dbr:Deletion–contraction_formula dbr:Fundamental_lemma_of_sieve_theory dbr:Hamiltonian_path_problem dbr:Hammersley–Clifford_theorem dbr:Permanent_(mathematics) dbr:Principle_of_inclusion_and_exclusion dbr:Maximum-minimums_identity dbr:Addition_principle dbr:Truth_function dbr:H-vector dbr:Abraham_de_Moivre dbr:Daniel_da_Silva_(mathematician) dbr:Dramaturgy_(sociology) dbr:Euclid's_theorem dbr:Finite_set dbr:Cardinal_number dbr:History_of_combinatorics dbr:Project_Euler dbr:James_Joseph_Sylvester dbr:HyperLogLog dbr:Coherence_(philosophical_gambling_strategy) dbr:Turán_sieve dbr:Boole's_inequality dbr:Exclusion_principle dbr:Inclusion dbr:Brun_sieve dbr:Catalog_of_articles_in_probability_theory dbr:IEP dbr:Inclusion-exclusion_principle dbr:Necklace_problem dbr:Symmetric_difference dbr:Euler_characteristic dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Random_permutation dbr:Poisson_clumping dbr:Stirling_numbers_of_the_second_kind dbr:Probability_axioms dbr:Outline_of_combinatorics dbr:Professor_Tarantoga dbr:Selberg_sieve dbr:Inclusion-Exclusion_formula dbr:Inclusion-Exclusion_principle dbr:Inclusion-exclusion dbr:Inclusion-exclusion_theorem dbr:Inclusion_exclusion dbr:Inclusion_exclusion_principle dbr:Inclusion_exclusion_theorem dbr:Inclusion–exclusion dbr:Sieve_principle dbr:Sifting_argument dbr:Principle_Of_Inclusion_and_Exclusion dbr:Principle_of_Inclusion_and_Exclusion dbr:Principle_of_inclusion-exclusion dbr:Principle_of_inclusion-exclusion_proof dbr:Principle_of_inclusion_exclusion dbr:Diluted_inclusion-exclusion_principle dbr:Diluted_inclusion–exclusion_principle dbr:Exclusion-inclusion dbr:Exclusion-inclusion_principle | ||||||
| is dbp:knownFor of | dbr:Abraham_de_Moivre | ||||||
| is foaf:primaryTopic of | wikipedia-en:Inclusion–exclusion_principle |
