离散及组合数学

PART 1 Fundamentals of Discrete Mathematics

1 Fundamental Principles of Counting

1.1 The Rules of Sum and Product

1.2 Permutations

1.3 Combinations: The BinomialTheorem

1.4 Combinations with Repetition

1.5 The Catalan Numbers （Optional）

1.6 Summary and HistoricalReview

2 Fundamentals of Logic

2.1 Basic Connectives and Truth Tables

2.2 LogicalEquivalence:The Laws ofLogic

2.3 Logicallmplication: Rules oflnference

2.4 The Use ofQuantifiers

2.5 Quantifiers, Definitions, and the Proofs of Theorems

2.6 Summary and HistoricalReview

3 SetTheory

3.1 Sets and Subsets

3.2 Set Operations and the Laws of Set Theory

3.3 Counting andVenn Diagrams

3.4 A First Word on Probability

3.5 TheAxioms ofProbability （Optional）

3.6 Conditional Probability: Independence （Optional）

3.7 Discrete Random Variables （Optional）

3.8 Summary and HistoricalReview

4 Properties of the Integers: Mathematicallnduction

4.1 The Well-Ordering Principle: Mathematicallnduction

4.2 RecursiveDefinions

4.3 The Division Algorithm: Prime Numbers

4.4 TheGreatestCommonDivisor:TheEuclideanAlgorithm

4.5 The FundamentalTheorem ofArithmetic

4.6 Summary and HistoricalReview

5 Relations and FunCtions

5.1 Cartesian Ptoducts and Relations

5.2 Functions: Plain and One-to-One

5.3 Onto Functions: Stirling Numbers ofthe Second Kind

5.4 SpecialFunctions

5.5 The Pigeonhole Principle

5.6 Function Composition andlnverse Functions

5.7 ComputationalComplexity

5.8 AnalysisofAlgorithms

5.9 Summary and HistoricalReview

6 Languages: Finite State Machines

6.1 Language:TheSetTheoryofStrings

6.2 Finite State Machines: A First Encounter

6.3 Firute State Machines: A Second Encounter

6.4 Summary and HistoricalReview

7 Relations:The Second Time Around

7.1 Relations Revisited: Properties ofRelations

7.2 Computer Recognition: Zero-One Matrices and Directed Graphs

7.3 artialOrders: Hasse Diagrams

7.4 Equivalence Relations and Partitions

7.5 Finite State Machines: The Minimization Process

7.6 Summary and HistoricaIReview

PART 2 Further Topics in Enumeration

8 The Prinaple of Inclusion and Exclusion

8.1 The Principle oflnclusion and Exclusion

8.2 Generalizations ofthe Principle

8.3 Derangements:NothingIsinltsRightPlace

8.4 RookPolynomials

8.5 Arrangements with Forbidden Positions

8.6 Summary and HistoricaIReview

……

PART 3 Graph Theory and Applications

PART 4 Modern Applied Algebra

Appendixl ExponentialandLogarithmicFunctions A-1

Appendix2 Matrices,MatrixOperations,andDeterminants A-11

Appendix 3 Countable and Uncountable Sets A-23

Solutions S-1

《国外信息科学与技术经典图书系列：离散及组合数学（第5版）（影印版）》内容主要由四部分组成：（1）基本离散结构，包括集合论与逻辑、函数与关系、语言与有限状态自动机；（2）组合数学，包括排列组合、容斥原理、生成函数、递推关系、鸽巢原理；（3）图论及其应用，包括图论基本知识、树、最优化与匹配；（4）现代应用代数，包括环论与模算术、布尔代数与交换函数、群、编码理论、波利亚计数方法、有限域与组合设计。
《国外信息科学与技术经典图书系列：离散及组合数学（第5版）（影印版）》可作为计算机、软件工程和电子类相关专业的本科生或研究生教材，也可供工程技术人员参考。