Talk:Inclusion-exclusion principle

From Wikipedia, the free encyclopedia

This article incorporates material from PlanetMath, which is licensed under the GFDL.

This is very confusing. How about some examples.


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\le i < j \le 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

∑ ∑
i 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

[edit] 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 Ai which are even is one less to the number of terms involving Ai 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)

[edit] 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)