Tag Archives: inclusion

PIE: proof by counting

Posted on August 13, 2019 by Brent

Recall the setup: we have a universal set and a collection of subsets , , , and so on, up to . PIE claims that we can compute the number of elements of that are in none of the (that … Continue reading →

Posted in combinatorics, pattern, proof | Tagged , , , , | 1 Comment

PIE: proof by algebra

Posted on August 7, 2019 by Brent

In my previous post I stated a very formal, general form of the Principle of Inclusion-Exclusion, or PIE.1 In this post I am going to outline one proof of PIE. I’m not going to give a completely formal proof, because … Continue reading →

Posted in combinatorics, induction, pattern, proof | Tagged , , , , , , | 2 Comments

Formal PIE

Posted on July 27, 2019 by Brent

I’ve been talking informally about the Principle of Inclusion-Exclusion but I realized it would be useful to state it more formally before proceeding to some proofs. The only problem is that a fully formal statement of PIE has a lot … Continue reading →

Posted in combinatorics, pattern | Tagged , , , , , | 5 Comments

Post without words #19

Posted on June 2, 2017 by Brent
Posted in pattern, pictures, posts without words | Tagged , , , , , , | 2 Comments

Post without words #18

Posted on May 31, 2017 by Brent
Posted in pattern, pictures, posts without words | Tagged , , , , , , | 5 Comments

PIE day

Posted on October 15, 2013 by Brent

[This is part six in an ongoing series; previous posts can be found here: Differences of powers of consecutive integers, Differences of powers of consecutive integers, part II, Combinatorial proofs, Making our equation count, How to explain the principle of … Continue reading →

Posted in combinatorics, counting | Tagged , , , , | 2 Comments

How to explain the principle of inclusion-exclusion?

Posted on June 11, 2012 by Brent

I’ve been remiss in finishing my series of posts on a combinatorial proof. I still intend to, but I must confess that part of the reason I haven’t written for a while is that I’m sort of stuck. The next … Continue reading →

Posted in combinatorics, meta | Tagged , , , | 7 Comments