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

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