Part I: MATHEMATICAL PRELIMINARIES
CHAPTER 1
Counting
Walter Crane (1814–1915), The Song of Sixpence: “The Queen was in the parlor, eating bread and honey.”
This chapter reviews the basic counting techniques that will be used throughout the book. An excellent reference for this material is [Rosen 2003].
1.1 THE SUM AND PRODUCT RULES
SUM RULE
If the first of two tasks can be performed in any of n1 ways and the second in any of n2 ways, and if these tasks cannot be performed at the same time, then there are n1 + n2 ways of performing either task.
Example 1.1.
The formula |N1 ∪ N2| = n1 + n2 is valid if
a) Sets N1 and N2 contain n1 = |N1| and n2 = |N2| elements, respectively.
b)
The sets have no elements in common 
.
GENERALIZED SUM RULE
If the ith of m tasks 1 ≤ i ≤ m can be performed in any of ni ways, and if these cannot be performed at the same time, then there are n1 + n2 + ··· + nm ways of performing any of the m tasks.
Example 1.2.
The formula 
is valid if
a) m sets N1, N2, ··· , Nm contain n1 = |N1|, n2 = |N2|, ··· , nm = |Nm| elements, respectively.
b) No pair of (distinct) sets Ni and Nj (1 ≤ i < j ≤ m) has an element in common (pairwise disjoint sets) .
If the m sets N1
