离散及组合数学 第5版 英文PDF电子书下载

PART 1 Fundamentals of Discrete Mathematics 1

1 Fundamental Principles of Counting 3

1.1 The Rules of Sum and Product 3

1.2 Permutations 6

1.3 Combinations:The Binomial Theorem 14

1.4 Combinations with Repetition 26

1.5 The Catalan Numbers(Optional) 36

1.6 Summary and Historical Review 41

2 Fundamentals of Logic 47

2.1 Basic Connectives and Truth Tables 47

2.2 Logical Equivalence:The Laws of Logic 55

2.3 Logical Implication:Rules of Inference 67

2.4 The Use of Quantifiers 86

2.5 Quantifiers,Definitions,and the Proofs of Theorems 103

2.6 Summary and Historical Review 117

3 Set Theory 123

3.1 Sets and Subsets 123

3.2 Set Operations and the Laws of Set Theory 136

3.3 Counting and Vean Diagrams 148

3.4 A First Word on Probability 150

3.5 The Axioms of Probability(Optional) 157

3.6 Conditional Probability:Independence(Optional) 166

3.7 Discrete Random Variables(Optional) 175

3.8 Summary and Historical Review 186

4 Properties of the Integers:Mathematical Induction 193

4.1 The Well-Ordering Principle:Mathematical Induction 193

4.2 Recursive Definitions 210

4.3 The Division Algorithm:Prime Numbers 221

4.4 The Greatest Common Divisor:The Euclidean Algorithm 231

4.5 The Fundamental Theorem of Arithmetic 237

4.6 Summary and Historical Review 242

5 Relations and Functions 247

5.1 Cartesian Products and Relations 248

5.2 Functions:Plain and One-to-One 252

5.3 Onto Functions:Stirling Numbers of the Second Kind 260

5.4 Special Functions 267

5.5 The Pigeonhole Principle 273

5.6 Function Composition and Inverse Functions 278

5.7 Computational Complexity 289

5.8 Analysis of Algorithms 294

5.9 Summary and Historical Review 302

6 Languages:Finite State Machines 309

6.1 Language:The Set Theory of Strings 309

6.2 Finite State Machines:A First Encounter 319

6.3 Finite State Machines:A Second Encounter 326

6.4 Summary and Historical Review 332

7 Relations:The Second Time Around 337

7.1 Relations Revisited:Properties of Relations 337

7.2 Computer Recognition:Zero-One Matrices and Directed Graphs 344

7.3 Partial Orders:Hasse Diagrams 356

7.4 Equivalence Relations and Partitions 366

7.5 Finite State Machines:The Minimization Process 371

7.6 Summary and Historical Review 376

PART 2 Further Topics in Enumeration 383

8 The Principle of Inclusion and Exclusion 385

8.1 The Principle of Inclusion and Exclusion 385

8.2 Generalizations of the Principle 397

8.3 Derangements:Nothing Is in Its Right Place 402

8.4 Rook Polynomials 404

8.5 Arrangements with Forbidden Positions 406

8.6 Summary and Historical Review 411

9 Generating Functions 415

9.1 Introductory Examples 415

9.2 Definition and Examples:Calculational Techniques 418

9.3 Partitions of Integers 432

9.4 The Exponential Generating Function 436

9.5 The Summation Operator 440

9.6 Summary and Historical Review 442

10 Recurrence Relations 447

10.1 The First-Order Linear Recurrence Relation 447

10.2 The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients 456

10.3 The Nonhomogeneous Recurrence Relation 470

10.4 The Method of Generating Functions 482

10.5 A Special Kind of Nonlinear Recurrence Relation(Optional) 487

10.6 Divide-and-Conquer Algorithms(Optional) 496

10.6 Summary and Historical Review 505

PART 3 Graph Theory and Applications 511

11 An Introduction to Graph Theory 513

11.1 Definitions and Examples 513

11.2 Subgraphs,Complements,and Graph Isomorphism 520

11.3 Vertex Degree:Euler Trails and Circuits 530

11.4 Planar Graphs 540

11.5 Hamilton Paths and Cycles 556

11.6 Graph Coloring and Chromatic Polynomials 564

11.7 Summary and Historical Review 573

12 Trees 581

12.1 Definitions,Properties,and Examples 581

12.2 Rooted Trees 587

12.3 Trees and Sorting 605

12.4 Weighted Trees and Prefix Codes 609

12.5 Biconnected Components and Articulation Points 615

12.6 Summary and Historical Review 622

13 Optimization and Matching 631

13.1 Dijkstra's Shortest-Path Algorithm 631

13.2 Minimal Spanning Trees:The Algorithms of Kruskal and Prim 638

13.3 Transport Networks:The Max-Flow Min-Cut Theorem 644

13.4 Matching Theory 659

13.5 Summary and Historical Review 667

PART 4 Modern Applied Algebra 671

14 Rings and Modular Arithmetic 673

14.1 The Ring Structure:Definition and Examples 673

14.2 Ring Properties and Substructures 679

14.3 The Integers Modulo n 686

14.4 Ring Homomorphisms and Isomorphisms 697

14.5 Summary and Historical Review 705

15 Boolean Algebra and Switching Functions 711

15.1 Switching Functions:Disjunctive and Conjunctive Normal Forms 711

15.2 Gating Networks:Minimal Sums of Products:Karnaugh Maps 719

15.3 Further Applications:Don't-Care Conditions 729

15.4 The Structure of a Boolean Algebra(Optional) 733

15.5 Summary and Historical Review 742

16 Groups,Coding Theory,and Polya's Method of Enumeration 745

16.1 Definition,Examples,and Elementary Properties 745

16.2 Homomorphisms,Isomorphisms,and Cyclic Groups 752

16.3 Cosets and Lagrange's Theorem 757

16.4 The RSA Cryptosystem(Optional) 759

16.5 Elements of Coding Theory 761

16.6 The Hamming Metric 766

16.7 The Parity-Check and Generator Matrices 769

16.8 Group Codes:Decoding with Coset Leaders 773

16.9 Hamming Matrices 777

16.10 Counting and Equivalence:Burnside's Theorem 779

16.11 The Cycle Index 785

16.12 The Pattern Inventory:Polya's Method of Enumeration 789

16.13 Summary and Historical Review 794

17 Finite Fields and Combinatorial Designs 799

17.1 Polynomial Rings 799

17.2 Irreducible Polynomials:Finite Fields 806

17.3 Latin Squares 815

17.4 Finite Geometries and Affine Planes 820

17.5 Block Designs and Projective Planes 825

17.6 Summary and Historical Review 830

Appendix 1 Exponential and Logarithmic Functions 1

Appendix 2 Matrices,Matrix Operations,and Determinants 11

Appendix 3 Countable and Uncountable Sets 23

Solutions 1