Discrete mathematics : elementary and beyond
L. Lovász, J. Pelikán, K. Vesztergombi
18250152
TABLE DES MATIÈRES

Preface             vii

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

5 février 2005