Category Archives: pattern

A few words about PWW #27

The images in my last post were particular realizations of the famous Sieve of Eratosthenes. The basic idea of the sieve is to repeatedly do the following: Circle the next number bigger than that is not yet crossed out, call … Continue reading

Posted in pattern, pictures, posts without words, primes | Tagged , , | 4 Comments

Post without words #27

Image | Posted on by | Tagged , , | 7 Comments

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 , , , , | 1 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 , , , , , , | 2 Comments

Formal PIE

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

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

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