经管营销哈工大ftp资料Chap14课件

Chapter14

Polyacounting

1Chapter14

Polyacounting1SummaryPermutationandsymmetrygroupsBurnsidetheoremPolyacountingformulaAssignments2SummaryPermutationandsymmetrColoringaregulartetrahedronSupposetocolorthefourcornersofaregulartetrahedronwithtwocolors,redandblue,howmanydifferentcoloringsarethere?Casea:thetetrahedronisfixedinspace,theneachcornerisdistinguishedfromtheothersbyitsposition,anditmatterswhichcoloreachcornergets.Thusall16colorsaredifferent.3ColoringaregulartetrahedronCaseb:thetetrahedronareallowedtomovearound.Inotherwords,thecornersareindistinguishable.Theonlywaytwocoloringscanbedistinguishedfromoneanotherisbythenumberofcornersofeachcolor.Thustherearetotal5differentcolorings.4Caseb:thetetrahedronarealColoringasquareSupposewecolorthe4cornersofasquarewiththecolorsredandblue.Howmanydifferentcoloringsarethere?5ColoringasquareSupposewecEquivalentandinequivalentcoloringsForboththetetrahedronandsquare,ifallowedtofreelymovearound,the16waystocoloritscornersarepartitionedintopartsinsuchawaythattwocoloringsinthesamepartareregardedasthesame(thecoloringsareequivalent),andtwocoloringsindifferentpartsareregardedasdifferent(thecoloringsareinequivalent).Thenumberofinequivalentcoloringsisthusthenumberofdifferentparts.6EquivalentandinequivalentcoPermutationandsymmetrygroups7PermutationandsymmetrygroupPermutationandfunctionLetXbeafiniteset.Withoutlossofgenerality,wetakeXtobetheset{1,2,3,…,n}.Eachpermutationi1,i2,i3,…,inofXcanbeviewedasaone-to-onefunctionfromXtoitselfdefinedbyf:X→X,wheref(1)=i1,f(2)=i2,….,f(n)=in.Apermutationisdenotedbya2-by-narrayasfollows:8PermutationandfunctionLetXExampleThe3!=6permutationsof{1,2,3}regardedasfunctionsare9ExampleThe3!=6permutationsCompositionofpermutationsLetaretwopermutationsof{1,2,…,n}.Thentheircomposition,intheorderffollowedbyg,isthepermutationwhere(g。f)(k)=g(f(k))=jik.10CompositionofpermutationsLetBinaryoperationWedenotethesetofalln!permutationsof{1,2,…,n}bySn.CompositionoffunctionsdefinesabinaryoperationonSn:iffandgareinSn,theng。fisalsoinSn.11BinaryoperationWedenotetheExampleLetfandgbethepermutationsinS4definedbyThen,(g。f)(1)=3,(g。f)(2)=4,(g。f)(3)=1,(g。f)(4)=2,andthus12ExampleLetfandgbetheperLawsoncompositionoperationAssociativelaw:(f。g)。h=f。(g。h))Commutativelaw:f。g≠g。fIdentitypermutation:l(k)=kforallk=1,2,…,n;Inversef-1:f-1(k)=sprovidedf(s)=k.f。f-1=f-1

。f=l.Compositionwithitself:f1=f,f2=f。f,…,fk=f。f。f。…。f(kf’s)13LawsoncompositionoperationAGettinginversefromthearrayStep1:interchangerows1and2Step2:rearrangecolumnssothattheintegers1,2,…,ninthefirstrowoccurinthenaturalorderDefinef0=l.Theinverseoftheidentitypermutationisitself:l-1=l.14GettinginversefromthearrayExample

ConsiderthepermutationinS6givenbyTheninterchangerows1and2,wegetRearrangingcolumnsweget15ExampleConsiderthepermutatPermutationgroupApermutationgroup,isdefinedtobeanon-emptysubsetGofpermutationsinSn,satisfyingthefollowingthreeproperties:(closureundercomposition)ForallpermutationsfandginG,f。gisalsoinG.(identity)TheidentitypermutationlofSnbelongstoG.(closureunderinverses)

