Monthly Archives: August 2019

PIE: proof by counting

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 , , , , | Leave a comment

PIE: proof by algebra

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 , , , , , , | 1 Comment