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, 
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 | 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 
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 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)
- 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)
