Combinatorial Enumeration

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

1、LectureNotesinCombinatorialEnumerationAshortcourseTeroHarjuDepartmentofMathematicsUniversityofTurku,Finlandharju@utu.fi1998and2004Contents1.Introduction...............................12.Permutations..............................63.GeneratingFunctions.....................114.Bino

2、mials................................175.Inclusion-Exclusion.......................246.M¨obiusInversion.........................307.Cauchy-FrobeniusTheorem...............428.P´olya-RedfieldTheorem..................47Bibliography................................551IntroductionIncom

3、binatorialenumerationweareinterestedincountingobjectsaccordingtoagivenproblemsetting.Inmanyinstancesitisnotsufficienttocounttheindividualobjects(satisfyingcertainproperties),butoneisrequiredtocounttheequivalenceclassestheyfallinto,whensomekindofkinshiprelationisgiven.Twoobjectsare

4、thenconsideredtobesimilarorindistinguishable,iftheyareinthisrelation.Suchrestrictionsoftenrefertosymmetry.Thefollowingisatypicalenumerationproblemindiscretemathematics.Problem.Assumethatwehavebeadsofdifferentcolourssuchthattwobeadsofthesamecolourareindistinguishable.(Thisconditio

5、ngivesaclassificationofthebeadsintoequivalenceclasses.)Howmanynecklacesarethereofnbeadsofkdifferentcolours?Clearlythesolutiondependsonwhatisconsideredtobeanecklace,i.e.,whatconditionsarerequiredfortwonecklacestobethesame.(i)Thereareexactlyknwaystoputnbeadsinarow,sinceabeadofanycol

6、ourcanbeputinanyoneofthenpositions.Inthisinstancethereisnosymmetry;differentdesignsgivedifferentsolutions.(ii)Ifthebeadsareboundtogetherbyastring,weobtainanopennecklacethatcanbeturnedover–sothatthelastbeadcomesfirstandsoon.Thismeansthatsomeofthedesignsin(i)givethesameopennecklace.H

7、owmanyopennecklacesarethereofnbeadsofkcolours?(iii)Anopennecklacecanbeweldedbyitsendstoobtaina(closed)necklace.Suchanecklacecanberotatedandturnedover,andthereforesomeoftheopennecklacesgivethesameclosednecklace.Howmanynecklacesarethereofnbeadsofkcolours?11.INTRODUCTION2Asanexampl

8、e,letk=2sothatwehaveonlyblackandwhitebeads.Ther