**Uh-oh, it looks like your Internet Explorer is out of date.**

For a better shopping experience, please upgrade now.

Combinatorics / Edition 2 available in Hardcover

## Hardcover

Buy New

**$156.48**

Buy Used

**$118.21**

^{$}156.48

**Temporarily Out of Stock Online**

Please check back later for updated availability.

## Overview

A mathematical gem–freshly cleaned and polished

This book is intended to be used as the text for a first course in combinatorics. the text has been shaped by two goals, namely, to make complex mathematics accessible to students with a wide range of abilities, interests, and motivations; and to create a pedagogical tool, useful to the broad spectrum of instructors who bring a variety of perspectives and expectations to such a course.

Features retained from the first edition:

- Lively and engaging writing style
- Timely and appropriate examples
- Numerous well-chosen exercises
- Flexible modular format
- Optional sections and appendices

Highlights of Second Edition enhancements:

- Smoothed and polished exposition, with a sharpened focus on key ideas
- Expanded discussion of linear codes
- New optional section on algorithms
- Greatly expanded hints and answers section
- Many new exercises and examples

###### ADVERTISEMENT

## Product Details

ISBN-13: | 9780471262961 |
---|---|

Publisher: | Wiley |

Publication date: | 08/08/2003 |

Series: | Wiley Series in Discrete Mathematics and Optimization Series , #63 |

Edition description: | REV |

Pages: | 576 |

Product dimensions: | 6.30(w) x 9.50(h) x 1.20(d) |

## About the Author

**RUSSELL MERRIS, PhD**, is Professor of Mathematics and Computer Science at California State University, Hayward. Among his other books is Graph Theory, also published by Wiley.

## Read an Excerpt

Combinatorics

By Russell Merris

By Russell Merris

John Wiley & Sons

John Wiley & Sons

Copyright © 2003

Copyright © 2003

Russell Merris

All right reserved.

Russell Merris

All right reserved.

ISBN: 0-471-26296-X

ISBN: 0-471-26296-X

Chapter One

**The Mathematics of Choice**

It seems that mathematical ideas are arranged somehow in strata, the ideas in each

stratum being linked by a complex of relations both among themselves and with those

above and below. The lower the stratum, the deeper (and in general the more difficult)

the idea. Thus, the idea of an irrational is deeper than the idea of an integer.

