ISBN-10:
047126296X
ISBN-13:
9780471262961
Pub. Date:
08/08/2003
Publisher:
Wiley
Combinatorics / Edition 2

Combinatorics / Edition 2

by Russell Merris

Hardcover

Current price is , Original price is $192.0. You

Temporarily Out of Stock Online

Please check back later for updated availability.

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


John Wiley & Sons



Copyright © 2003

Russell Merris
All right reserved.



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 fundamental
counting 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 from Combinatorics
by Russell 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)

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews