ABSTRACT
In this chapter, we will consider more advanced counting questions and techniques. At the start, we will examine a range of combinatorial questions commonly encountered and reframe all of these in the language of distributing balls into boxes. Later in the chapter, we will try to figure out how many ways there are to distribute balls into boxes. That sounds simple, but there are lots of variations: Are the balls identical, or are they labeled? What about the labeling of the boxes? Does it matter whether any of the boxes is empty? It turns out that addressing some of the possible scenarios is quite difficult and well beyond this text! We will focus on balls-and-boxes problems that can be answered using binomial coefficients or permutations in interesting ways. We will also work with the principle of inclusion-exclusion, or PIE for short. Back in the old days of Chapter 1, we used the sum principle to determine the size of a collection of disjoint sets; PIE reveals how to determine the size of a collection of sets that are not disjoint. One application of PIE is to Venn diagrams and how to figure out the number of objects represented by one of the regions of a Venn diagram given sufficient information about the other regions.
