组合数学试题2011年秋季学期期末考试试卷

2011年秋HITShenzhenGraduateSchoolExaminationCourse 组合数 Thefollowingformulaandresultsmaybeusefulforyouinthis

QuestionOne:Pleasegivetheanswersforthefollowing17questionswithoutDetermineanintegermnsuchthatifmnpointsarechosenwithinanequilateraltriangleofsidelength1,therearetwowhosedistanceapartisatmostଵ. mn=( ୬Considerthepermutationof{1,2,3,4,5,6,7,8}.Thepermutationwithaninversion ଶ୬ሺ୬ି ଶ1x

1(exex2ex1xx2

Amongthecombinationof{x7,x6,…,x1,x0},whatisthecombinationthat yfollow{x7,x5,x3,x2,x1,x0}byusingthebase2arithmeticgenerating 题内容写

n在Thenumberofwaystoplacennon-attacking,indistinguishablerooksonann-by-nboardwith边线positionsequalsnr1(n-1r2(n-21)krk(n-k)!+…+(-外视ForaspecifiedgridiinchessboardC,letCibeachessboardinducedfromCbydeletingtherowand为效无columnofgridi；letCebeinducedfromCbydeletinggridifromC.Then,效

Leth୬equalthenumberofdifferentwaysinwhichthesquaresofa1-by-nchessboardcanbecolored,usingthecolorsred,green,andblacksothatnotwosquaresthatarecoloredredareadjacent.Then,therecurrencerelationforh୬is( xR(Ci)+R(CAssumethatthesequenceh0,h1,h2,…,hn,…hasadifferencetablewhose0thdiagonalequals,c0,c1,c2,…,cp≠0,0,0,…Then,hn=c0C(n,0)+c1C(n,1)+c2C(n,2)+…+cpC(n,p).and

Determinethegeneratingfunctionforthenumbereଷ൅6eସൌି

ofnon-negativeintegralsolutionof

൅5eଶnhcn

cn

n 0

pp1

Leth୬equalthenumberofdifferentwaysinwhichthesquaresofa1‐by‐nchessboardcanbek

Letn≥2beaninteger.Ifthereexistn-1MOLSofordern,thenthereexistsaresolvableBIBD

usingthecolorsred,blue,white,andgreen,sothatthenumberofsquarescoloredrediseven,andparametersb=n2+n,v=n2,k=n,r=N(G,C)1 |C(f)||G|f

=

numberofsquarescoloredwhiteisodd.Thenh୬= Letthesequenceh൅,hଵ,hଶ，…h୬…bedefined h୬ൌି2nଶൌିn൅3, e

Then h୩=|G PG(z1,z2,,zn) z11z22zn,wheretype(f)=(e1,|G f

ି൅

12345

12345f= andg= 64215 35624Letc=(R,B,B,R,R,R)beacoloringof1,2,3,4,5,6withthecolorsRandB.StudentStudent StudentStudentሺ

PageNo.Suppose20indistinguishableballsareallocatedto5 ssothateveryonehasnolessthan3balls.Thenthenumberofwaysis( ).Iftheballsaredistinguishable,thenthenumberofwaysis( Determinethenumberofternarygroupschoosingfromtheset{1,2,…,20},wheretherearenotwoadjacentnumbersineachgroup.Inhowmanywayscan100studentsbeallocatedintoA,BandCclasses,whereclassAcan 30girls,classBcan modate32boys,classCcan modate40students(boysorgirls),andthe100studentshave40girlsand60boys.

Inhowmanywayscan5redrooksand3bluerookscanbeplacedon12×12boardsothatnotwocanattackoneanother,wherethefirstlineandthefirstcolumnshouldnotThereisapartywith4couples.Inhowmanywayscantheychoosetheirpartner,whereeachpairpartnersisnotCountthepermutationsiଵ,iଶ,iଷ,iସ,iହ,i൅ofሼ1,2,3,4,5,6ሽwhereiଶି1,4;iଷି2,3,5,iସି4,i൅ିApplythedeferredacceptancealgorithmtoobtainastablecompletemarriageforthe

Note:PleasegiveadetailedexplanationforthefollowingthreehasSDRs?Why?ofAwhichcanbechosensuchthattheyhavean

Whatisthelargestnumberof ܣ ܤ ܦ

Giveamax-matchingandamin-coverofthefollowinggraphbyapplyingthematchingalgorithmwithPageNo.QuestionThree:Letpbeaprimenumber.Determinethenumberofdifferentnecklacesthatcanbemadefrompbeadsofndifferentcolors.

QuestionFour:Supposethereare25varietiesofproductswhichneedtobetestedby30consumers