Tag Archives: PIE

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

Have a piece of PIE

Posted on July 21, 2019 by Brent

Commenter Stuart LoPresti gave a very nice analysis answering the questions at the end of my last post. And indeed, the punchline is that the answers are very similar to the answers to the post before that. PIE If we … Continue reading →

Posted in pattern, probability | Tagged , | 6 Comments

Probabilistic PIE

Posted on July 17, 2019 by Brent

Commenters Sylvain B., xpil, and Christian Luca all gave correct answers to the challenge from my previous post. If the probability that someone likes X is , then the probability they don’t like X is . Therefore the probability that … Continue reading →

Posted in pattern, probability, solutions | Tagged , | 7 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