| 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| 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 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: 1.
* Include the cardinalities of the sets. 2.
* Exclude the cardinalities of the pairwise intersections. 3.
* Include the cardinalities of the triple-wise intersections. 4.
* Exclude the cardinalities of the quadruple-wise intersections. 5.
* Include the cardinalities of the quintuple-wise intersections. 6.
* 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 calculation of the inverse of a certain matrix. This inverse has a special structure, making the principle 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." (en)
- 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, principle of inclusion and exclusion, Principle of inclusion-exclusion, PIE）あるいは包含と排除の原理とは、数え上げ組合せ論における基本的な結果のひとつ。特別な場合には「有限集合 A と B の和集合に属する元の数を計算するには、まずそれぞれに属する元の数 |A| と |B| を足しあわせた後、それらの共通部分に属する元の数 |A ∩ B| を引き去ればよい」というものである。つまり単に数え上げた後で重複を取り除くことに相当する。 以上の2つの有限集合 A, B に対する包除原理は次のように表せる。 同様に、3つの有限集合 A, B, C に対する包除原理は次のように表せる。 一般に、 n 個の有限集合 A1, ..., An が与えられたとき、その和集合に属する元の数は と表せる。ただし、ここで [n] = {1, 2, …, n} とした。 この原理の名称は、あらゆるものを「含め」、その後で「取り除いて」補正をするという考え方に基づいていることからきている。n > 2 のとき、共通部分の補正項を計算するのが非常に困難になることもある。また、公式には符号が交互にあらわれる。 この公式はアブラーム・ド・モアブルによるものと考えられているが、ジェームス・ジョセフ・シルベスターまたはアンリ・ポアンカレによるとも言われる。 (ja)
- 조합론에서 포함배제의 원리(包含排除의原理, 영어: inclusion–exclusion principle)는 유한 집합의 합집합의 원소 개수를 세는 기법이다. 조합론에서 널리 쓰이는 근본적인 기법이며, 이에 대하여 조합론자 잔카를로 로타는 다음과 같이 평했다. (ko)
- In de combinatoriek (combinatorische wiskunde), de getaltheorie en de stochastiek, is het principe van inclusie en exclusie (ook principe van insluiting en uitsluiting) een teltechniek om het aantal elementen in de vereniging van meerdere eindige verzamelingen te bepalen. Het principe is een generalisatie van de bekende methode om het aantal elementen in de vereniging van twee eindige verzamelingen en te bepalen. Daarvoor geldt: waarin het aantal elementen van de eindige verzameling aangeeft. De formule toont aan dat de som van de aantallen elementen van beide verzamelingenmogelijk te groot is, doordat de gemeenschappelijke elementen tweemaal geteld worden. De dubbelgetelde elementen zijn die in de doorsnede van de twee verzamelingen en de telling wordt gecorrigeerd door de grootte van de doorsnede van het resultaat af te trekken. Het principe is gemakkelijker te begrijpen in het geval van drie verzamelingen. Het principe wordt voor de verzamelingen en gegeven door Deze formule kan worden geverifieerd door te tellen hoe vaak elke regio in het plaatje van het venndiagram hiernaast wordt meegeteld aan de rechterzijde van deze formule. Merk op dat als het aantal elementen in de paarsgewijze doorsneden van de drie verzamelingen (respectievelijk van en van en en van en ) afgetrokken wordt van de kardinaliteiten van en te veel wordt afgetrokken. De drievoudige doorsnede van alle drie de verzamelingen en moet er weer bij opgeteld worden om het juiste resultaat te krijgen. Het generaliseren van de resultaten van deze voorbeelden geeft het principe van insluiting en uitsluiting. Ga als volgt te werk om de kardinaliteit van de vereniging van verzamelingen te vinden: 1.
* Sluit de kardinaliteiten van de verzamelingen in. 2.
* Sluit de kardinaliteiten van de paarsgewijze doorsneden uit. 3.
* Sluit de kardinaliteiten van de tripelgewijze doorsneden in. 4.
* Sluit de kardinaliteiten van de viervoudige doorsneden uit. 5.
* Sluit de kardinaliteiten van de vijfvoudige doorsneden in. 6.
* Ga door totdat de kardinaliteit van de -tupelgewijze doorsneden is ingesloten (als oneven is) of is uitgesloten (als even is). (nl)
- In matematica ed in particolare nella teoria degli insiemi, il principio di inclusione-esclusione è un'identità che mette in relazione la cardinalità di un insieme, espresso come unione di insiemi finiti, con le cardinalità di intersezioni tra questi insiemi. Denotiamo con la cardinalità di un insieme e consideriamo una famiglia finita di insiemi finiti: .Per la cardinalità dell'unione di tale famiglia si ha Rappresentazione con un diagramma di Eulero-Venn del caso per tre insiemi Nel caso la formula si riduce a quella, molto intuitiva e ricavabile dalle definizioni, esprimibile come Nel caso il principio si esprime con l'uguaglianza Questa si dimostra servendosi più volte della precedente e della distributività della intersezione rispetto alla unione: (it)
- 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)
- Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре. Например, в случае двух множеств формула включений-исключений имеет вид: В сумме элементы пересечения учтены дважды, и чтобы компенсировать это мы вычитаем из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа. Таким же образом и в случае множеств процесс нахождения количества элементов объединения состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы. (ru)
- Формула включень-виключень (або принцип включень-виключень) — комбінаторна формула, що дозволяє визначити потужність об'єднання скінченного числа скінченних множин, які в загальному випадку можуть перетинатися один з одним. Наприклад, у випадку двох множин та формула включень-виключень має вигляд: У сумі елементи перетину враховані двічі, тому віднімаємо з правої частини формули. Справедливість цього міркування видно з діаграми Ейлера-Венна для двох множин, яка наведена на малюнку праворуч. У випадку трьох множин A, B та C формула має вигляд: Ця формула може бути перевірена підрахунком того, скільки разів кожна область діаграми Ейлера-Венна використовується в правій частині формули. В цьому випадку, можна зауважити, що елементи перетину трьох множин будуть три рази враховані і три рази відняті, тому їх потрібно додати задля правильного підрахунку. Таким же чином і в разі множин процес знаходження кількості елементів об'єднання полягає у включенні всього, потім виключення зайвого, потім включенні помилково виключеного і так далі, тобто в чергуванні включення і виключення. Звідси і походить назва формули. (uk)
- 容斥原理又称排容原理，在組合數學裏，其說明若, ..., 為有限集，則 其中表示的基數。例如在兩個集的情況時，我們可以通過將和相加，再減去其交集的基數，而得到其并集的基數。 (zh)
|
| 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| を引き去ればよい」というものである。つまり単に数え上げた後で重複を取り除くことに相当する。 以上の2つの有限集合 A, B に対する包除原理は次のように表せる。 同様に、3つの有限集合 A, B, C に対する包除原理は次のように表せる。 一般に、 n 個の有限集合 A1, ..., An が与えられたとき、その和集合に属する元の数は と表せる。ただし、ここで [n] = {1, 2, …, n} とした。 この原理の名称は、あらゆるものを「含め」、その後で「取り除いて」補正をするという考え方に基づいていることからきている。n > 2 のとき、共通部分の補正項を計算するのが非常に困難になることもある。また、公式には符号が交互にあらわれる。 (ja)
- In matematica ed in particolare nella teoria degli insiemi, il principio di inclusione-esclusione è un'identità che mette in relazione la cardinalità di un insieme, espresso come unione di insiemi finiti, con le cardinalità di intersezioni tra questi insiemi. Denotiamo con la cardinalità di un insieme e consideriamo una famiglia finita di insiemi finiti: .Per la cardinalità dell'unione di tale famiglia si ha Rappresentazione con un diagramma di Eulero-Venn del caso per tre insiemi Nel caso la formula si riduce a quella, molto intuitiva e ricavabile dalle definizioni, esprimibile come (it)
- In de combinatoriek (combinatorische wiskunde), de getaltheorie en de stochastiek, is het principe van inclusie en exclusie (ook principe van insluiting en uitsluiting) een teltechniek om het aantal elementen in de vereniging van meerdere eindige verzamelingen te bepalen. Het principe is een generalisatie van de bekende methode om het aantal elementen in de vereniging van twee eindige verzamelingen en te bepalen. Daarvoor geldt: Het principe is gemakkelijker te begrijpen in het geval van drie verzamelingen. Het principe wordt voor de verzamelingen en gegeven door (nl)
- Формула включень-виключень (або принцип включень-виключень) — комбінаторна формула, що дозволяє визначити потужність об'єднання скінченного числа скінченних множин, які в загальному випадку можуть перетинатися один з одним. Наприклад, у випадку двох множин та формула включень-виключень має вигляд: У сумі елементи перетину враховані двічі, тому віднімаємо з правої частини формули. Справедливість цього міркування видно з діаграми Ейлера-Венна для двох множин, яка наведена на малюнку праворуч. У випадку трьох множин A, B та C формула має вигляд: (uk)
- Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре. Например, в случае двух множеств формула включений-исключений имеет вид: (ru)
|
