# Combinatorics: A Problem Oriented Approach

### By Daniel A. Marcus

Catalog Code: CMB
Print ISBN: 978-0-88385-710-6
Electronic ISBN: 978-0-88385-981-0
156 pp., Paperbound, 1998
List Price: $43.50 MAA Member:$34.50
Series: MAA Textbooks

The unique format of this book combines features of a traditional textbook with those of a problem book. The subject matter is presented through a series of approximately 250 problems with connecting text where appropriate, and is supplemented by some 200 additional problems for homework assignments. While intended primarily for use as the text for a college-level course taken by mathematics, computer science, and engineering students, the book is suitable as well for a general education course at a good liberal arts college, or for self-study.

Part I. Basics
Section A: Strings
Section B: Combinations
Section C: Distributions
Section D: Partitions
Part II: Special Counting Methods
Section E: Inclusion and Exclusion
Section F: Recurrence Relations
Section G: Generating Functions
Section H: The Pólya-Redfield Method
List of Standard Problems
Dependence of Problems
Index

### Excerpt: Section. G General Functions (p. 87)

In section E, we saw how the principle of inclusion and exclusion could be used to count combinations with limited repetition. In this section we will solve problems of this type, including more complicated variations, by a different method.

Example  Find the number of ways to select a three-letter combination from the set {A, B, C} if A can be included at most once, B at most twice, and C at most three times.

G1  Do this by counting directly.

Another approach to this problem is to form the expression

(1 + A)(1 + B + B2)(1 + C + C2 + C3)

and notice that when this is multiplied out, each term represents a different combination of letters. For example, the term B2C represents the combination BBC. (Notice how the term 1 in the first factor allows A to be missing from this combination.)

The terms AiBjCk having a total degree i + j + k = 3 correspond to the three-letter combinations counted in problem G1. This observation suggests the following idea: If we replace A, B, and C by X everywhere they appear, the the number of combinations counted in problem G1 is equal to the number of times X3 occurs in teh expansion of the product

(1 + X)(1 + X + X2)(1 + X + X2 + X3).

In other words, the number of combinations is the coefficient of X3 in the product.