Edition:

2

Publisher:

Chapman & Hill/CRC

Number of Pages:

430

Price:

79.95

ISBN:

9781420082609

Joint review of

*How To Count: An Introduction to Combinatorics*, by R. B. J. T. Allenby and Alan Slomson*Introduction to Combinatorics*, W. D. Wallis and J. G. George

The two books under review are introductory combinatorics texts, also suitable for individual study. I shall refer to them by the combination of the first letters of the authors’ last names: AS and WG. Both book are thoughtfully written, contain plenty of material and exercises. Understandably, there is a considerable overlap. Common to the books are the essential topics, such as permutations and combinations, the Inclusion-Exclusion principle, generating functions and recurrence relations, graphs and graph algorithms, groups of permutations, counting patterns, Pólya counting, the pigeonhole principle and Ramsey theory, and Catalan and Sterling numbers.

AS features chapters on integer partitions, barely touched in WG, and, in general, covers more expansively the common topics, especially, group and Ramsey theories, matching and marriages. WG, on the other hand, devotes separate chapters to coding theory, Latin squares, balanced incomplete block designs, and applications of linear algebra to combinatorics. AS (p. 228) observes that “Latin squares are interesting and important combinatorial objects, but because of shortage of space we are not able to discuss them in this book.” There are briefer, say section-level, differences: rook polynomials, Euclidean Ramsey theory (AS), sum-free sets, exponential generating functions (WG).

In both books exercises come in two categories: A and B. The A exercises are supplied with solutions, the B exercises (which in WG are collected in separate sections) are not. WG also offers lists of problems — generally more sophisticated questions — that are accompanied by hints and solutions at the end of the book.

Both books begin with extensive Introductions that outline the contents by posing questions and problems that the books deal with subsequently. AS offers short biographical information in footnotes; WG in a separate Appendix. In addition, WG covers some background information (proof techniques, matrices and vectors) in two separate appendices.

WG provides numerous fragments of Mathematica code and this is a nice touch. For example, on pp. 259–260 the authors discuss the problem of determining the number of ways to cover a 2×6 board with nonoverlapping dominos. They form a digraph and its adjacency matrix A and then rely on Mathematica’s

B = Inverse[IdentityMatrix[6] - x*A];

B[[2,2]]

to obtain the generating function

(1 – 2x

^{2}+ x^{4})/(1- x – 6x^{2}– x^{3}+ 6x^{4}+ 2x^{5}– x^{6})

which they then expand into a power series with

Series[%,{x,0,10}]

and subsequently elucidate the meanings of every coefficient.

For a balance check, AS goes to a considerably greater length introducing elements of group theory as a tool towards Frobenius and Pólya counting theorems.

At this point I would like to confess that the two books have been sitting on my desk for a while now. Somehow my first impression was so distressing that I could not see the point of reviewing them. As luck would have it, I opened the books the first time on pages with misprints. For AS, it was a confusing swap of “>” for “<” on page 296. For WG, it was a section titled “Applications of P(n, k) and C(n, k)” that had no mention of P(n, k).

Truth be told, I actually came across only a few more typos in AS and eventually found the text very readable and useful. I can’t say the same of WG. The number of typos there is bewildering. For example, on pages 196–197 there are three:

- B
_{1}A_{4}B_{3}B_{4}B_{5}B_{6}B_{7}instead of B_{1}B_{2}B_{3}B_{4}B_{5}B_{6}B_{7} - ainC instead of a∈C, and
- N instead of n.

These were actually trifles. On page 73, Example 4.3 refers to Example 2.2 (p. 27), while the reference should be to Example 2.6 (p. 31) The diagram in the latter example is exactly the same as that accompanying Example 4.3, even though the diagram is not quite suitable for the earlier stage.

I truly came to grief with the WG’s index. None of the terms I wanted to check could be found on the pages the Index pointed me to. Only after I decided to record the discrepancies, I realized that a major part of the index was off by 2 pages. It’s not that, bad one may say, but not every student will be as savvy or as determined to discover the truth. Further, the Index contains the word “Arrangement”, but it is not defined (far as I can see) anywhere in the book; what the index poinst to is the definition of “Derangement”.