ForeachpermutationfinG,theinversef-1isalsoinG.16PermutationgroupApermutationSymmetricgroupThesetSnofallpermutationsofX={1,2,…,n}isapermutationgroup,calledthesemmetricgroupofordern.ThesetG={l}consistingonlyoftheidentitypermutationisapermutationgroup.17SymmetricgroupThesetSnofaCancellationlawEverypermutationgroupsatisfiesthecancellationlawThisisbecausewemayapplyf-1tobothsidesoftheequationand,usingtheassociationlaw.18CancellationlawEverypermutatExamplesletnbeapositiveintegerandletpndenotethepermutationof{1,2,…,n}definedbythuspn(i)=i+1fori=1,2,…,n-1andpn(n)=1.thinkoftheintegersfrom1tonasevenlyspacedaroundacircleoronthecornersofaregularn-gon,asshown,forn=8,inthefigure.19ExamplesletnbeapositiveiIndeedwemayconsiderpnastherotationofthecirclebyanangleof360/ndegree.Thepermutationpn2isthentherotationby2×(360/n)degree,andmoregenerally,foreachnon-nagativeintegerk,pnkistherotationbyk×(360/n)degree.1234567820IndeedwemayconsiderpnastIfrequalskmodn,thenpnr=pnk.Thusthereareonlyndistinctpowersofpn,namely,pn0=l,pn,pn2,…,pnn-1.Alsopn-1=pnn-1,andmoregenerally,

(pnk)-1=pnn-k

fork=0,1,…,n-1.Wethusconcludethat

Cn={pn0=l,pn,pn2,…pnn-1}isapermutationgroup.Itisanexampleofacyclicgroupofordern.21Ifrequalskmodn,thenpnrSymmetryLetQbeageometricalfigure.AsymmetryofQisa(geometric)motionthatbringsthefigureQontoitself.Thegeometricfigureslikeasquare,atetrahedron,andacubearecomposedofcorners(orvertices)andedges,andinthecaseofthree-dimensionalfigure,offaces(orsides).Asaresult,eachsymmetryactsasapermutationonthecorners,ontheedges,andinthecaseofthreedimensionalfigures,onthefaces.22SymmetryLetQbeageometricaSymmetrygroupsWeconcludethatthesymmetriesofQactasapermutationgroupGConitscorners(calledcorner-symmetrygroup),apermutationgroupGEonitsedges(callededge-symmetrygroup),andinthecaseQisthreedimensional,apermutationgroupGFonitsfaces(calledface-symmetrygroup).23SymmetrygroupsWeconcludethaExample

ConsiderthefollowingsquareQwithitscornerslabeled1,2,3,4andedgeslabeleda,b,candd.Thereare8symmetriesofQandtheyareoftwotypes.Therearethe4rotationsaboutthecornerofthesquarethroughtheanglesof0,90,180,and270degrees.1243abcdThese4symmetriesconstitutetheplanersymmetriesofQ,thesymmetrieswherethemotiontakesplaceintheplanecontainingQ.Theplanersymmetriesbythemselvesformagroup.24ExampleConsiderthefollowinTheothersymmetriesarethefourreflectionsaboutthelinesjoiningoppositecornersandthelinesjoiningthemidpointsofoppositesides.Forthesesymmetriesthemotiontakesplaceinspacesinceto“flip”thesquareoneneedstogooutsideoftheplanecontainingit.Therotationsactingonthecornersgivethefourpermutations1243abcd25TheothersymmetriesarethefThereflectionsactingonthecornersgivethefourpermutationsThusthecorner-symmetrygroupofasquareisGC={p40=l,p4,p42,p43,r1,r2,r3,r4}.1243abcd26ThereflectionsactingontheConsidertheedgesofQtobelabeleda,b,canddinthefigure.Theedge-symmetrygroupGEisobtainedfromthecorner-symmetrygroupGCbyreplacing1,witha,2withb,3withcand4withd.Thus,forinstance,doingthisreplacementinr2,wegetandthisisthepermutationoftheedgesthatresultswhenthesquareisreflectedaboutthemidpointsofthelinesbandd.1243abcd27ConsidertheedgesofQtobeDihedralgroupInasimilarwaywecanobtainthesymmetrygroupofaregularn-gonforanyn≥3.Besidesthenrotationspn0=l,pn,pn2,…,pnn-1,wehavenreflectionsr1,r2,…,rn.Ifniseven,thentherearen/2reflectionsaboutoppositecornersandn/2reflectionsaboutthelinesjoiningthemidpointsofoppositesides.Ifnisodd,thenthereflectionsarethenreflectionsaboutthelinesjoiningacornertothesideoppositeit.TheresultinggroupGC={pn0=l,pn,pn2,…,pnn-1,r1,r2,…,rn}of2npermutationsof{1,2,…,n}isaninstanceofadihedralgroupoforder2n.28DihedralgroupInasimilarwayExample

Considertheregularpentagonwithitsverticeslabeled1,2,3,4and5.ItscornersymmetrygroupD5contains5rotations.The5rotationsare1234529ExampleConsidertheregularpLetridenotethereflectionaboutthelinejoiningcorneritothesideoppositeit(i=1,2,3,4,5).Thenwehave1234530LetridenotethereflectionaColoring

SupposewehaveagroupGofpermutationsofasetXwhereX={1,2,…,n}.AcoloringofXisanassignmentofacolortoeachelementofX.LetCbeacollectionofcoloringsofX.31ColoringSupposewehaveagroEquivalentcoloringLetGbeagroupofpermutationsactingonasetX.LetCbeacollectionofcoloringsofXsuchthatforallfinGandallcinC,thecoloringf*cofXisalsoinC.ThusGactsonCinthesensethatittakescoloringsinCtocoloringsinC.Letc1andc2betwocoloringsinC.c1isequivalent(undertheactionofG)toc2providedthereisapermutationfinGsuchthatf*c1=c2.32EquivalentcoloringLetGbeaExample

ConsiderthepreviousexamplewhereGC={p40=l,p4,p42,p43,r1,r2,r3,r4}.Letc={R,B,B,R)b1243abcdp4*c43c12abdl*c=cb1243acdp42*c1243abcdp43*cb1243acdr1*c1243acdr2*c4c312adr3*c4123acdr4*c33ExampleConsiderthepreviousBurnside’stheorem

34Burnside’stheorem34StabilizerLetG(c)={f:finG,f*c=c},thatisG(c)isthesetofallpermutationsthatfixthecoloringc.wecallG(c)thestabilizerofc.E.g.,inthepreviousexample,G(c)={l,r4}isastabilizerofcoloringc={R,B,B,R}.WedenoteC(f)={c:cinC,f*c=c}.35StabilizerLetG(c)={f:finTheorem14.2.1Foreachcoloringc,thestabilizerG(c)ofcisapermutationgroup.Moreover,foranypermutationsfandginG,g*c=f*cifandonlyiff-1。gisinG(c).36Theorem14.2.1ForeachcolorinCorollary14.2.2LetcbeacoloringinC.thenumber

|{f*c:finG}|ofcoloringsthatareequivalenttocequalsthenumber|G|/|G(c)|obtainedbydividingthenumberofpermutationsinGbythenumberofpermutationsinthestabilizerofc.37Corollary14.2.2LetcbeacolBurnside’stheoremLetGbeagroupofpermutationsofXandletCbeasetofcoloringsofXsuchthatf*cisinCforallfinGandallcinG.ThenthenumberN(G,C)ofinequivalentcoloringsinCisgivenbyInwords,thenumberofinequivalentcoloringsinCequalstheaverageofthenumberofcoloringsfixedbythepermutationsinG.38Burnside’stheoremLetGbeagExample1

(countingcircularpermutations).Howmanywaysaretheretoarrangendistinctobjectsinacircle?Hints:theansweristhenumberofwaystocolorthecornersofaregularn-gonQwithndifferentcolorswhichareinequivalentwithrespecttothegroupofrotationsofQ.39Example1(countingcircularpLetCconsistofalln!waystocolorthencornersofQinwhicheachofthencolorsoccursonce.ThenthecyclicgroupCn={pn0=l,pn,pn2,…,pnn-1}actsonC,andthenumberofcircularpermutationsequalsthenumberofinequivalentcoloringsinC.TheidentitypermutationlinCn

fixesalln!coloringsinC.everyotherpermutationinCdoesnotfixanycoloringinCsinceinthecoloringsofCeverycornerhasadifferentcolor.Hence,byBurnside’stheorem,N(Cn,C)=1/n(n!+0+…+0)=(n-1)!.40LetCconsistofalln!waystExample2(countingnecklaces).Howmanywaysaretheretoarrangen≥3differentlycoloredbeadsinanecklace?Hints:itisalmostthesameaspreviousexampleexceptthatnecklacecanbeflippedover.ThegroupGofpermutationsnowhastobetakentobetheentirevertex-symmetrygroupofaregularn-gon.ThusinthiscaseGisthedihedralgroupDnoforder2n.Theonlypermutationthatcanfixacoloringistheidentityanditfixesalln!colorings.Hence,N(Dn,C)=1/2n(n!+0+…+0)=(n-1)!/2.41Example2(countingnecklaces).Example3Howmanyinequivalentwaysaretheretocolorthecornersofaregular5-gonwiththecolorsredandblue?Hints:Thegroupofsymmetriesofaregular5-gonisthedihedralgroupD5={p50=l,p5,p52,p53,p54,r1,r2,r3,r4,r5}(seetheexamplein30).LetCbethesetofall25=32coloringsofthecornersofaregular5-gon.WecomputethenumberofcoloringsleftfixedbyeachpermutationinD5andthenapplyBurnside’stheorem.42Example3HowmanyinequivalentTheidentitylfixesallcolorings.Eachoftheother4rotationsfixesonlytwocolorings,namely,thecoloringinwhichallcornersarered,andthecoloringinwhichallcornersareblue.Thus,|C(p50)|=32and|C(p5i)|=2wherei=1,2,3,4.Nowconsideranyofthereflections,sayr1.Inorderthatacoloringbefixedbyr1,corners2and5musthavethesamecolorandcorners3and4musthavethesamecolor.Hence,thecoloringsfixedbyr1areobtainedbypickingacolorforcorner1(twochoice),pickingacolorfor2and5(twochoice)andpickingacolorforcorners3and4(againtwochoices).Hencethenumberofcoloringsfixedbyr1equals8.Asimilarcalculationholdsforeachreflectionandhence|C(rj)|=8foreachj=1,2,3,4,5.Therefore,thenumberofinequivalentcoloringsisN(D5,C)=1/10(32+2×4+8×5)=8.43TheidentitylfixesallcolorExample4Howmanyinequivalentwaysaretheretocolorthecornersofaregular5-gonwiththecolorsred,blue,andgreen?Hints:refertoexample3.nowthesetCofallcoloringsnumber35=243.Theidentityfixesall243colorings.Everyotherrotationfixesonly3colorings.Eachreflectionfixes3×3×3=27colorings.HenceN(D5,C)=1/10(243+3×4+27×5)=39.44Example4HowmanyinequivalentExercise

Howmanyinequivalentwaysaretheretocolorthecornersofaregular5-gonwithpcolors?Answer:1/10(p5+4×p+5×p3)45ExerciseHowmanyinequivalentExample5LetS={∞{r},∞{b},∞{g},∞{y}}bemultisetoffourdistinctobjectsr,b,g,y,eachwithaninfiniterepetitionnumber.Howmanyn-permutationsofSarethereifwedonotdistinguishbetweenapermutationreadfromlefttorightandthepermutationreadfromrighttoleft?Thusforinstance,r,g,g,g,b,y,yisregardedasequivalenttoy,y,b,g,g,g,r.46Example5LetS={∞{r},∞{b},Solution

Theansweristhenumberofinequivalentwaystocolortheintegersfrom1tonwiththefourcolorsred,blue,greenandyellowundertheactionofthegroupofpermutationsG={l,r},where47SolutionTheansweristhenumNotethatGisagroup.Why?LetCbethesetofall4nwaystocolortheintegersfrom1tonwiththegivenfourcolors.ThenlfixesallcoloringsinC.Thenumberofcoloringsfixedbyrdependsonwhethernisevenorodd.First,supposeniseven.Thenacoloringisfixedbyriff1andnhavethesamecolor,2andn-1havethesamecolor,….,n/2andn/2+1havethesamecolor.Hencerfixes4n/2coloringsinC.Nowsupposethatnisodd.Thenacoloringisfixedbyriff1andnhavethesamecolor,2andn-1havethesamecolor,…,(n-1)/2and(n+3)/2havethesamecolor.

Hencethenumberofcoloringsfixedbyris4(n-1)/2×4=4(n+1)/2.Thus48NotethatGisagroup.Why?LExercise

Ifinsteadoffourcolor,wehavepcolors,whatisthenumberofinequivalentcolorings?Answer:49ExerciseIfinsteadoffourcoPolya’scountingformula50Polya’scountingformula50Factorization

Letbea

permutationoftheset{1,2,3,4,5,6,7,8}.Thenfhasafactorizationasfollows:51FactorizationLetCyclefactorizationLetfbeanypermutationofthesetX.Thenwithrespecttotheoperationofcompositionfhasafactorization

f=[i1i2…ip]。[j1j2..jq]。…。[l1l2…lr]intocycleswhereeachintegerinXoccursinexactlyoneofthecycles.Wecallitcyclefactorizationoff.Thecyclefactorizationoffisuniqueapartfromtheorderinwhichthecyclesappear,andthisorderisarbitrary.EveryelementofXoccursexactlyonceinthecyclefactorization.52CyclefactorizationLetfbeanExample1

DeterminethecyclefactorizationofeachpermutationinthedihedralgroupD4oforder8(thecornersymmetrygroupofasquare).D4Cyclefactorizationp40[1]。[2]。[3]。[4]p41[1234]p42[13]。[24]p43[1432]r1[1]。[24]。[3]r2[13]。[2]。[4]r3[12]。[34]r4[14]。[23]53Example1DeterminethecycleExample2DeterminethecyclefactorizationofeachpermutationinthedihedralgroupD5oforder10(thecorner-symmetrygroupofaregular5-gon).D5Cyclefactorizationp50[1]。[2]。[3]。[4]。[5]P51[12345]p52[13524]p53[14253]p54[15432]r1[1]。[25]。[34]r2[13]。[2]。[45]r3[15]。[3]。[24]r4[12]。[35]。[4]r5[14]。[23]。[5]54Example2DeterminethecyclefExample3LetfbethepermutationofX={1,2,3,4,5,6,7,8,9}.Thecyclefactorizationoffisf=[1473]。[29]。[56]。[8].SupposethatwecolortheelementsofXwiththecolorsred,white,andblue,andletCbethesetofallsuchcolorings.Howmany|C(f)|coloringsinCareleftfixedbyf?Hints:foreachcycle,alltheelementsinthesamecyclewillbecoloredwiththesamecolor.Hence,thetotalcolorings|C(f)|=34=81.55Example3Letfbethepermutat#(f)#(f)isthenumberofcyclesinthecyclefactorizationofapermutationf.E.g.,forf=[1473]。[29]。[56]。[8],#(f)=4.Itisindependentofthesizesofthecycles.56#(f)#(f)isthenumberofcyclTheorem14.3.1LetfbeapermutationofasetX.SupposewehavekcolorsavailablewithwhichtocolortheelementsofX.LetCbethesetofallcoloringsofX.Thenthenumber|C(f)|ofcoloringsofCthatarefixedbyfequalsk#(f).57Theorem14.3.1LetfbeapermuExampleHowmanyinequivalentwaysaretheretocolorthecornersofasquarewiththecolorsred,white,andblue?LetCbethesetofall34=81coloringsofthecornersofasquarewithcolorsred,whiteandblue.Thecorner-symmetrygroupofasquareisthedihedralgroupD4,thecyclefactorizationofwhoseelementswascomputedinExample1.58ExampleHowmanyinequivalentD4Cyclefactorizationp40[1]。[2]。[3]。[4]p41[1234]p42[13]。[24]p43[1432]r1[1]。[24]。[3]r2[13]。[2]。[4]r3[12]。[34]r4[14]。[23]#(f)|C(f)|434=81131=3232=9131=3333=27333=27232=9232=9Hence,theanswerisN(D4,C)=(81+3+9+3+27+27+9+9)/8=2159D4Cyclefactorizationp40[1]。[2TypeofapermutationLetfbeapermutationofXwhereXhasnelements.Supposethatthecyclefactorizationoffhase11-cycles,e22-cycles,…andenn-cycles.Then1e1+2e2+…+nen=n.wecallthen-tuple(e1,e2,…,en)thetypeofthepermutationfandwritetype(f)=(e1,e2,…,en).#(f)=(e1+e2+…+en)Differentpermutationmayhasthesametype.Why?60TypeofapermutationLetfbeMonomialofapermutationWeintroducenindeterminatesz1,z2,…,znwherezkistocorrespondtoak-cycle(k=1,2,…,n).Toeachpermutationfwithtype(f)=(e1,e2,…,en)weassociatethemonomialoff,mon(f)=z1e1z2e2…znen.61MonomialofapermutationWeinGeneratingfunctionLetGbeagroupofpermutationsofX.ThegeneratingfunctionforthepermutationsinGaccordingtotypeis

Ifwecombineterms,thecoefficientofz1e1z2e2…znenequalsthenumberofpermutationsinGoftype(e1,e2,…,en).62GeneratingfunctionLetGbeaCycleindexThecycleindexofGisthegeneratingfunctiondividedbythenumber|G|ofpermutationsinG.Thatis63CycleindexThecycleindexofExample

DeterminethecycleindexofthedihedralgroupD4.PD4(z1,z2,z3,z4)=(z14+2z4+3z22+2z12z2)/8D4Cyclefactorizationp40[1]。[2]。[3]。[4]p41[1234]p42[13]。[24]p43[1432]r1[1]。[24]。[3]r2[13]。[2]。[4]r3[12]。[34]r4[14]。[23]typemonomial(4,0,0,0)z14(0,0,0,1)z4(0,2,0,0)z22(0,0,0,1)z4(2,1,0,0)z12z2(2,1,0,0)z12z2(0,2,0,0)z22(0,2,0,0)z2264ExampleDeterminethecycleinExerciseDeterminethecycleindexofthedihedralgroupD5.AnswerPD5(z1,z2,z3,z4,z5)=(z15+4z5+5z1z22)/10.65ExerciseDeterminethecycleiTheorem14.3.2LetXbeasetofnelementsandsupposewehaveasetofkcolorsavailablewithwhichtocolortheelementsofX.LetCbethesetofallkncoloringsofX.LetGbeagroupofpermutationsofX.Thenthenumberofinequivalentcoloringsisthenumber|N(G,C)|=PG(k,k,…,k)obtainedbysubstitutingzi=k,(i=1,2,…,n)inthecycleindexofG.66Theorem14.3.2LetXbeasetoExample

Wearegivenasetofkcolors.Whatisthenumberofinequivalentwaystocolorthecornersofasquare?ThecycleindexofthedihedralgroupD4hasalreadybeendeterminedtobePD4(z1,z2,z3,z4)=(z14+2z4+3z22+2z12z2)/8.HencetheanswerisPD4(k,k,k,k)=(k4+2k+3k2+2k3)/8.Ifk=6,thenthenumberofinequivalentcoloringsis

PD4(6,6,6,6)=(64+2×6+3×62+2×63)/8=231.67ExampleWearegivenasetofExampleHowmanyinequivalentcoloringsarethereofthecornersofaregular5-goninwhichthreecornersarecoloredredandtwoarecoloredblue?Hints:(a)|C|=10;(b)Forthecyclefactorizationofeachpermutation,computerthenumberoffixedcolorings;(c)ApplyBurnsidetheorem.68ExampleHowmanyinequivalentTheorem14.3.3LetXbethesetofelementsandletGbeagroupofpermutationsofX.Let{u1,u2,…,uk}beasetofkcolorsandletCbeanysetofcoloringsofXwiththepropertythatGactsasapermutationgrouponC.ThenthegeneratingfunctionforthenumberofinequivalentcoloringsofCaccordingtothenumberofcolorsofeachkindistheexpressionPG(u1+…+uk,u12+…+uk2,….,u1n+…+ukn).69Theorem14.3.3LetXbethesetTheorem14.3.3(cont’d)PG(u1+…+uk,u12+…+uk2,….,u1n+…+ukn)isobtainedfromthecycleindexPG(z1,z2,…zn)bymakingthesubstitutionszj=u1j+…ukj(j=1,2,…,n).Thecoefficientofu1p1u2p1…ukpkequalsthenumberofinequivalentcoloringsinCwithp1elementsofXcoloredu1,p2elementscoloredu2,…,pkelementscoloreduk.70Theorem14.3.3(cont’d)PG(u1+…Example1Determinethegeneratingfunctionforinequivalentcoloringsofthecornersofasquarewith2colorsandalsothosewith3colors.PD4(z1,z2,z3,z4)=(z14+2z4+3z22+2z12z2)/8.Letthetwocolorsberandb.ThenthegeneratingfunctionisPD4(r+b,r2+b2,r3+b3,r4+b4)=1/8[(r+b)4+2(r4+b4)+3(r2+b2)2+2(r+b)2(r2+b2)]=r4+r3b+2r2b2+rb3+b4.(howtocolor?)Continuethecasefor3colorsbyyourself!!!!!71Example1DeterminethegeneratExample2Determinethegeneratingfunctionforinequivalentcoloringsofthecornersofaregular5-gonwith2colorsandalsothosewith3colors.ThecycleindexofD5isPD5(z1,z2,z3,z4,z5)=(z15+4z5+5z1z22)/10.ThenthegeneratingfunctionforinequivalentcoloringsisPD5(r+b,r2+b2,…,r5+b5)=r5+r4b+2r3b2+2rrb3+rb4+b5.thetotalnumberofinequivalentcoloringsequals1+1+2+2+1+1=8.Continueforthecasewith3colorsbyyourself.72Example2DeterminethegeneratExample3Determinethesymmetrygroupofacubeandthenumberofinequivalentwaystocolorthecornersandfacesofacubewithaspecifiednumberofcolors.12345678Thereare24symmetriesofacube,andtheyarerotationsoffourtypesdifferentkinds.73Example3DeterminethesymmetrStep1determinethesymmetries(1)theidentityrotationl(numberis1)(2)therotationsaboutthecentersofthethreepairsofoppositefacesby(a)90degrees(numberis3)(b)180degree(numberis3)(c)270degree(numberis3)(3)therotationsby180degreeaboutmidpointsofoppositeedges(numberis6)(4)therotationsaboutoppositecornersby(a)120degrees(numberis4)240degree(numberis4).74Step1determinethesymmetrieStep2computethetype123456781234567812345678(a)(0,0,0,2,0,0,0,0)(b)(0,4,0,0,0,0,0,0)(c)(0,0,0,2,0,0,0,0)(0,4,0,0,0,0,0,0)(2,0,2,0,0,0,0,0)(2,0,2,0,0,0,0,0)Computethefacetypebyyourself!!!!75Step2computethetype1234567Step3cycleindex

PGC(z1,z2,…z8)=1/24(z18+6z42+9z24+8z12z32).symmetrynumberCornertypeFacetype(1)1(8,0,0,0,0,0,0,0)(6,0,0,0,0,0)2(a)3(0,0,0,2,0,0,0,0)(2,0,0,1,0,0)2(b)3(0,4,0,0,0,0,0,0)(2,2,0,0,0,0)2(c)3(0,0,0,2,0,0,0,0)(2,0,0,1,0,036(0,4,0,0,0,0,0,0)(0,3,0,0,0,04(a)4(2,0,2,0,0,0,0,0)(0,0,2,0,0,04(b)4(2,0,2,0,0,0,0,0)(0,0,2,0,0,076Step3cycleindexPGC(z1,z2,Step4generatingfunctionSupposeweapplytwocolorsrandb.ThegeneratingfunctionforinequivalentcoloringsofthecornersofacubeisPGC(r+b,r2+b2,…,r8+b8)=r8+r7b

+

3r6b2+3r5b3+7r4b4+3r3b5+3r2b6+rb7+b8.Hencethetotalnumberofinequivalentcoloringsforthecornersis23.Computerthetotalnumberofinequivalentcoloringsforthefacesbyyourself!!!!77Step4generatingfunctionSuppAssignments1,6,8,11,18,23,26,29,35,37,38.78Assignments1,6,8,11,18,23Chapter14

Polyacounting

79Chapter14

Polyacounting1SummaryPermutationandsymmetrygroupsBurnsidetheoremPolyacountingformulaAssignments80SummaryPermutationandsymmetrColoringaregulartetrahedronSupposetocolorthefourcornersofar