离散数学暨组合数学：英文版

Prefacexi

1TruthTables,Logic,andProofs

1.1.StatementsandConnectives1

1.2.ConditionalStatements9

1.3.EquivalentStatements13

1.4.AxiomaticSystems:ArgumentsandProofs20

1.5.CompletenessinPropositionalLogic30

1.6.KarnaughMaps3s

1.7.CircuitDiagrams41

2SetTheory51

2.1.IntroductiontoSets51

2.2.SetOperationss4

2.3.VennDiagrams60

2.4.BooleanAlgebras67

2.5.Relations72

2.6.PartiallyOrderedSets84

2.7.EquivalenceRelationsss

3Logic,Integers,andProofs94

3.1.PredicateCalculus94

3.2.BasicConceptsofProofsandtheStructureofIntegers104

3.3.MathematicalInduction109

3.4.Divisibility119

3.5.PrimeIntegers124

3.6.CongruenceRelations129

4Functionsand.Matrices136

4.1.Functions136

4.2.SpecialFunctions141

4.3.Matrices147

4.4.Cardinality158

4.5.CardinalsContinued160

5AlgorithmsantiRecursion16s

5.1.The"for"ProcedureandAlgorithmsforMatrices165

5.2.RecursiveFunctionsandAlgorithms169

5.3.ComplexityofAlgorithmsis2

5.4.SortingAlgorithmslSV

5.5.PrefixandSuffixNotation195

5.6.BinaryandHexadecimalNumbers200

5.7.SignedNumbers212

5.8.MatricesContinued217

6Graphs,DirectedGraphs,andTrecs224

6.1.Graphs22,1

6.2.DirectedGraphs231

6.3.Trees238

6.4.InstantInsanity245

6.5.EulerPathsandCycles247

6.6.IncidenceandAdjacencyMatrices254

6.7.HypercubesandGrayCode265

7NumberTheory272

7.1.SieveofEratosthenes272

7.2.Fermat'sFactorizationMethod273

7.3.TheDivisionandEuclideanAlgorithms2us

7.4.ContinuedFractions279

7.5.Convergents284

8CountingantiProbability290

8.1.BasicCountingPrinciples290

8.2.Inclusion-ExclusionIntroduced297

8.3.PermutationsandCombinations304

8.4.GeneratingPermutationsandCombinations316

8.5.ProbabilityIntroduced32o

8.6.GeneralizedPermutationsandCombinations327

8.7.PermutationsandCombinationswithRepetition332

8.8.PigeonholePrinciple337

8.9.ProbabilityRevisitedM2

8.10.Bayes'Theorem357

8.11.MarkovChains359

9AlgebraicStructuressss

9.1.PartiallyOrderedSetsRevisited365

9.2.SemigroupsandSemilattices369

9.3.Lattices374

9.4.Groups38o

9.5.GroupsandHomomorphisms386

10NumberTheoryRevisited393

10.1.IntegralSolutionsofLinearEquations393

10.2.SolutionsofCongruenceEquations395

10.3.ChineseRemainderTheorem399

10.4.PropertiesoftheFunction405

10.5.OrderofanInteger410

11RecursionRevisited418

11.1.HomogeneousLinearRecurrenceRelations418

11.2.NonhomogeneousLinearRecurrenceRelations430

11.3.FiniteDifferences44o

11.4.FactorialPolynomials444

11.5.SumsofDifferences45s

12CountingContinued462

12.1.OccupancyProblems462

12.2.CatalanNumbers468

12.3.GeneralInclusion-ExclusionandDerangements474

12.4.RookPolynomialsandForbiddenPositions480

13GeneratingFunctions494

13.t.DefininingtheGeneratingFunction(optional)494

13.2.GeneratingFunctionsandRecurrenceRelations496

13.3.GeneratingFunctionsandCounting508

13.4.Partitionssis

13.5.ExponentialGeneratingFunctions521

14GraphsRevisiteds2s

14.1.AlgebraicPropertiesofGraphs528

14.2.PlanarGraphs551

14.3.ColoringGraphs557

14.4.HamiltonianPathsandCycles569

14.5.WeightedGraphsandShortestPathAlgorithms578

15Trees590

15.1.PropertiesofTrees590

15.2.BinarySearchTrees597

15.3.WeightedTrees6o2

15.4.TraversingBinaryTrees613

15.5.SpanningTrees62O

15.6.MinimalSpanningTrees642

16Networks650

16.1.NetworksandFlows650

16.2.Matching664

16.3.PetriNets672

17TheoryofComputation681

17.1.RegularLanguages681

17.2.Automata

17.3.Grammars696

18TheoryofCodes70s

18.1.Introduction708

18.2.GeneratorMatrices712

18.3.HammingCodes721

19EnumerationofColors72s

19.1.Burnside'sTheorem728

19.2.Polya'sTheorem733

20Rings,IntegralDomains,andFields740

20.1.RingsandIntegralDomains740

20.2.IntegralDomains749

20.3.Polynomials752

20.4.AlgebraandPolynomials759

21GroupandSemigroupCharacters769

21.1.ComplexNumbers769

21.2.GroupCharacters770

21.3.SemigroupCharacters775

22ApplicationsofNumberTheory780

22.1.Application:PatternMatching780

22.2.Application:HashingFunctions787

22.3.Application'Cryptography794

Bibliography801

HintsandSolutionstoSelectedExercisesA-1

IndexI-1