You are here

Combinatorics: A Problem Oriented Approach

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: $45.00
MAA Member: $33.75
Series: MAA Textbooks

Buy Print BookBuy eBook

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.

Table of Contents

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

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.

About the Author

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.

MAA Review

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: