Discrete mathematics
Subtitle: elementary and beyond
By: L. Lovász, J. Pelikán, K. Vesztergombi.
Contributors: Pelikán, J.; Vsztergombi, K.
Series: Undergraduate texts in mathematics
Publisher: Springer
Published: 2003
Place of publication: New York
Language: eng
Number of pages: 290
Subjects: Mathematics.; Computer science -- Mathematics.
Description: Discrete mathematics is quickly becoming one of the most important areas of mathematical research, with applications to cryptography, linear programming, coding theory and the theory of computing. This book is aimed at undergraduate mathematics and computer science students interested in developing a feeling for what mathematics is all about, where mathematics can be helpful, and what kinds of questions mathematicians work on. The authors discuss a number of selected results and methods of discrete mathematics, mostly from the areas of combinatorics and graph theory, with a little number theory, probability, and combinatorial geometry. Wherever possible, the authors use proofs and problem solving to help students understand the solutions to problems. In addition, there are numerous examples, figures and exercises spread throughout the book. László Lovász is a Senior Researcher in the Theory Group at Microsoft Corporation. He is a recipient of the 1999 Wolf Prize and the Gödel Prize for the top paper in Computer Science. József Pelikán is Professor of Mathematics in the Department of Algebra and Number Theory at Eötvös Loránd University, Hungary. In 2002, he was elected Chairman of the Advisory Board of the International Mathematical Olympiad. Katalin Vesztergombi is Senior Lecturer in the Department of Mathematics at the University of Washington.
Notes: Includes index.
Table of contents: title: Preface
pagenum: v; label: 1
title: Let's Count!
pagenum: 1; label: 1.1
title: A Party
pagenum: 1; label: 1.2
title: Sets and the Like
pagenum: 4; label: 1.3
title: The Number of Subsets
pagenum: 9; label: 1.4
title: The Approximate Number of Subsets
pagenum: 14; label: 1.5
title: Sequences
pagenum: 15; label: 1.6
title: Permutations
pagenum: 17; label: 1.7
title: The Number of Ordered Subsets
pagenum: 19; label: 1.8
title: The Number of Subsets of a Given Size
pagenum: 20; label: 2
title: Combinatorial Tools
pagenum: 25; label: 2.1
title: Induction
pagenum: 25; label: 2.2
title: Comparing and Estimating Numbers
pagenum: 30; label: 2.3
title: Inclusion-Exclusion
pagenum: 32; label: 2.4
title: Pigeonholes
pagenum: 34; label: 2.5
title: The Twin Paradox and the Good Old Logarithm
pagenum: 37; label: 3
title: Binomial Coefficients and Pascal's Triangle
pagenum: 43; label: 3.1
title: The Binomial Theorem
pagenum: 43; label: 3.2
title: Distributing Presents
pagenum: 45; label: 3.3
title: Anagrams
pagenum: 46; label: 3.4
title: Distributing Money
pagenum: 48; label: 3.5
title: Pascal's Triangle
pagenum: 49; label: 3.6
title: Identities in Pascal's Triangle
pagenum: 50; label: 3.7
title: A Bird's-Eye View of Pascal's Triangle
pagenum: 54; label: 3.8
title: An Eagle's-Eye View: Fine Details
pagenum: 57; label: 4
title: Fibonacci Numbers
pagenum: 65; label: 4.1
title: Fibonacci's Exercise
pagenum: 65; label: 4.2
title: Lots of Identities
pagenum: 68; label: 4.3
title: A Formula for the Fibonacci Numbers
pagenum: 71; label: 5
title: Combinatorial Probability
pagenum: 77; label: 5.1
title: Events and Probabilities
pagenum: 77; label: 5.2
title: Independent Repetition of an Experiment
pagenum: 79; label: 5.3
title: The Law of Large Numbers
pagenum: 80; label: 5.4
title: The Law of Small Numbers and the Law of Very Large Numbers
pagenum: 83; label: 6
title: Integers, Divisors, and Primes
pagenum: 87; label: 6.1
title: Divisibility of Integers
pagenum: 87; label: 6.2
title: Primes and Their History
pagenum: 88; label: 6.3
title: Factorization into Primes
pagenum: 90; label: 6.4
title: On the Set of Primes
pagenum: 93; label: 6.5
title: Fermat's "Little" Theorem
pagenum: 97; label: 6.6
title: The Euclidean Algorithm
pagenum: 99; label: 6.7
title: Congruences
pagenum: 105; label: 6.8
title: Strange Numbers
pagenum: 107; label: 6.9
title: Number Theory and Combinatorics
pagenum: 114; label: 6.10
title: How to Test Whether a Number is a Prime?
pagenum: 117; label: 7
title: Graphs
pagenum: 125; label: 7.1
title: Even and Odd Degrees
pagenum: 125; label: 7.2
title: Paths, Cycles, and Connectivity
pagenum: 130; label: 7.3
title: Eulerian Walks and Hamiltonian Cycles
pagenum: 135; label: 8
title: Trees
pagenum: 141; label: 8.1
title: How to Define Trees
pagenum: 141; label: 8.2
title: How to Grow Trees
pagenum: 143; label: 8.3
title: How to Count Trees?
pagenum: 146; label: 8.4
title: How to Store Trees
pagenum: 148; label: 8.5
title: The Number of Unlabeled Trees
pagenum: 153; label: 9
title: Finding the Optimum
pagenum: 157; label: 9.1
title: Finding the Best Tree
pagenum: 157; label: 9.2
title: The Traveling Salesman Problem
pagenum: 161; label: 10
title: Matchings in Graphs
pagenum: 165; label: 10.1
title: A Dancing Problem
pagenum: 165; label: 10.2
title: Another Matching Problem
pagenum: 167; label: 10.3
title: The Main Theorem
pagenum: 169; label: 10.4
title: How to Find a Perfect Matching
pagenum: 171; label: 11
title: Combinatorics in Geometry
pagenum: 179; label: 11.1
title: Intersections of Diagonals
pagenum: 179; label: 11.2
title: Counting Regions
pagenum: 181; label: 11.3
title: Convex Polygons
pagenum: 184; label: 12
title: Euler's Formula
pagenum: 189; label: 12.1
title: A Planet Under Attack
pagenum: 189; label: 12.2
title: Planar Graphs
pagenum: 192; label: 12.3
title: Euler's Formula for Polyhedra
pagenum: 194; label: 13
title: Coloring Maps and Graphs
pagenum: 197; label: 13.1
title: Coloring Regions with Two Colors
pagenum: 197; label: 13.2
title: Coloring Graphs with Two Colors
pagenum: 199; label: 13.3
title: Coloring Graphs with Many Colors
pagenum: 202; label: 13.4
title: Map Coloring and the Four Color Theorem
pagenum: 204; label: 14
title: Finite Geometries, Codes, Latin Squares, and Other Pretty Creatures
pagenum: 211; label: 14.1
title: Small Exotic Worlds
pagenum: 211; label: 14.2
title: Finite Affine and Projective Planes
pagenum: 217; label: 14.3
title: Block Designs
pagenum: 220; label: 14.4
title: Steiner Systems
pagenum: 224; label: 14.5
title: Latin Squares
pagenum: 229; label: 14.6
title: Codes
pagenum: 232; label: 15
title: A Glimpse of Complexity and Cryptography
pagenum: 239; label: 15.1
title: A Connecticut Class in King Arthur's Court
pagenum: 239; label: 15.2
title: Classical Cryptography
pagenum: 242; label: 15.3
title: How to Save the Last Move in Chess
pagenum: 244; label: 15.4
title: How to Verify a Password—Without Learning It
pagenum: 246; label: 15.5
title: How to Find These Primes
pagenum: 246; label: 15.6
title: Public Key Cryptography
pagenum: 247; label: 16
title: Answers to Exercises
pagenum: 251; title: Index
pagenum: 287