-G. H. Hardy (*A Mathematician's Apology*)

Roughly speaking, the first chapter of this book is the top stratum, the surface layer

of combinatorics. Even so, it is far from superficial. While the first main result, the

so-called fundamental counting principle, is nearly self-evident, it has enormous

implications throughout combinatorial enumeration. In the version presented here,

one is faced with a sequence of decisions, each of which involves some number of

choices. It is from situations like this that the chapter derives its name.

To the uninitiated, mathematics may appear to be "just so many numbers and

formulas." In fact, the numbers and formulas should be regarded as shorthand

notes, summarizing *ideas*. Some ideas from the first section are summarized by

an algebraic formulafor multinomial coefficients. Special cases of these numbers

are addressed from a combinatorial perspective in Section 1.2.

Section 1.3 is an optional discussion of probability theory which can be omitted

if probabilistic exercises in subsequent sections are approached with caution.

Section 1.4 is an optional excursion into the theory of binary codes which can be

omitted by those not planning to visit Chapter 6. Sections 1.3 and 1.4 are partly

motivational, illustrating that even the most basic combinatorial ideas have real-life

applications.

In Section 1.5, ideas behind the formulas for sums of powers of positive integers

motivate the study of relations among binomial coefficients. Choice is again the

topic in Section 1.6, this time with or without replacement, where order does or

doesn't matter.

To better organize and understand the multinomial theorem from Section 1.7,

one is led to symmetric polynomials and, in Section 1.8, to partitions of *n*.

Elementary symmetric functions and their association with power sums lie at the

heart of Section 1.9. The final section of the chapter is an optional introduction to

algorithms, the flavor of which can be sampled by venturing only as far as

Algorithm 1.10.3. Those desiring not less but more attention to algorithms can

find it in Appendix A2.

*1.1. THE FUNDAMENTAL COUNTING PRINCIPLE*

How many different four-letter words, including nonsense words, can be produced

by rearranging the letters in LUCK? In the absence of a more inspired approach,

there is always the brute-force strategy: Make a systematic list.

Once we become convinced that Fig. 1.1.1 accounts for every possible rearrangement

and that no "word" is listed twice, the solution is obtained by counting the

24 words on the list.

While finding the brute-force strategy was effortless, implementing it required

some work. Such an approach may be fine for an isolated problem, the *like* of which

one does not expect to see again. But, just for the sake of argument, imagine yourself

in the situation of having to solve a great many thinly disguised variations of

this same problem. In that case, it would make sense to invest some effort in finding

a strategy that requires less work to implement. Among the most powerful tools in

this regard is the following commonsense principle.

**1.1.1 Fundamental Counting Principle.** Consider a (finite) sequence of decisions.

Suppose the number of choices for each individual decision is independent

of decisions made previously in the sequence. Then the number of ways to make the

whole sequence of decisions is the product of these numbers of choices.

To state the principle symbolically, suppose [c.sub.i] is the number of choices for decision*i*. If, for 1 [less than or equal to] *i* [less than or equal to] n, [c.sub.i]+1 does not depend

on which choices are made in decisions 1,..., *i*, then the number of different ways to make the sequence of

decisions is [c.sub.1]x[c.sub.2]x ... x [c.sub.n].

Let's apply this principle to the word problem we just solved. Imagine yourself

in the midst of making the brute-force list. Writing down one of the words involves

a sequence of four decisions. Decision 1 is which of the four letters to write first, so

[c.sub.1] = 4. (It is no accident that Fig. 1.1.1 consists of four rows!) For each way of

making decision 1, there are [c.sub.2] = 3 choices for decision 2, namely which letter

to write second. Notice that the specific letters comprising these three choices

depend on how decision 1 was made, but their *number* does not. That is what is

meant by the number of choices for decision 2 being independent of how the previous

decision is made. Of course, [c.sub.3] = 2, but what about [c.sub.4]? Facing no alternative,

is it correct to say there is "no choice" for the last decision? If that were literally

true, then [c.sub.4] would be zero. In fact, [c.sub.4] = 1. So, by the fundamental counting

principle, the number of ways to make the sequence of decisions, i.e., the number

of words on the final list, is

[c.sub.1]x[c.sub.2]x[c.sub.3]x[c.sub.4] = 4x3x2x1.

The product n x (n - 1) x (n - 2) x ... x 2 x 1 is commonly written n! and

read *n-factorial*. The number of four-letter words that can be made up by rearranging

the letters in the word LUCK is 4! = 24.

What if the word had been LUCKY? The number of five-letter words that can be

produced by rearranging the letters of the word LUCKY is 5! = 120. A systematic

list might consist of five rows each containing 4! = 24 words.

Suppose the word had been LOOT? How many four-letter words, including non-sense

words, can be constructed by rearranging the letters in LOOT? Why not apply

the fundamental counting principle? Once again, imagine yourself in the midst of

making a brute-force list. Writing down one of the words involves a sequence of

four decisions. Decision 1 is which of the three letters L, O, or T to write first.

This time, [c.sub.1] = 3. But, what about [c.sub.2]? In this case, the number of choices for decision

2 depends on how decision 1 was made! If, e.g., *L* were chosen to be the first

letter, then there would be two choices for the second letter, namely O or T. If, however,

O were chosen first, then there would be three choices for the second decision,

L, (the second) O, or T. Do we take [c.sub.2] or [c.sub.2]= 3? The answer is that *the fundamentalcounting principle does not apply to this problem* (at least not directly).

The fundamental counting principle applies

*only*when the

*number*of choices for

decision

*i*+ 1 is

*independent*of how the previous

*i*decisions are made.

To enumerate all possible rearrangements of the letters in LOOT, begin by distinguishing

the two O's. maybe write the word as LOoT. Applying the fundamental

counting principle, we find that there are 4! = 24 different-*looking* four-letter words

that can be made up from L, O, o, and T.

Among the words in Fig. 1.1.2 are pairs like OLoT and oLOT, which look different

only because the two O's have been distinguished. In fact, every word in the

list occurs twice, once with "big O" coming before "little o", and once the other

way around. Evidently, the number of different words (with indistinguishable O's)

that can be produced from the letters in LOOT is not 4! but 4!/2...=2

What about TOOT? First write it as TOot. Deduce that in any list of all possible

rearrangements of the letters T, O, o, and t, there would be 4! = 24 different-looking

words. Dividing by 2 makes up for the fact that two of the letters are O's. Dividing

by 2 again makes up for the two T's. The result, 24/(2x2) = 6, is the number

of different words that can be made up by rearranging the letters in TOOT. Here

they are

TTOO TOTO TOOT OTTO OTOT OOTT

All right, what if the word had been LULL? How many words can be produced

by rearranging the letters in LULL? Is it too early to guess a pattern? Could the

number we're looking for be 4!/3 = 8? No. It is easy to see that the correct answer

must be 4. Once the position of the letter U is known, the word is completely determined.

Every other position is filled with an L. A complete list is ULLL, LULL,

LLUL, LLLU.

To find out why 4!/3 is wrong, let's proceed as we did before. Begin by distinguishing

the three L's, say [L.sub.1], [L.sub.2], and [L.sub.3]. There are 4! different-looking words that

can be made up by rearranging the four letters [L.sub.1], [L.sub.2], [L.sub.3], and U. If we were to make

a list of these 24 words and then erase all the subscripts, how many times would,

say, LLLU appear? The answer to this question can be obtained from the fundamental

counting principle! There are three decisions: decision 1 has three choices,

namely which of the three L's to write first. There are two choices for decision 2

(which of the two remaining L's to write second) and one choice for the third decision,

which L to put last. Once the subscripts are erased, LLLU would appear 3!

times on the list. We should divide 4! = 24, not by 3, but by 3! = 6. Indeed,

4!/3! = 4 is the correct answer.

Whoops! if the answer corresponding to LULL is 4!/3!, why didn't we get 4!/2!

for the answer to LOOT? In fact, we did: 2! = 2.

Are you ready for MISSISSIPPI? It's the same problem! If the letters were all

different, the answer would be 11!. Dividing 11! by 4! makes up for the fact that

there are four I's. Dividing the quotient by another 4! compensates for the four S's.

Dividing that quotient by 2! makes up for the two P's. In fact, no harm is done if

that quotient is divided by 1! = 1 in honor of the single M. The result is

11!/4!4!2!1! = 34,650

(Confirm the arithmetic.) The 11 letters in MISSISSIPPI can be (re)arranged in

34,650 different ways.

There is a special notation that summarizes the solution to what we might call

the "MISSISSIPPI problem."

** 1.1.2 Definition.** The

*multinomial coefficient*

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [r.sub.1] + [r.sub.2] + ··· + [r.sub.k] = n.

So, "multinomial coefficient" is a *name* for the answer to the question, how

many *n*-letter "words" can be assembled using [r.sub.1] copies of one letter, [r.sub.2] copies

of a second (different) letter, [r.sub.3] copies of a third letter,..., and [r.sub.k] copies of a

kth letter?

** 1.1.3 Example.** After cancellation.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore, 2520 different words can be manufactured by rearranging the nine letters

in the word SASSAFRAS.

In real-life applications, the words need not be assembled from the English

alphabet. Consider, e.g., POSTNET barcodes commonly attached to U.S. mail

by the Postal Service. In this scheme, various numerical delivery codes are represented

by "words" whose letters, or *bits*, come from the alphabet ,. Corresponding,

e.g., to a ZIP + 4 code is a 52-bit barcode that begins and ends with |. The 50-bit

middle part is partitioned into ten 5-bit zones. The first nine of these zones are

for the digits that comprise the ZIP + 4 code. The last zone accommodates a *parity check* digit, chosen so that the sum of all ten digits is a multiple of 10. Finally, each

digit is represented by one of the 5-bit barcodes in Fig. 1.1.3. Consider, e.g., the ZIP

+4 code 20090-0973, for the Mathematical Association of America. Because the

sum of these digits is 30, the parity check digit is 0. The corresponding 52-bit

word can be found in Fig. 1.1.4.

We conclude this section with another application of the fundamental counting

principle.

** 1.1.4 Example.** Suppose you wanted to determine the number of positive

integers that exactly divide

*n*= 12. That isn't much of a problem; there are six

of them, namely, 1, 2, 3, 4, 6, and 12. What about the analogous problem for

*n*= 360 or for

*n*= 360,000? Solving even the first of these by brute-force list

making would be a lot of work. Having already found another strategy whose

implementation requires a lot less work, let's take advantage of it.

Consider 360 = [2.sup.3] x [3.sup.2] x 5, for example. If 360 = dq for positive integers *d*

and *q*, then, by the uniqueness part of the *fundamental theorem of arithmetic*, the

prime factors of *d*, together with the prime factors of *q*, are precisely the prime

factors of 360, multiplicities included. It follows that the prime factorization of *d*

must be of the form *d* = [2.sup.a] x [3.sup.b] x [5.sup.c] , where 0 [less than or equal to] *a* [less than or equal to] 3, 0 [less than or equal to] *b* [less than or equal to] 2, and 0 [less than or equal to] *c* [less than or equal to] 1. Evidently, there are four choices for *a* (namely 0, 1, 2, or 3), three choices for *b*, and two choices for c. So, the number of possibile *d*'s is 4 x 3 x 2 = 24.

**1.1. EXERCISES**

** 1** The Hawaiian alphabet consists of 12 letters, the vowels *a, e, i, o, u* and the

consonants *h, k, l, m, n, p, w*.

**(a)** Show that 20,736 different 4-letter "words" could be constructed using the

12-letter Hawaiian alphabet.

**(b)** Show that 456,976 different 4-letter "words" could be produced using the

26-letter English alphabet.

**(c)** How many four-letter "words" can be assembled using the Hawaiian

alphabet if the second and last letters are vowels and the other 2 are

consonants?

**(d)** How many four-letter "words" can be produced from the Hawaiian

alphabet if the second and last letters are vowels but there are no restrictions

on the other 2 letters?

**2** Show that

**(a)** 3! x 5! = 6!.

**(b)** 6! x 7! = 10!.

**(c)** (*n*+1) x (*n*!) = (*n*+1)!.

**(d)** [*n*.sub.2] = *n*![1/(*n*-1)! + 1/(*n*-2)!].

**(e)** [*n*.sub.3] = *n*![1/(*n*-1)! + 3/(*n*-2)! + 1/(*n*-3)!]

**3** One brand of electric garage door opener permits the owner to select his or her

own electronic "combination" by setting six different switches either in the

"up" or the "down" position. How many different combinations are possible?

**4** One generation back you have two ancestors, your (biological) parents. Two

generations back you have four ancestors, your grandparents. Estimating [2.sup.10] as

[10.sup.3*Continues...*

Excerpted fromCombinatorics

byRussell Merris

Copyright © 2003 by Russell Merris.

Excerpted by permission.

All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.

Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

## Table of Contents

Preface.

**Chapter 1: The Mathematics of Choice.**

1.1. The Fundamental Counting Principle.

1.2. Pascal’s Triangle.

*1.3. Elementary Probability.

*1.4. Error-Correcting Codes.

1.5. Combinatorial Identities.

1.6. Four Ways to Choose.

1.7. The Binomial and Multinomial Theorems.

1.8. Partitions.

1.9. Elementary Symmetric Functions.

*1.10. Combinatorial Algorithms.

**Chapter 2: The Combinatorics of Finite Functions.**

2.1. Stirling Numbers of the Second Kind.

2.2. Bells, Balls, and Urns.

2.3. The Principle of Inclusion and Exclusion.

2.4. Disjoint Cycles.

2.5. Stirling Numbers of the First Kind.

**Chapter 3: Pólya’s Theory of Enumeration.**

3.1. Function Composition.

3.2. Permutation Groups.

3.3. Burnside’s Lemma.

3.4. Symmetry Groups.

3.5. Color Patterns.

3.6. Pólya’s Theorem.

3.7. The Cycle Index Polynomial.

**Chapter 4: Generating Functions.**

4.1. Difference Sequences.

4.2. Ordinary Generating Functions.

4.3. Applications of Generating Functions.

4.4. Exponential Generating Functions.

4.5. Recursive Techniques.

**Chapter 5: Enumeration in Graphs.**

5.1. The Pigeonhole Principle.

*5.2. Edge Colorings and Ramsey Theory.

5.3. Chromatic Polynomials.

*5.4. Planar Graphs.

5.5. Matching Polynomials.

5.6. Oriented Graphs.

5.7. Graphic Partitions.

**Chapter 6: Codes and Designs.**

6.1. Linear Codes.

6.2. Decoding Algorithms.

6.3. Latin Squares.

6.4. Balanced Incomplete Block Designs.

Appendix A1: Symmetric Polynomials.

Appendix A2: Sorting Algorithms.

Appendix A3: Matrix Theory.

Bibliography.

Hints and Answers to Selected Odd-Numbered Exercises.

Index of Notation.

Index.

Note: Asterisks indicate optional sections that can be omitted without loss of continuity.

## What People are Saying About This

**From the Publisher**

“…broad and interesting…” (*Zentralblatt Math*, Vol.1035, No.10, 2004)

“...engagingly written...a robust learning tool...” (*American Mathematical Monthly*, March 2004)