Talk:Inclusion–exclusion principle

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Old discussion

GRRRRRRRRRRRRRRRRRRRRRRRR

GRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR ARGH ARGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH — Preceding unsigned comment added by 2604:3D09:1580:9600:34FB:9537:7F0C:5963 (talk) 21:57, 29 March 2022 (UTC)[reply]

QUOTE

"... is an equation relating the sizes of two sets and their union. It states that if A and B are two (finite) sets, then

   |A \cup B| = |A| + |B| - |A \cap B|. \,

The meaning of the statement is that the number of elements in the union of the two sets is the sum of the elements in each set, respectively, minus the number of elements that are in both. Similarly, for three sets A, B and C," ENDQUOTE

Sets don't have a size, they have a number of members - also known as cardinality, the cardinality of the union of two sets is NOT the sum of the elements in each set.... that would give another set, not a number. Mathematics is the area above all of human achievement where clarity of thought is most necessary and most refined. Who are the people who take it upon themselves to write articles about mathematical subjects, when they don't have the ability to distinguish the elements of the set from the number of those elements. Many many articles in the encyclopedia suffer from this kind of ineptness. If they stopped and left it to those better equipped the article count would increase more slowly, yet the readers would be more enlightened, there would be more silk purses and there would be fewer sows ears.

— Preceding unsigned comment added by 82.0.89.176 (talk) 23:30, 7 February 2013 (UTC)[reply]

This is very confusing. How about some examples.

agreed - examples of probability calculations would be very helpful New Thought (talk) 13:43, 25 March 2009 (UTC)[reply]

I added an example for the overall principle of inclusion / exclusion based on a deck of cards. Someone might want to add internal links. Antares5245 (talk) 02:22, 15 May 2009 (UTC)[reply]

The new section repeatedly had

-1^{p}\,

where

(-1)^{p}\,

appeared to be intended. Those are of course two different things. I hope I've fixed all of those. Michael Hardy (talk) 02:41, 15 May 2009 (UTC)[reply]

You are correct, thank you. Antares5245 (talk) 02:46, 15 May 2009 (UTC)[reply]

The way the formula is written at the moment, doesn't, $\sum _{i,j\,:\,i\neq j}\left|A_{i}\cap A_{j}\right|$ count everything twice (and so on for the other terms)? Would it be correct to write it as $\sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|$ ? I think I don't understand this well enough to change the article...

Note the sign changes --CSTAR 19:18, 5 Jun 2005 (UTC)

The notation $\sum _{i,j\,:\,i\neq j}\left|A_{i}\cap A_{j}\right|$ in this context does not mean the set of all ordered pairs (i,j). It does not say $\sum _{i}\sum _{j}$ , i.e. we don't have j running from 1 through n separately for each fixed value of i. Michael Hardy 01:48, 6 Jun 2005 (UTC)

Ah, I entirely missed the point of the reader's confusion.--CSTAR

Horrifically obtuse

This proof is horrifically obtuse - is there a more intuitive (but still algebraic) one?

Suppose the point i is in k of the sets. The first term counts it k times, the second subtracts it ${k \choose 2}$ times, the third adds it ${k \choose 3}$ times, and so on. So the total number of times it is counted is

k-{k \choose 2}+{k \choose 3}-\cdots

which is the binomial expansion for $1-(1-1)^{k}=1$ . Thus, each point is counted exactly once. Is that clearer? McKay 04:55, 30 May 2006 (UTC)[reply]

I would say that in the actual version of the article there is only a equivalent formulation of the problem but no proof. Above there is correctly given a proof for the inclusion-exclusion formula. Alternatively one can argue as follows.

For any i in the union we have that the number of terms involving

A_{i}

which are even is one less to the number of terms involving

A_{i}

which are odd. The combinatorial proof just says that the numbers of even and odd subesets of any set is the same. So this is in principle exactly the above calculation where the term for the empty set (i.e.

{k \choose 0}

) is not there.

Maybe one can write it formaly as follows

