Talk:Inclusion–exclusion principle

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)

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)

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)

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

---

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)

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)

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)

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)

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)

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)

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)

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)

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)

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

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)

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)

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)

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)

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)