Chapter 2 Advanced Combinatorics
¶The combinatorics we have investigated so far has been nice. While not always immediately obvious, each problem had an answer in a nice form that, once you saw how to think about it the right way, could be expressed with a closed formula.
Not all of combinatorics is like this. There are natural questions for which we do not have neat closed formulas. This might be because we (mathematicians) have not yet figured out how to think about these problems in the “right” way, or because there is really no clean approach to solve these problems.
But lack of clean solutions does not mean the problems have no answer. Rather, we must simply look for more abstract techniques before we can get any hold on them.
The plan for this chapter is as follows. We will start with two combinatorial tools. First, the Principle of Inclusion and Exclusion and then generating functions. We will then consider some natural extensions of distribution problems first introduced in Section 1.3: partitioning sets and integers.