\sum _{J\subseteq \{1,...n\}}(-1)^{|J|+1}\left|\bigcap _{j\in J}A_{j}\right|=\sum _{J\subseteq \{1,...n\}}(-1)^{|J|+1}\sum _{x\in \bigcup A_{i}:x\in A_{j},\forall j\in J}1=\sum _{x\in \bigcup A_{i}}\sum _{J\subseteq \{1,...n\}:x\in A_{j},\forall j\in J}(-1)^{|J|+1}=0.

The inclusion-exclusion formula follows by solving for the term

J=\emptyset

Well maybe it's a little bit complicated to write it in such a manner. At least one should see now the double-counting.

--Zuphilip 15:20, 18 April 2007 (UTC)[reply]

Indeed, the definition as given, scares the reader momentarily away from the article. Introducing the topicwith elemantary math, examples, and illustrations is the better approach, in line with McKay above but with more detailed explanations and examples starting with 2 and 3 sets. Lantonov 14:33, 23 October 2007 (UTC)[reply]

Sieve principle

I added the parenthesis with the synonym 'sieve principle'; and didn't notice until after saving that I was auto-logged out. Just so that you know whom to blame...JoergenB 14:25, 27 September 2006 (UTC)[reply]

I've actually never heard it referred to as the sieve principle, but I am not a combinatorist. I usually associate "sieve" with the sieve of eratosthenes or other number theoretic sieves. Of course these are applications of the inclusion-exclusion principle.--CSTAR 15:31, 27 September 2006 (UTC)[reply]

I never heard of it being called the "sieve principle" either. I reverted for now, perhaps the contributor who added that can come up with some references. Oleg Alexandrov (talk) 01:39, 28 September 2006 (UTC)[reply]

Combinatorics folks call it the sieve formula quite often. The first example that came up in a search was K. Dohmen, Some remarks on the sieve formula, the Tutte polynomial and Crapo's beta invariant, Aequationes Mathematicae, Volume 60, Numbers 1-2 / August, 2000. Searching for "sieve formula" at scholar.google.com finds other examples too (but not all hits are to inclusion-exclusion). McKay 04:01, 4 October 2006 (UTC)[reply]

Another example is in Stanley's Enumerative Combinatorics, where it is called a sieve method, although it seems to be considered only one of many. Cheeser1 23:46, 1 April 2007 (UTC)[reply]

Combinatorics people quite often don't call it a sieve method. I find the connection rather strained. Opinions differ as you can see. I edited the language from "is" to "can be viewed as". Zaslav (talk) 23:15, 12 May 2022 (UTC)[reply]

Diagram for n=4

The diagram currently for n=4 appears to depict a special case where - labelling the 4 sets going clockwise around the diagram say, A,B,C,D - the number of elements in the intersection of A & C which are not in B or D is zero, and the number of elements in the intersection of B & D not in A or C is also zero. This could lead students to derive alternative incorrect formulae, such as:

{\begin{aligned}|A\cup B\cup C\cup D|&=|A|+|B|+|C|+|D|\\&\qquad -|A\cap B|-|B\cap C|-|C\cap D|-|D\cap A|+|A\cap B\cap C\cap D|\end{aligned}}

I think the special case diagram is likely to lead to faulty reasoning, and would be better either removed or replaced with something catering for the general case. Stumps (talk) 03:35, 27 June 2008 (UTC)[reply]

Maybe using something like? Anyone a better artist? Stumps (talk) 05:18, 27 June 2008 (UTC)[reply]

My brain just exploded. I was always told that no "Venn Diagram" could be drawn for n > 3, and yet your picture seems to accomplish it. Perhaps my over-zealous school teachers meant it couldn't be done using only circles, which is indeed true. Austinmohr (talk) 04:47, 14 March 2010 (UTC)[reply]

Probability vs Measure spaces

Hi, do you see a particular reason to bound the discussion to probability? It seems to me that a half-way level of generality is not so convenient here after all. In fact, it only forces to repeat everything with a different notation ( P(A) instead of |A|).

