Talk:Inclusion–exclusion principle

Old discussion

edit

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

 

where

 

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,   count everything twice (and so on for the other terms)? Would it be correct to write it as   ? 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   in this context does not mean the set of all ordered pairs (i,j). It does not say  , 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

edit

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   times, the third adds it   times, and so on. So the total number of times it is counted is

 

which is the binomial expansion for  . 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   which are even is one less to the number of terms involving   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.  ) is not there.
Maybe one can write it formaly as follows
 
The inclusion-exclusion formula follows by solving for the term  
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

edit

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

edit

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:

 

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

edit

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,

 

to be also stated in this form

 

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?

edit

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   out of  " in order to get the correct sum of the contributions of the intersections of   subsets of  .

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?

edit

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

edit

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?

edit

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?

edit

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

edit

To count the number of elements in exactly   sets, the coefficient for the intersection of   sets is  

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/w/index.php?curid=8481291

edit

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

mistake : confusion between n-uple and set

edit

"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?

edit

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