To give one more example, Theorem 13.3 reads, “The balanced bipartite graph B has exactly Per(B(G)) perfect matchings.” As a matter of fact the term “balanced bipartite graph” is not found in the index and, as far as I can judge, is not defined anywhere in the book, at least not where I would expect it to be. The same holds for the “Cancellation law” entry.

Thus, for a long time I was at a loss whether to write a review or to let time pass. Then somebody tweeted me a review (by John Trimble) of *Writing With Style: Conversations on the Art of Writing*, a book by James M. Lang. The review is full of praise, in particular from the book’s current editor Brad Potthoff:

He brings out the best in his editors and asks as much of them as he does of himself. As such, working with John is a joyous challenge and one of the highlights of my career.

This note gave me a point of reference and an impulse to pull myself together. Whether or not this is due to the authors’ failure to engage the editors at CRC, the fact is that the latter did a lousy job editing the books, crucially so for WG.

Alex Bogomolny is a freelance mathematician and educational web developer. He regularly works on his website Interactive Mathematics Miscellany and Puzzles and blogs at Cut The Knot Math.

Date Received:

Monday, October 25, 2010

Reviewable:

Yes

Series:

Discrete Mathematics and Its Applications

Publication Date:

2011

Format:

Hardcover

Audience:

Category:

Textbook

Alex Bogomolny

02/15/2011

**What’s It All About?**

What Is Combinatorics?

Classic Problems

What You Need to Know

Are You Sitting Comfortably?

**Permutations and Combinations**

The Combinatorial Approach

Permutations

Combinations

Applications to Probability Problems

The Multinomial Theorem

Permutations and Cycles

**Occupancy Problems**

Counting the Solutions of Equations

New Problems from Old

A "Reduction" Theorem for the Stirling Numbers

**The Inclusion-Exclusion Principle**

Double Counting

Derangements

A Formula for the Stirling Numbers

**Stirling and Catalan Numbers**

Stirling Numbers

Permutations and Stirling Numbers

Catalan Numbers

**Partitions and Dot Diagrams **Partitions

Dot Diagrams

A Bit of Speculation

More Proofs Using Dot Diagrams

**Generating Functions and Recurrence Relations **Functions and Power Series

Generating Functions

What Is a Recurrence Relation?

Fibonacci Numbers

Solving Homogeneous Linear Recurrence Relations

Nonhomogeneous Linear Recurrence Relations

The Theory of Linear Recurrence Relations

Some Nonlinear Recurrence Relations

**Partitions and Generating Functions **The Generating Function for the Partition Numbers

A Quick(ish) Way of Finding

An Upper Bound for the Partition Numbers

The Hardy–Ramanujan Formula

The Story of Hardy and Ramanujan

**Introduction to Graphs**

Graphs and Pictures

Graphs: A Picture-Free Definition

Isomorphism of Graphs

Paths and Connected Graphs

Planar Graphs

Eulerian Graphs

Hamiltonian Graphs

The Four-Color Theorem

**Trees **What Is a Tree?

Labeled Trees

Spanning Trees and Minimal Connectors

The Shortest-Path Problem

**Groups of Permutations **Permutations as Groups

Symmetry Groups

Subgroups and Lagrange’s Theorem

Orders of Group Elements

The Orders of Permutations

**Group Actions **Colorings

The Axioms for Group Actions

Orbits

Stabilizers

**Counting Patterns **Frobenius’s Counting Theorem

Applications of Frobenius’s Counting Theorem

**Pólya Counting **Colorings and Group Actions

Pattern Inventories

The Cycle Index of a Group

Pólya’s Counting Theorem: Statement and Examples

Pólya’s Counting Theorem: The Proof

Counting Simple Graphs

**Dirichlet’s Pigeonhole Principle **The Origin of the Principle

The Pigeonhole Principle

More Applications of the Pigeonhole Principle

**Ramsey Theory**

What Is Ramsey’s Theorem?

Three Lovely Theorems

Graphs of Many Colors

Euclidean Ramsey Theory

**Rook Polynomials and Matchings**

How Rook Polynomials Are Defined

Matchings and Marriages

**Solutions to the A Exercises**

**Books for Further Reading **

**Index**

Publish Book:

Modify Date:

Tuesday, February 15, 2011

- Log in to post comments