My suggestion is to keep the first part with statement and proofs in the finite cardinality case, and then in a last section Inclusion–exclusion principle in measure theory just observe that everything holds in general measure spaces (so in particular for probability measures): this way we don't either need to change notation, because |A| for a general measure is standard.

Notice also that the measure theoretic setting also includes cases with a somehow more direct visual appeal (subsets in R^2 etc), than examples in Probability.

Another thing:

I would like the case of regular intersections,

{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}\,.

to be also stated in this form

{\biggl |}S\setminus \bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}a_{k}\,.

which is of common use in combinatorics and somehow nicer. --PMajer (talk) 12:51, 30 October 2008 (UTC)[reply]

Of course, the inclusion-exclusion principle could be stated right away as a result from measure theory. The combinatorics formula follows by using the counting measure, the probability version by using a probability measure. However, counting is a very easy concept, so the article should start this way. Next, every element of the sets can be given a weight, which easily leads to the concept of probability (in the case of a countable probability space). Often, introductory courses in probability are taught without using measure theory. Therefore, these readers can understand the formula in this case. For those familiar with measure theory - well, they don't really need this article anyway. In conclusion, I prefer the repetition for easy reading. Note that there is a common, joint proof for all the cases.

On the other hand, you have a point by mentioning the direct visual appeal concerning area in the plane. If you can rewrite the article accordingly without scaring away those unfamiliar with measurable spaces and measurable sets, go ahead!

If you like the other representation in the case of regular intersections, feel free to mention it in the article. Schmock (talk) 22:52, 30 October 2008 (UTC)[reply]

How about a proof by induction?

You might want to take a look at the approach given in Inclusion-Exclusion Principle in ProofWiki (a fast-growing baby sibling of this one).

The emphasis here is on the general additive function, which automatically takes on board the counting function and the probability measure (in fact, any measure you care to consider).

The proof itself is inductive and purely algebraic, in that it does not use anything more complicated than an (admittedly) intuitive appeal to "all subsets of order $s$ out of $\left\{{1,2,\ldots ,r}\right\}$ " in order to get the correct sum of the contributions of the intersections of $s$ subsets of $r$ .

IMO it's easier to follow (well I would think that, I wrote it). --WestwoodMatt (talk) 07:46, 3 March 2010 (UTC)[reply]

A Written Explanation?

This article illustrates the principle and gives an example, but to be honest I don't think your average wikipedia reader will understand it. Is it possible to illustrate a principle like this in a purely written format using examples? I'm not saying remove the mathematics, just that some sort of written explanation would make it an awful lot more readable for a general audience.

At present this is as close to a written explanation as we are given:

"The meaning of the statement is that the number of elements in the union of the two sets is the sum of the elements in each set, respectively, minus the number of elements that are in both."

What this statement is saying appears quite simple to me, it's just written in a way that is likely to promote confusion amongst those without a background in mathematics. It would also help immensely if it were followed up with an example (I know there is an example further down, but this is an example of a calculation, not a simple example of what the above statement actually means). I know this seems like dumbing down the article, but surely the key goal should be to communicate the information to as many people as possible.

Personally, I don't have the writing ability nor knowledge to do a good job of this. I'm commenting here in the hope someone else can furnish a solution. Blankfrackis (talk) 14:10, 15 December 2010 (UTC)[reply]

How about the following: To find the probability of the union of several events,

i. include the probability of the events,

ii. exclude the probabilities of the pairwise intersections,

iii. include the probabilities of the triplewise intersections,

iv. exclude the probabilities of the 4×wise intersections,

v. include the probabilities of the 5×wise intersections,

vi. and continue.

Ijon Tichy x2 (talk) 07:47, 30 March 2013 (UTC)[reply]

Möbius inversion

