资源描述：
《On the Foundations of Combinatorial Theory》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Z.Wahrseheinlichkeitstheorie2,340--368(1964)OntheFoundationsofCombinatorialTheoryI.TheoryofMiibiusFunctionsByGIAN-CAI~LOROT~Contents1.Introduction...............................3402.Preliminaries...............................3423.Theincidencealgebra...........................3444.Mai
2、nresults...............................3475.Applications................................3496.TheEulercharacteristic..........................3527.Geometriclattices.............................3568.Representations.............................3609.Application:thecoloringofgraphs........
3、.............36110.Application:flowsinnetworks.......................3641.IntroductionOneofthemostusefulprinciplesofenumerationindiscreteprobabilityandcombinatorialtheoryisthecelebratedprincipleo/inclusion-exclusion(cf.F~LL]~R*,FR~C~IET,RIORDA~,RYS~).Whenskillfullyapplied,thisprincipl
4、ehasyieldedthesolutiontomanyacombinatorialproblem.ItsmathematicalfoundationswerethoroughlyinvestigatednotlongagoinamonographbyF~CH~T,anditmightatfirstappearthat,aftersuchexhaustivework,littleelsecouldbesaidonthesubject.Onefrequentlynotices,however,awidegapbetweenthebarestatementofthep
5、rincipleandtheskillrequiredinrecognizingthatitappliestoaparticularcombinatorialproblem.Ithasoftentakenthecombinedeffortsofmanyacombinatorialanalystoverlongperiodstorecognizeaninclusion-exclusionpattern.Forexample,forthem4nageproblemittookfifty-fiveyears,sinceCAYL~'sattempts,beforeJACQ
6、UESTOUCHA~Din1934couldrecognizeapattern,andthencereadilyobtainthesolutionasanexplicitbinomialformula.Thesituationbecomesbewilderinginproblemsrequiringanenumerationofanyofthenumerouscollectionsofcombinatorialobjectswhicharenowadayscomingtothefore.Thecountingoftrees,graphs,partiallyorde
7、redsets,complexes,finitesetsonwhichgroupsact,nottomentionmoredifficultproblemsrelatingtopermu-tationswithrestrictedposition,suchasLatinsquaresandthecoloringofmaps,seemtoliebeyondpresent-daymethodsofenumeration.ThelackofasystematicThisworkwasbegunundercontract5TSF-GP-149,continuedunder
8、contr
