Discrete mathematics : elementary and beyond = 离散数学 : 基础与提高 /

preface.

1 let's count!

1.1 a party

1.2 sets and the like

1.3 the number of subsets

1.4 the approximate number of subsets

1.5 sequences

1.6 permutations

1.7 the number of ordered subsets

1.8 the number of subsets of a given size

2 combinatorial tools

2.1 induction

2.2 comparing and estimating numbers

2.3 inclusion-exclusion

2.4 pigeonholes

2.5 the twin paradox and the good old logarithm

3 binomial coefficients and pascal's triangle

3.1 the binomial theorem

3.2 distributing presents

3.3 anagrams

.3.4 distributing money

3.5 pascal's triangle

3.6 identities in pascal's triangle

3.7 a bird's-eye view of pascal's triangle

3.8 all eagle's-eye view: fine details

4 fibonacci numbers

4.1 fil)onacci's exercise

4.2 lots of identities

4.3 a formula for tire fibonacci numbers

5 combinatorial probability

5.1 events and probabilities

5.2 independent repetition of an experiment

5.3 the law of large numbers

5.4 the law of small numbers and the law of very large numbers

6 integers, divisors, and primes

6.1 divisibility of integers

6.2 primes and their history

6.3 factorization into primes

6.,1 on the set of primes

6.5 fermat's "little" theorem

6.6 the euclidean algorithm

6.7 congruences.

6.8 strange numbers

6.9 number theory and combinatorics

6.10 how to test whether a number is a prime?..

7 graphs

7.1 even and odd degrees

7.2 paths, cycles, and connectivity

7.3 eulerian walks and hamiltonian cycles

8 trees

8.1 how to define trees

8.2 how to grow trees

8.3 how to count trees?

8.4 how to store trees

8.5 the number of unlabeled trees

9 finding the optimum

9.1 finding the best tree

9.2 the traveling salesman problem

10 matchings in graphs

10.1 a dancing problem

10.2 another matching problem

10.3 the main theorem

10.4 how to find a perfect matching

11 combinatorics in geometry

11.1 intersections of diagonals

11.2 counting regions

11.3 convex polygons

12 euler's formula

12.1 a planet under attack

12.2 planar graphs

12.3 euler's formula for polyhedra

13 coloring maps and graphs

13.1 coloring regions with two colors

13.2 coloring graphs with two colors

13.3 coloring graphs with many colors

13.4 map coloring and the four color theorem

14 finite geometries, codes,latin squares,and other pretty creatures

14.1 small exotic worlds

14.2 finite affine and projective planes

14.3 block designs

14.4 steiner systems

14.5 latin squares

14.6 codes

15 a glimpse of complexity and cryptography

15.1 a connecticut class in king arthur's court

15.2 classical cryptography

15.3 how to save the last move in chess

15.4 how to verify a password--without learning it

15.5 how to find these primes

15.6 public key cryptography

16 answers to exercises

index...