Talk:Inclusion-exclusion principle

From Wikipedia, the free encyclopedia

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)

[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)
Retrieved from "http://en.wikipedia.org../../../i/n/c/Talk%7EInclusion-exclusion_principle_6222.html"