说明教案成果mth2 counting

CountingRemark(MultiplicationIftherearen1waysofngsomething,andn2waysofnganothermdifferentthings,andthefirstonecanbedoneinn1ways,thesecondinn2ways,etc.,thentherearen1·n2·····nmwaystodothemall.Moreformally,ifS1,S2,...,Smarefinitesets,|S1×S2×···×Sm|=|S1|·|S2|·...·|Sm|Tochooseoneelementfrom{A,B,C}andoneelementfrom{X,Y},istochooseoneelementfrom{AX,AY,BX,BY,CX,CY},orfrom{A,B,C}×{X,Y}.Thereare3·2=6waystodo CountingRemark(AdditionIfwehaven1waysofngsomethingandn2waysofnganotherthingandwecannotdobothatthesametime,thentherearen1+n2thefirstonecanbedoneinn1ways,thesecondinn2ways,etc.,andwecandoonlyoneofthesethings,thentherearen1+n2+···+nmwaystochooseoneoftheactions.|S1∪S2∪···∪Sm|=|S1|+|S2|+···+|Sm|Tochooseoneelementfrom{A,B,C}or{X,Y},istochooseoneelementfrom{A,B,C,X,Y}={A,B,C}∪{X,Y}.Thereare3+2=5waystodo CountingRemark(OtherCounting positionPrinciplesuggeststobreakthesetofpossible y,andthentoapplytheadditionprinciple.TheideaofCountingtheComplement(SubtractionPrinciple)saysthatinsteadofcountingtheobjectsofaclassthathaveaspecialproperty,onemaycountallobjectsinthatclassandthensubtractthenumberofthosewithoutthatproperty.ThePrincipleofInclusionandExclusionmaybeseenasa tionofthepreviousprinciples.Wewillstudythatlater.TocounttheelementsofasetA,wemayfirstprovethatthereTocounttheelementsofasetA,wemaycountanothercleverlythesecondcount,|B|appearsjustasamultipleof|A|,weonly PermutationsandCombinationsofDefinitionandLetr∈NandX={x1,x2,...,xn}beasetwithn<∞elementsofXoflengthr.Repetitionsareallowed.ofrpairwise ThereareP(n,r)=nPr:=n·(n−1)···(n−r+1)

manysuchr-permutations,if0≤r≤n.Otherwise,P(n,r)=0 ThereareC(n,r)=C=!n":= manysuchn

(n−r)!combinationsofrelements,if0≤r≤n.Otherwise,C(n,r)=0 PermutationsandAclubhas20members.Theofficesof ,vice 2differenectionscounting2: Election1

2equalelectionscounting1: PermutationsandCombinationsofDefinitionandLetr∈NandX={n1·x1,n2·x2,...,nk·xk}beamultisetn:=n1+n2+···+nk<∞manyelementsofkdistincttypesxi"(xj1,xj2,...,xjr)ofrelementsofX,inwhicheachtypxjmayberepeateduptonj"ThereareP(n;n1,n2,...,nk)

Ifnj≥rforj=1,2,...,k,thenther-permutationsofXarepreciselyther-tuplesovertheunderlyingset{x1,x2,...,xk}.Therearekr {m1·x1,m2·x2,...,mk·xk}⊆Xwithrmanyelements,r=m1+m2+···+mkand0≤mj≤njforj=1,2,...,kIfnj≥rforj=1,2,...,k,thenthereC(r+k−1,r)=!r+k−1"=!r+k−1" PermutationsandCombinationsasAnr-tupley=(y1,y2,...,yr)overasetX={x1,x2,...,xn}isbasicallyjustafunctiony:{1,2,...,r}−→X i−→y(i):=yiAnr-permutationy=(y1,y2,...,yr)ofasetX={x1,x2,...,xn}isbasicallyaninjectivefunctiony:{1,2,...,r}−→X i−→y(i):=yiApermutationy=(y1,y2,...,yn)ofann-elementX={n1·x1,n2·x2,...,nk·xk}isbasicallyay:{1,2,...,n}−→{x1,x2,...,xk} i−→y(i):=yi

|y−1(xj)|= forj=1,2,...,k DistinguishableObjectsand

n1

n2

n3123456y:{1,2,...,7}−→{A,B,1−→

2,3−→ |y(A)|=2 2−→3−→4−→5−→6−→7−→

5,6 |y(B)|=2= üûú üûú|y(C)|=3=3Boxn1

n2

n3 DistinguishableObjectsandn1=2n2 n3{ú,û,ú(C,A,A,C,B,B, 123456

Box

(A,C,A,C,B,B, 123456

Box

permutationsofthemultiset,whichwouldbeP(7;2,2,3)=!27Letn=n1+n2+···+nk.ThenumberofwaysinwhichnB1,B2,...,Bk,suchthatexactlyn1objectsgointoboxB1,n2gointoB2,etc.,isequaltoP(n;n1,n2,...,nk)= IndistinguishableObjectsand

n1

n2

n3 {ú,û,úboxesA,B,C.Thereisanaturalbijectionbetweenthesetofall••••{A, {B,

Box

. binationsofthemultiset.Moregenerally,wehaveabijectionbetweenthesetofall ofamultisetwithktypesofobjectsofmultiplicitiesnjandthesetofassignmentofridenticalobjectsintokboxesBjwithcapacitiesnj.Wemayusethistodeducethenumberof binationsinthecasen1,n2,...,nk≥r,whichwepresentedinanearliertheorem,fromthe IndistinguishableObjectsandkdistinguishableboxesB1,B2,...,BkisequaltoC(r+k−1,k−1)Proof{1,2,...,n+k−1}intothesetofallpossibledistributionsoftheobjectstothekboxes.Forexample,forr=5andk=3,we 离散数学第1周和第2UweSchauz博士西交利物浦大学数学2014112627将对象分配到盒子中Brualdi页面：27-60。你可以带计算器。我们在考试中也需要它备注（乘法原理）n1，n2n1·n2这两种操作。如果有m种不同的事情，第一个可以用n1种方法完成，第二个可以用n2种方法n1·n2·····nmS1,S2,...,SmS1S2×···×Sm||S1|·|S2|·...·|Sm|示例从{A,B,C}中选择一个元素，从{X,Y}中选择一个元素，就是从{AX,AY,BX,CX,CY}中选择一个元素，或者从{A,B,C}×{X，Y}。有3·2=6备注（加法原理）n1n2n1n2mn1n2么有n1+n2+…+nmS1,S2,...,Sm是成对不相交的有限集，则S1[S2[…[Sm|=|S1|+|S2|+···+|Sm|。示例从{A,B,C}或{X,Y}中选择一个元素，就是从{A,B,C,X,Y}={A,B,C}[{X,为了统计集合A的元素，我们可以首先证明A和另一个集合B之间存在双射，然后统计BAB（双重计数）。虽然第一次计数产生|B|，第二个给出|B|作为|A|的函数。如果在第二次计数中|B|显示为|A|的倍数，我们只需除以得到|A|来自|B|（划分原则）。MTH114定义和定理设r2N和X={x1,x2,...,xn}是一个包含n<1XrrX(xj1,xj2,...,xjrr有n个这样的r元组。集合X的r排列是一个序列(xj1,xj2,...,xjrr的X的成对不同元素。不允许重复。有P(n,r)=nPr:=n·(n.1)···(n.r=n！许多这样的r排列，如果0rn。否则，P(n，r)=0XrXr{xj1,xj2,...,xjr.n！n有C(n,r)=nCr=:=许多这样的rn。r）！呃！r元素的组合，如果0rn。否则，C(n,r)=0。 有20名成员。、、财务长和的将被填补。可能有多少种不同 次不同的 计数职位1 2会长副会长财务 PeterJieMayXuJieMayXuPeter示例A有20名会员。可能有多少种不同的4人 次 计 数职位 1 2PeterJie MayXuPeter定义和定理设r2N且X={n1·x1,n2·x2...,nk·xk}nn1n2···nk1kxiXrXr(xj1,xj2,...,xjrxj最多nj次。有P(n;n1,n2,...,nk)=n:=n!许多n1,n2,...,nk n-排列（排列）如果njr对于j=1,2,...,k，则X的r排列恰好是基础集合{x1,x2,...,xk}上的rkrXrr{m1·x1,m2·x2mk·xk}X即r=m1+m2+…+mk和0mjnj对于j=1,2,...,k。如果njr对于j=1,2,...,kor+k.1C(rk1,r)=r备注集合X={x1,x2,...,xn}上的r元组y=(y1,y2,...,yr)基本上只是一个函数y:2,...,r}.!X，7.！y(i):=yi。备注集合X={x1,x2,...,xn}的r排列=(y1,y2,...,yr)y:{1,2,...,r}.!X，7.！y(i):=yinX{n1·x1,n2·x2nk·xk}y=(y1,y2,...,yn)本上是一个函数y:{1,2,...,n}.!{x1,x2,...,xk},i7.!y(i):=yi,|y.1(xj)|njj=1,2,...,kn1=2n2=2n3=3z}|{z}|{z}|y=(C,A,A,C,B,B,C)是{A,A,B,B,C,C,C}1.23456y{1,2,7}{A,B,C}2,3|{z}7.!7.！C|y.1(A)|=2=7.！7.！47.！C