离散及组合数学 第5版 英文PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

PART 1 Fundamentals of Discrete Mathematics1

1 Fundamental Principles of Counting3

1.1 The Rules of Sum and Product3

1.2 Permutations6

1.3 Combinations:The Binomial Theorem14

1.4 Combinations with Repetition26

1.5 The Catalan Numbers(Optional)36

1.6 Summary and Historical Review41

2 Fundamentals of Logic47

2.1 Basic Connectives and Truth Tables47

2.2 Logical Equivalence:The Laws of Logic55

2.3 Logical Implication:Rules of Inference67

2.4 The Use of Quantifiers86

2.5 Quantifiers,Definitions,and the Proofs of Theorems103

2.6 Summary and Historical Review117

3 Set Theory123

3.1 Sets and Subsets123

3.2 Set Operations and the Laws of Set Theory136

3.3 Counting and Vean Diagrams148

3.4 A First Word on Probability150

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 Review186

4 Properties of the Integers:Mathematical Induction193

4.1 The Well-Ordering Principle:Mathematical Induction193

4.2 Recursive Definitions210

4.3 The Division Algorithm:Prime Numbers221

4.4 The Greatest Common Divisor:The Euclidean Algorithm231

4.5 The Fundamental Theorem of Arithmetic237

4.6 Summary and Historical Review242

5 Relations and Functions247

5.1 Cartesian Products and Relations248

5.2 Functions:Plain and One-to-One252

5.3 Onto Functions:Stirling Numbers of the Second Kind260

5.4 Special Functions267

5.5 The Pigeonhole Principle273

5.6 Function Composition and Inverse Functions278

5.7 Computational Complexity289

5.8 Analysis of Algorithms294

5.9 Summary and Historical Review302

6 Languages:Finite State Machines309

6.1 Language:The Set Theory of Strings309

6.2 Finite State Machines:A First Encounter319

6.3 Finite State Machines:A Second Encounter326

6.4 Summary and Historical Review332

7 Relations:The Second Time Around337

7.1 Relations Revisited:Properties of Relations337

7.2 Computer Recognition:Zero-One Matrices and Directed Graphs344

7.3 Partial Orders:Hasse Diagrams356

7.4 Equivalence Relations and Partitions366

7.5 Finite State Machines:The Minimization Process371

7.6 Summary and Historical Review376

PART 2 Further Topics in Enumeration383

8 The Principle of Inclusion and Exclusion385

8.1 The Principle of Inclusion and Exclusion385

8.2 Generalizations of the Principle397

8.3 Derangements:Nothing Is in Its Right Place402

8.4 Rook Polynomials404

8.5 Arrangements with Forbidden Positions406

8.6 Summary and Historical Review411

9 Generating Functions415

9.1 Introductory Examples415

9.2 Definition and Examples:Calculational Techniques418

9.3 Partitions of Integers432

9.4 The Exponential Generating Function436

9.5 The Summation Operator440

9.6 Summary and Historical Review442

10 Recurrence Relations447

10.1 The First-Order Linear Recurrence Relation447

10.2 The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients456

10.3 The Nonhomogeneous Recurrence Relation470

10.4 The Method of Generating Functions482

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

10.6 Divide-and-Conquer Algorithms(Optional)496

10.6 Summary and Historical Review505

PART 3 Graph Theory and Applications511

11 An Introduction to Graph Theory513

11.1 Definitions and Examples513

11.2 Subgraphs,Complements,and Graph Isomorphism520

11.3 Vertex Degree:Euler Trails and Circuits530

11.4 Planar Graphs540

11.5 Hamilton Paths and Cycles556

11.6 Graph Coloring and Chromatic Polynomials564

11.7 Summary and Historical Review573

12 Trees581

12.1 Definitions,Properties,and Examples581

12.2 Rooted Trees587

12.3 Trees and Sorting605

12.4 Weighted Trees and Prefix Codes609

12.5 Biconnected Components and Articulation Points615

12.6 Summary and Historical Review622

13 Optimization and Matching631

13.1 Dijkstra's Shortest-Path Algorithm631

13.2 Minimal Spanning Trees:The Algorithms of Kruskal and Prim638

13.3 Transport Networks:The Max-Flow Min-Cut Theorem644

13.4 Matching Theory659

13.5 Summary and Historical Review667

PART 4 Modern Applied Algebra671

14 Rings and Modular Arithmetic673

14.1 The Ring Structure:Definition and Examples673

14.2 Ring Properties and Substructures679

14.3 The Integers Modulo n686

14.4 Ring Homomorphisms and Isomorphisms697

14.5 Summary and Historical Review705

15 Boolean Algebra and Switching Functions711

15.1 Switching Functions:Disjunctive and Conjunctive Normal Forms711

15.2 Gating Networks:Minimal Sums of Products:Karnaugh Maps719

15.3 Further Applications:Don't-Care Conditions729

15.4 The Structure of a Boolean Algebra(Optional)733

15.5 Summary and Historical Review742

16 Groups,Coding Theory,and Polya's Method of Enumeration745

16.1 Definition,Examples,and Elementary Properties745

16.2 Homomorphisms,Isomorphisms,and Cyclic Groups752

16.3 Cosets and Lagrange's Theorem757

16.4 The RSA Cryptosystem(Optional)759

16.5 Elements of Coding Theory761

16.6 The Hamming Metric766

16.7 The Parity-Check and Generator Matrices769

16.8 Group Codes:Decoding with Coset Leaders773

16.9 Hamming Matrices777

16.10 Counting and Equivalence:Burnside's Theorem779

16.11 The Cycle Index785

16.12 The Pattern Inventory:Polya's Method of Enumeration789

16.13 Summary and Historical Review794

17 Finite Fields and Combinatorial Designs799

17.1 Polynomial Rings799

17.2 Irreducible Polynomials:Finite Fields806

17.3 Latin Squares815

17.4 Finite Geometries and Affine Planes820

17.5 Block Designs and Projective Planes825

17.6 Summary and Historical Review830

Appendix 1 Exponential and Logarithmic Functions1

Appendix 2 Matrices,Matrix Operations,and Determinants11

Appendix 3 Countable and Uncountable Sets23

Solutions1