I am almost finished with my refactoring of this article. I've expanded the lead to make it readable, clarified the statement of the principle, talked about special cases and generalizations and vastly expanded the list of applications. I am now moving on to improve some of the mathematical writing. Before tackling the proofs (which I have moved to the end of the article, where they belong) I want to redo the section on Möbius inversion (titled "Other forms" - that will be changed!). My usual modus operandi is to leave as much of what previous editors have contributed alone and build up the section with small corrections and changes. I especially don't like to touch referenced material that I don't have access to. In this section however, I feel that I need to make some major changes. The statement of the result is not accurate, the presentation leaves much to be desired and the emphasis seems a bit skewed. This may not be the fault of the editor, but rather the reference that was used. I am planning on replacing the reference with something a bit more mainstream as I redo the section and I am afraid that not much of what is currently there will survive. Any comments before I do this? Bill Cherowitzo (talk) 03:25, 1 April 2013 (UTC)[reply]

Can the proofs be cleaned up?

The "Alternative proof" at the end is essentially exactly the same as the "First possibility" under "Proof". I could redo this, but might be better if someone familiar with the page did. Thanks! Natkuhn (talk) 02:56, 22 December 2014 (UTC)[reply]

Sorry, I meant to do this last year but it kinda fell off my radar. I'll put the algebraic proof back in a few days after I polish it up a bit. Bill Cherowitzo (talk) 19:38, 22 December 2014 (UTC)[reply]

Can the text about the origin of the concept be clarified?

The text (in the introductory part) says "This concept is attributed to Abraham de Moivre (1718);[1] but it first appears in a paper of Daniel da Silva (1854),[2] and later in a paper by J. J. Sylvester (1883).[3]"

But 1718 is long before 1854, so what does this text mean? Did de Moivre not actually write about the principle but people cite him anyway for some reason? Or is it just a mistake with the dates? It's hard to tell because de Moivre (1718) isn't actually listed in the references. Nathaniel Virgo (talk) 09:17, 2 July 2018 (UTC)[reply]

The statement in Roberts and Tesman is that de Moivre wrote the principle in another form. They then reference this to his book, The Doctrine of Chances, privately printed in London in 1718. The form of the principle as stated in this article can be traced back to da Silva and Sylvester. --Bill Cherowitzo (talk) 17:23, 2 July 2018 (UTC)[reply]

Generalization to elements in exactly k sets

To count the number of elements in exactly $k$ sets, the coefficient for the intersection of $m$ sets is $(-1)^{m+k}{m \choose k}$

In the normal case this results in coefficients 1, -1, 1, -1, ...

For elements in exactly 1 set this is 0, 1, -2, 3, -4, ...

For elements in exactly 2 sets this is 0, 0, 1, -3, 6, -10, ...

I believe this result is in textbooks but it's strangely hard to find it on the internet. I don't have a proof though so this result and the proof should be added to the article. Wqwt (talk) 06:47, 20 August 2018 (UTC)[reply]

I just found it here with reference https://math.stackexchange.com/questions/1808129/generalised-inclusion-exclusion-principle Wqwt (talk) —Preceding undated comment added 07:07, 20 August 2018 (UTC)[reply]

By Samuel Monnier - Own work (low res file), CC BY-SA 3.0, https://commons.wikimedia.org/enwiki/w/index.php?curid=8481291

By Samuel Monnier - Own work (low res file), CC BY-SA 3.0, https://commons.wikimedia.org/enwiki/w/index.php?curid=8481291 — Preceding unsigned comment added by Noosphericus (talk • contribs) 19:55, 28 December 2018 (UTC)[reply]

mistake : confusion between n-uple and set

"where the last sum runs over all subsets I of the indices 1, ..., n which contain exactly k elements, and .."

no: I runs over all n-uples.. etc. Please amend--Federicolo (talk) 13:37, 1 January 2021 (UTC)[reply]

Can we add a simplified probability calculation?

I don't have a reference for this, but it consistently works in Excel. p(at least one of 5 independent events) = p on each trial*5 - pr(event occurs 2 times) - 2pr(3 times) - 3pr(4 times) - 4pr(5 times). Etc. for any number of events. This works by correcting for double counting. It clearly works for exactly 2 events but I had to play with it to get it to work for more than 2. Does somebody have a reference and is this worth adding to this page? Ed Gracely (talk) Ed Gracely (talk) 14:43, 14 June 2024 (UTC)[reply]