Combinatorics Through Guided Discovery

《Combinatorics Through Guided Discovery》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、CombinatoricsThroughGuidedDiscovery1KennethP.BogartNovember6,20041DevelopmentofthisprojectwassupportedbyNationalScienceFoundationGrantNumberDUE-0087466iicKennethP.Bogart,2004ContentsPrefacevii1WhatisCombinatorics?11.1AboutTheseNotes........................21.2BasicCountingPrinciples..........

2、..........21.2.1Thesumandproductprinciples............51.2.2Functionsanddirectedgraphs.............91.2.3Thebijectionprinciple..................121.2.4Countingsubsetsofaset................121.2.5Pascal’sTriangle.....................131.2.6Thequotientprinciple..................161.3SomeApplica

3、tionsofBasicCountingPrinciples........221.3.1LatticepathsandCatalanNumbers..........221.3.2TheBinomialTheorem.................251.3.3Thepigeonholeprinciple.................271.3.4RamseyNumbers.....................291.4SupplementaryChapterProblems................302ApplicationsofInductionandRe

4、cursioninCombinatoricsandGraphTheory332.1SomeExamplesofMathematicalInduction..........332.1.1Mathematicalinduction.................332.1.2BinomialCoefficientsandtheBinomialTheorem...352.1.3Inductivedefinition....................362.1.4Provingthegeneralproductprinciple(Optional)...372.1.5DoubleIn

5、ductionandRamseyNumbers........382.1.6Abitofasymptoticcombinatorics...........392.2RecurrenceRelations.......................412.2.1Examplesofrecurrencerelations............41iiiivCONTENTS2.2.2ArithmeticSeries(optional)...............432.2.3Firstorderlinearrecurrences..............432.2.4Geom

6、etricSeries.....................442.3GraphsandTrees.........................452.3.1Undirectedgraphs....................452.3.2Walksandpathsingraphs...............462.3.3Countingvertices,edges,andpathsintrees......472.3.4Spanningtrees......................492.3.5Minimumcostspanningtrees.......

7、.......492.3.6Thedeletion/contractionrecurrenceforspanningtrees502.3.7Shortestpathsingraphs.................522.4SupplementaryProblems.....................543DistributionProblems573.1TheIdeaofaDistribution....................573.1.1Thetwenty-