Table of contents for Discrete mathematics : elementary and beyond / L. Lov‚asz, J. Pelik‚an, K. Vesztergombi.


Bibliographic record and links to related information available from the Library of Congress catalog. Note: Electronic data is machine generated. May be incomplete or contain other coding.


Counter




Preface                                                v
1 Let's Count!                                            1
1.1  A  Party  .............................           1
1.2 Sets and the Like ........................         4
1.3 The Number of Subsets ..........   ..........      9
1.4 The Approximate Number of Subsets ............ .   14
1.5 Sequences ............................             15
1.6 Permutations ...................        .......    17
1.7 The Number of Ordered Subsets ...............      19
1.8 The Number of Subsets of a Given Size ..........  20
2 Combinatorial Tools                                    25
2.1  Induction  ............................           25
2.2 Comparing and Estimating Numbers .. ...........    30
2.3  Inclusion-Exclusion  .......................      32
2.4 Pigeonholes ...........................            34
2.5 The Twin Paradox and the Good Old Logarithm ......  37
3 Binomial Coefficients and Pascal's Triangle            43
3.1  The Binomial Theorem  ....................       43
3.2 Distributing Presents .  ...................       45
3.3 Anagrams .......................... .             46
3.4 Distributing Money .......................        48



3.5 Pascal's Triangle .........................          49
3.6 Identities in Pascal's Triangle .................    50
3.7 A Bird's-Eye View of Pascal's Triangle .....  .......  54
3.8 An Eagle's-Eye View: Fine Details ......... .... .   57
4 Fibonacci Numbers                                         65
4.1  Fibonacci's Exercise ......................         65
4.2 Lots of Identities ........................          68
4.3 A Formula for the Fibonacci Numbers ............     71
5 Combinatorial Probability                                 77
5.1 Events and Probabilities .................... 77
5.2 Independent Repetition of an Experiment ........ .   79 
5.3 The Law of Large Numbers ..................          80
5.4 The Law of Small Numbers and the Law of Very Large 
    Numbers        ............         ............       83
6 Integers, Divisors, and Primes                            87
6.1 Divisibility of Integers ..  ...................     87
6.2 Primes and Their History ...................         88
6.3  Factorization into Primes  ...............   ....   90
6.4 On the Set of Primes . .....................         93
6.5 Fermat's "Little" Theorem  ..................        97
6.6 The Euclidean Algorithm  ...................         99
6.7  Congruences ...........................            105
6.8 Strange Numbers ........................107
6.9 Number Theory and Combinatorics ............. 114
6.10 How to Test Whether a Number is a Prime? ....... . 117
7 Graphs                                                  125
7.1 Even and Odd Degrees ..................... 125
7.2 Paths, Cycles, and Connectivity ................ 130
7.3 Eulerian Walks and Hamiltonian Cycles ...........   135
8 Trees                                                   141
8.1 How to Define Trees ...................... 141
8.2 How to Grow Trees ....................... 143
8.3  How  to Count Trees? ......................        146
8.4 How to Store Trees .............................148
8.5 The Number of Unlabeled Trees ............... 153
9 Finding the Optimum                                     157
9.1 Finding the Best Tree ..................... 157
9.2 The Traveling Salesman Problem ............... 161
10 Matchings in Graphs                                    165



10.1 A Dancing Problem  .......................         165
10.2 Another matching problem  .................. 167
10.3  The Main Theorem  ....................            169
10.4 How to Find,a Perfect Matching .. .............    171
11 Combinatorics in Geometry                              179
11.1 Intersections of Diagonals .. ................. 179
11.2  Counting regions  ........................        181
11.3 Convex Polygons ......................... 184
12 Euler's Formula                                         189
12.1 A Planet Under Attack  ........................    189
12.2 Planar Graphs ......................... 192
12.3 Euler's Formula for Polyhedra ................. 194
13 Coloring Maps and Graphs                               197
13.1 Coloring Regions with Two Colors .............. 197
13.2 Coloring Graphs with Two Colors  .......... ... .  199
13.3 Coloring graphs with many colors ............... 202
13.4 Map Coloring and the Four Color Theorem  ........ . 204
14 Finite Geometries, Codes, Latin Squares,
   and Other Pretty Creatures                              211
14.1 Small Exotic Worlds ............ .......... 211
14.2 Finite Affine and Projective Planes .............. 217
14.3 Block Designs .......................... 220
14.4 Steiner Systems ......................... 224
14.5  Latin  Squares  ..........................        229
14.6 Codes ............................. 232
15 A Glimpse of Complexity and Cryptography               239
15.1 A Connecticut Class in King Arthur's Court ........ . 239 
15.2  Classical Cryptography  ....................      242
15.3 How to Save the Last Move in Chess .............. . 244
15.4 How to Verify a Password-Without Learning it ...... 246 
15.5 How to Find These Primes .................. 246
15.6 Public Key Cryptography ................... 247
16 Answers to Exercises                                   251
Index                                                   287





Library of Congress Subject Headings for this publication: Mathematics, Computer science Mathematics