A-Walk-Through-Combinatorics---GBV英文精品课件

AWalkThroughCombinatoricsAnIntroductiontoEnumerationandGraphTheoryMiklosBonaDepartmentofMathematicsUniversityofFloridaUSAWorldScientificNewJersey•London•Singapore•HongKongContentsForewordviiPrefaceixAcknowledgementxiI.BasicMethodsChapter1SevenIsMoreThanSix.ThePigeon-HolePrinciple11.1TheBasicPigeon-HolePrinciple11.2TheGeneralizedPigeon-HolePrinciple3Exercises10SupplementaryExercises11SolutionstoExercises12Chapter2OneStepataTime.TheMethodofMathematicalInduction192.1WeakInduction192.2StrongInduction25Exercises.-26SupplementaryExercises28SolutionstoExercises29xiiixivContentsII.EnumerativeCombinatoricsChapter3ThereAreALotOfThem.Elemen-taryCountingProblems373.1Permutations373.2StringsoveraFiniteAlphabet403.3ChoiceProblems43Exercises47SupplementaryExercises51SolutionstoExercises52Chapter4NoMatterHowYouSliceIt.TheBi-nomialTheoremandRelatedIdentities654.1TheBinomialTheorem654.2TheMultinomialTheorem704.3WhentheExponentIsNotaPositiveInteger73Exercises75SupplementaryExercises.78SolutionstoExercises79Chapter5DivideandConquer.Partitions895.1Compositions895.2SetPartitions915.3IntegerPartitions94Exercises100SupplementaryExercises102SolutionstoExercises103Chapter6NotSoViciousCycles.CyclesinPermutations1096.1CyclesinPermutations1106.2PermutationswithRestrictedCycleStructure116Exercises120SupplementaryExercises123SolutionstoExercises123Chapter7YouShallNotOvercount.TheSieve1317.1EnumeratingtheElementsofIntersectingSets1317.2ApplicationsoftheSieveFormula134Exercises138ContentsxvSupplementaryExercises139SolutionstoExercises140Chapter8AFunctionIsWorthManyNumbers.GeneratingFunctions1458.1OrdinaryGeneratingFunctions1458.1.1RecursiveFormulaeandGeneratingFunctions1458.1.2ProductsofGeneratingFunctions1518.1.3CompositionsofGeneratingFunctions1568.2ExponentialGeneratingFunctions1608.2.1RecursiveFormulaeandExponentialGeneratingFunctions1608.2.2ProductsofExponentialGeneratingFunctions1628.2.3CompositionsofExponentialGeneratingFunctions...164Exercises168SupplementaryExercises169SolutionstoExercises171III.GraphTheoryChapter9DotsandLines.TheOriginsofGraphTheory1839.1TheNotionofGraphs.EulerianWalks1849.2HamiltonianCycles1889.3DirectedGraphs1909.4TheNotionofIsomorphisms193Exercises196SupplementaryExercises200SolutionstoExercises200Chapter10StayingConnected.Trees20710.1MinimallyConnectedGraphs20710.2Minimum-weightSpanningTrees21410.3GraphsandMatrices21810.3.1AdjacencyMatricesofGraphs21810.4TheNumberofSpanningTreesofaGraph221Exercises226SupplementaryExercises...229SolutionstoExercises230xviContentsChapter11FindingAGoodMatch.ColoringandMatching23911.1Introduction23911.2BipartiteGraphs24111.3MatchingsinBipartiteGraphs24611.4MoreThanTwoColors25211.5MatchingsinGraphsThatAreNotBipartite254Exercises258SupplementaryExercises259SolutionstoExercises260Chapter12DoNotCross.PlanarGraphs26512.1Euler'sTheoremforPlanarGraphs26512.2Polyhedra26812.3ColoringMaps275Exercises'.278SupplementaryExercises278SolutionstoExercises279IV.HorizonsChapter13DoesItClique?RamseyTheory28313.1RamseyTheoryforFiniteGraphs28313.2GeneralizationsoftheRamseyTheorem28913.3RamseyTheoryinGeometry292Exercises293SupplementaryExercises295SolutionstoExercises296Chapter14SoHardToAvoid.SubsequenceCon-ditionsonPermutations30114.1PatternAvoidance30114.2StackSortablePermutations313Exercises324SupplementaryExercises326SolutionstoExercises327ContentsxviiChapter15WhoKnowsWhatItLooksLike,ButItExists.TheProbabilisticMethod33915.1TheNotionofProbability33915.2NonconstructiveProofs34315.3IndependentEvents34515.3.1TheNotionofIndependenceandBayes'Theorem...34515.3.2MoreThanTwoEvents35015.4ExpectedValues35015.4.1LinearityofExpectation35215.4.2ExistenceProofsUsingExpectation35415.4.3ConditionalExpectation356Exercises358SupplementaryExercises361SolutionstoExercises362Chapter16AtLeastSomeOrder:PartialOrdersandLattices36916.1TheNotionofPartiallyOrderedSets36916.2TheMobiusFunctionofaPoset37416.3Lattices383Exercises,390SupplementaryExercises392SolutionstoExercises393Bibliography401Index403