Introduction to Combinatorics (eBook)

Martin J. Erickson (Autor)

eBook Download: EPUB

2013 | 2. Auflage
John Wiley & Sons (Verlag)
978-1-118-63758-6 (ISBN)

Infos

Praise for the First Edition
“This excellent text should prove a useful accoutrement for any developing mathematics program . . . it’s short, it’s sweet, it’s beautifully written.” —The Mathematical Intelligencer

“Erickson has prepared an exemplary work . . . strongly recommended for inclusion in undergraduate-level library collections.” —Choice

Featuring a modern approach, Introduction to Combinatorics, Second Edition illustrates the applicability of combinatorial methods and discusses topics that are not typically addressed in literature, such as Alcuin’s sequence, Rook paths, and Leech’s lattice. The book also presents fundamental results, discusses interconnection and problem-solving techniques, and collects and disseminates open problems that raise questions and observations.

Many important combinatorial methods are revisited and repeated several times throughout the book in exercises, examples, theorems, and proofs alike, allowing readers to build confidence and reinforce their understanding of complex material. In addition, the author successfully guides readers step-by-step through three major achievements of combinatorics: Van der Waerden’s theorem on arithmetic progressions, Pólya’s graph enumeration formula, and Leech’s 24-dimensional lattice.  Along with updated tables and references that reflect recent advances in various areas, such as error-correcting codes and combinatorial designs, the Second Edition also features:

• Many new exercises to help readers understand and apply combinatorial techniques and ideas
• A deeper, investigative study of combinatorics through exercises requiring the use of computer programs
• Over fifty new examples, ranging in level from routine to advanced, that illustrate important combinatorial concepts
• Basic principles and theories in combinatorics as well as new and innovative results in the field

Introduction to Combinatorics, Second Edition is an ideal textbook for a one- or two-semester sequence in combinatorics, graph theory, and discrete mathematics at the upper-undergraduate level. The book is also an excellent reference for anyone interested in the various applications of elementary combinatorics.

MARTIN J. ERICKSON, PhD, is Professor in the Department of Mathematics at Truman State University. The author of numerous books, including Mathematics for the Liberal Arts (Wiley), he is a member of the American Mathematical Society, Mathematical Association of America, and American Association of University Professors.

Inhalt

Preface xi

1 Basic Counting Methods 1

1.1 The multiplication principle 1

1.2 Permutations 4

1.3 Combinations 6

1.4 Binomial coefficient identities 10

1.5 Distributions 19

1.6 The principle of inclusion and exclusion 23

1.7 Fibonacci numbers 31

1.8 Linear recurrence relations 33

1.9 Special recurrence relations 41

1.10 Counting and number theory 45

Notes 50

2 Generating Functions 53

2.1 Rational generating functions 53

2.2 Special generating functions 63

2.3 Partition numbers 76

2.4 Labeled and unlabeled sets 80

2.5 Counting with symmetry 86

2.6 Cycle indexes 93

2.7 Pólya's theorem 96

2.8 The number of graphs 98

2.9 Symmetries in domain and range 102

2.10 Asymmetric graphs 103

Notes 105

3 The Pigeonhole Principle 107

3.1 Simple examples 107

3.2 Lattice points, the Gitterpunktproblem, and SET®
110

3.3 Graphs 115

3.4 Colorings of the plane 118

3.5 Sequences and partial orders 119

3.6 Subsets 124

Notes 126

4 Ramsey Theory 131

4.1 Ramsey's theorem 131

4.2 Generalizations of Ramsey's theorem 135

4.3 Ramsey numbers, bounds, and asymptotics 139

4.4 The probabilistic method 143

4.5 Sums 145

4.6 Van der Waerden's theorem 146

Notes 150

5 Codes 153

5.1 Binary codes 153

5.2 Perfect codes 156

5.3 Hamming codes 158

5.4 The Fano Configuration 162

Notes 168

6 Designs 171

6.1 t-designs 171

CONTENTS ix

6.2 Block designs 175

6.3 Projective planes 180

6.4 Latin squares 182

6.5 MOLS and OODs 185

6.6 Hadamard matrices 188

6.7 The Golay code and S(5, 8, 24) 194

6.8 Lattices and sphere packings 197

6.9 Leech's lattice 199

Notes 201

A Web Resources 205

B Notation 207

Exercise Solutions 211

References 225

Index 227

Rezensionen

"Indeed, Erickson's Introduction to Combinatoricsis
appealing on precisely the count that it is very
user-friendly." (MAA Reviews, 5 January
2014)

Textauszug

CHAPTER 1

BASIC COUNTING METHODS

We begin our tour of combinatorics by investigating elementary methods for counting finite sets. How many ways are there to choose a subset of a set? How many permutations of a set are there? We will explore these and other such questions.

1.1 The multiplication principle

We start with the simplest counting problems. Many of these problems are concerned with the number of ways in which certain choices can occur.

Here is a useful counting principle: If one choice can be made in x ways and another choice in y ways, and the two choices are independent, then the two choices together can be made in xy ways. This rule is called the “multiplication principle.”

EXAMPLE 1.1

Suppose that you have three hats and four scarves. How many different hat and scarf outfits can you choose?

Solution: By the multiplication principle, there are 3 · 4 = 12 different outfits. Let’s call the hats h1, h2, and h3 and the scarves s1, s2, s3, and s4. Then we can list the different outfits as follows:

EXAMPLE 1.2

At the French restaurant Chacun à Son Got, there are three choices for the appetizer, four choices for the entrée, and five choices for the dessert. How many different dinner orders (consisting of appetizer, entrée, and dessert) can we make?

Solution: The answer is 3 · 4 · 5 = 60, and it isn’t difficult to list all the possibilities. Let’s call the appetizers a1, a2, and a3, the entrées e1, e2, e3, and e4, and the desserts d1, d2, d3, d4, and d5. Then the different possible dinners are as follows:

EXAMPLE 1.3

A variable name in a certain computer programming language consists of a letter (A through Z), a letter followed by another letter, or a letter followed by a digit (0 through 9). How many different variable names are possible?

Solution: There are 26 variable names consisting of a single letter, 262 variable names consisting of two letters, and 26 · 10 variable names consisting of a letter followed by a digit. Altogether, there are

variable names.

EXAMPLE 1.4 Number of binary strings

How many binary strings of length n are there?

Solution: There are two choices (0 or 1) for each element in the string. Hence, there are 2n possible strings.

For instance, there are 23 = 8 binary strings of lenght 3:

EXAMPLE 1.5 Number of subsets of a set

Let S be a set of n elements. How many subsets does S have?

Solution: There are two choices for each element of S; it can be in the subset or not in the subset. This means that there are 2n subsets altogether.

For instance, let S = {a, b, c}, so that n = 3. Then S has 23 = 8 subsets:

EXERCISES

1.1 A person making a book display wants to showcase a novel, a history book, and a travel guide. There are four choices for the novel, two choices for the history book, and 10 choices for the travel guide. How many choices are possible for the three books?

1.2 A license consists of three digits (0 through 9), followed by a letter (A through Z), followed by another digit. How many different licenses are there?

1.3 How many strings of length 10 are there in which the symbols may be 0, 1, or 2?

1.4 How many subsets of the set {a, b, c, d, e, f, g, h, i, j} do not contain both a and b?

1.5 How many binary strings of length 99 have an odd number of 1′s?

1.6 How many functions map the set {a, b, c} to the set {w, x, y, z}?

1.7 Let X be an n-element set. How many functions from X to X are there?

1.8 Let X = {1, 2, 3,…,2n}. How many functions from X to X are there such that each even number is mapped to an even number and each odd number is mapped to an odd number?

1.2 Permutations

One of the fundamental concepts of counting is that of a permutation. A permutation of a set is an ordering of the elements of the set.

EXAMPLE 1.6

List the permutations of the set {a, b, c}.

Solution: There are six permutations:

We set

(1.1)

The expression n! is called n factorial.

We see in the above example that the number of permutations is 6 = 3!.

There are n! permutations of an n-element set. The reason is there are n choices for the first element in the permutation. Once that choice is made, there are n – 1 choices for the second element, and then n – 2 choices for the third element, and so on. Altogether, there are

choices, which is n!

EXAMPLE 1.7

In how many ways can the letters of the word MISSISSIPPI be arranged?

Solution: This is an example of a permutation of a set with repeated elements. There are 11! permutations of the 11 letters of MISSISSIPPI, but there is much duplication.

We need to divide by the number of permutations of the four I’s, the four S’s, the two P’s, and the one M. Thus, the number of different arrangements of the letters is

Let S be an n-element set, where n ≥ 0. How many permutations of k elements of S are there, where 1 ≤ k ≤ n? There are n choices for the first element, n − 1 choices for the second element,…,n – k + 1 choices for the kth element. Hence, there are

choices altogether. This expression, denoted P(n, k), may be written as

(1.2)

(Notice that we now allow k = 0, which gives P(n, 0) = 1.) We can interpret this formula as a MISSISSIPPI-type problem. The selected elements may be denoted X1,…,Xk, and the nonselected elements all denoted with the letter N (for nonselected).

EXAMPLE 1.8

An organization has 100 members. How many ways may they select a president, a vice-president, a secretary, and a treasurer?

Solution: The number of ways to select a permutation of four people from a group of 100 is

EXERCISES

1.9 A teacher has eight books to put on a shelf. How many different orderings of the books are possible?

1.10 You have three small glasses, four medium-size glasses, and five large glasses. If glasses of the same size are indistinguishable, how many ways can you arrange the glasses in a row?

1.11 A couple plans to visit three selected cities in Germany, followed by four selected cities in France, followed by five selected cities in Spain. In how many ways can the couple order their itinerary?

1.12 A student has 10 books but only room for six of them on a shelf. How many permutations of the books are possible on the shelf?

1.13 A librarian wants to arrange four astronomy books, five medical books, and six religious books on a shelf. Books of the same category should be grouped together, but otherwise the books may be put in any order. How Many orderings are possible?

1.14 In how many ways can you arrange the letters of the word RHODODENDRON?

1.15 How many one-to-one functions are there from the set {a, b, c} to the set {t, u, v, w, x, y, z}?

1.16 Let X be an n-element set. How many functions from X to X are not one-to-one?

1.17 Find a formula for the number of different binary relations possible on a set of n elements.

1.3 Combinations

Another fundamental concept of counting is that of a combination. A combination from a set is an unordered subset (of a given size) of the set.

For convenience, we sometimes refer to an n-element set as an n-set and a k-element subset as a k-subset. Also, we use the notation N = {1, 2, 3,…,} and Nm = {1, 2, 3,…,m}.

Let S be an n-set, where n ≥ 0. How many k-subsets of S are there, where 0 ≤ k ≤ n? We can regard this as a MISSISSIPPI-type problem, i.e., a problem of permutations with repeated elements. Let X denote selected elements and N denote nonselected elements. Then the number of combinations is the number of arrangements of k X’s and n – k N’s, since each such arrangement specifies a combination.

Hence, the number of combinations, denoted C(n, k), is given by

(1.3)

We call this expression “n choose k.” We set C(n, k) = 0 for k < 0 and k > n.

For example, with n = 5 and k = 3, we have C(5, 3) = 5!/(3!2!) = 10 combinations of three elements from the set S = {a, b, c, d, e}, as shown below with the corresponding arrangements of X’s and N’s:

The values of...

Produkt-Details

• Erscheint lt. Verlag: 13.6.2013
• Reihe/Serie: Wiley-Interscience Series in Discrete Mathematics and Optimization
• Reihe/Serie: Wiley-Interscience Series in Discrete Mathematics and Optimization
• Reihe/Serie: Wiley Series in Discrete Mathematics and Optimization
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Graphentheorie
• Themenwelt: Technik
• Schlagworte: combinatorics • Discrete Mathematics • Diskrete Mathematik • Electrical & Electronics Engineering • Elektrotechnik u. Elektronik • Introduction to Combinatorics, Ramsey theory, error-correcting codes, combinatorial designs, basic counting methods, generating functions, the pigeonhole principle, • Kombinatorik • Mathematics • Mathematik • Numerical Methods & Algorithms • Numerische Methoden u. Algorithmen
• ISBN-10: 1-118-63758-5 / 1118637585
• ISBN-13: 978-1-118-63758-6 / 9781118637586