ABSTRACT
In earlier chapters, we have spent a lot of time studying the counting problem: given a finite set S, how many elements does S have? This chapter generalizes the counting problem to the following situation. Given a finite set S of objects, where each object is assigned an integer-valued weight, how many objects in S are there of each given weight? A convenient way to present the answer to this question is via a generating function, which is a polynomial a0 + a1x + a2x
2 + · · · + anxn such that ak (the coefficient of xk) is the number of objects in S of weight k. After giving the basic definitions, we will develop rules for manipulating generating functions that are analogous to the sum rule and product rule from Chapter 1. We will also derive formulas for certain generating functions that generalize factorials, binomial coefficients, and multinomial coefficients. In later chapters, we extend all of these ideas to the more general situation where S is an infinite set of weighted objects.
