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

Answers to Selected Problems

Index

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* + *B*^{2})(1 + *C* + *C*^{2} + *C*^{3})

and notice that when this is multiplied out, each term represents a different combination of letters. For example, the term *B ^{2}C* represents the combination

The terms *A ^{i}B^{j}C^{k}* having a total degree

(1 + *X*)(1 + *X* + *X*^{2})(1 + *X* + *X*^{2} + *X*^{3}).

In other words, the number of combinations is the coefficient of *X ^{3}* in the product.

**Daniel A. Marcus** received his PhD from Harvard University. He was a J. Willard Gibbs Instructor at Yale University from 1972-74. He has published research papers in the areas of combinatorics, graph theory, and number theory, and is the author of *Number Fields*, and *Differential Equations : An Introduction*.

*Combinatorics: a problem oriented approach* is a book on Combinatorics that mainly focuses on counting problems and generating functions. By restricting himself to an accomplishable goal, without attempting to be encyclopedic, the author has created a well-focused, digestible treatise on the subject. Continued...

Book Series: