《discrete mathematics：elementary and beyodn P290》

1Let’s Count!1

1.1 A Party1

1.2 Sets and the Like4

1.3 The Number of Subsets9

1.4 The Approximate Number of Subsets14

1.5 Sequences15

1.6 Permutations17

1.7 The Number of Ordered Subsets19

1.8 The Number of Subsets of a Given Size20

2Combinatorial Tools25

2.1 Induction25

2.2 Comparing and Estimating Numbers30

2.3 Inclusion-Exclusion32

2.4 Pigeonholes34

2.5 The Twin Paradox and the Good Old Logarithm37

3Binomial Coefficients and Pascal’s Triangle43

3.1 The Binomial Theorem43

3.2 Distributing Presents45

3.3 Anagrams46

3.4 Distributing Money48

3.5 Pascals Triangle49

3.6 Identities in Pascals Triangle50

3.7 A Birds-Eyc View of Pascals Triangle54

3.8 An Eagles-Eye View: Fine Details57

4Fibonacci Numbers65

4.1 Fibonaccis Exercise65

4.2 Lots of Identities68

4.3 A Forinula for the Fibonacci Nurnbers71

5Combinatorial Probability77

5.1 Events and Probabilities77

5.2 Independent Repetition of an Experiment79

5.3 The Law of Large Numbers80

5.4 The Law of Small Numbers and the Law of Very Large Nuun-bers83

6Integers, Divisors, and Primes87

6.1 Divisibility of Integers87

6.2 Primes and Their History88

6.3 Factorization into Primes90

6.4 On the Set of Primes93

6.5 Fermat’s“Littlc” Theorem97

6.6 The Euclidean Algorithm99

6.7 Congrucnccs105

6.8 Strange Numbers107

6.9 Nnnnber Theory and Conmbinatorics114

6.10 How to Tcst Whether a Number is a Prime?117

7Graphs125

7.1 Even and Odd Degrees125

7.2 Paths, Cycles, and Connectivity130

7.3 Eulerian Walks and Hamiltonian Cycles135

8Trees141

8.1 How to Define Trees141

8.2 How to Grow Trees143

8.3 How to Count Trees?146

8.4 How to Store Trees148

8.5 The Number of Unlabeled Trees153

9Finding the Optimum157

9.1 Finding the Best Tree157

9.2 The Traveling Salesman Problem161

10 Matchings in Graphs165

10.1 A Dancing Problem165

10.2 Another matching problem167

10.3 The Main Theorem169

10.4 How to Find a Perfect Matching171

11 Combinatorics in Geometry179

11.1 Intersections of Diagonals179

11.2 Counting regions181

11.3 Convex Polygons184

12 Euler’s Formula189

12.1 A Planet Under Attack189

12.2 Planar Graphs192

12.3 Eulers Formula for Polyhedra194

13 Coloring Maps and Graphs197

13.1 Coloring Regions with Two Colors197

13.2 Coloring Graphs with Two Colors199

13.3 Coloring graphs with many colors202

13.4 Mlap Coloring and the Four Color Theorem204

14 Finite Geometries, Codes,Latin Squares,and Other Pretty Creatures211

14.1 Small Exotic Worlds211

14.2 Finite Affine and Projective Planes217

14.3 Block Designs220

14.4 Steiner Systems224

14.5 Latin Squares229

14.6 Codes232

15 A Glimpse of Complexity and Cryptography239

15.1 A Connecticut Class in King Arthur’s Court239

15.2 Classical Cryptography242

15.3 How to Save the Last Move in Chess244

15.4 How to Verify a Password—Without Learning it246

15.5 How to Find These Primes246

15.6 Public Key Cryptography247

16 Answers to Exercises251

Index287