第二周-小乒乓球的组合之旅

1组合数学Combinatorics2小乒乓球的组合之旅2-1加减乘除来计数计数的基本法则清华大学马昱春关注国球•国球----乒乓球–第５２届世界乒乓球锦标赛将于２０１４年４月２８日－５月５日在日本东京–2014年“直通东京”中国乒乓球队选拔赛于2014年1月25日在镇江开赛2行程规划•北京-镇江–高铁动车7趟；其他列车2趟–7+2=9种不同行程–分类加法•北京-镇江–飞机北京-南京上午5趟航班动车南京-镇江下午6趟–5×6=30种不同行程–分步乘法341.1加法法则与乘法法则[加法法则TheSumRule]设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言：若|A|=m,|B|=n,AB=,则|AB|=m+n。男生25女生5全班25+5=30。非文科班级51.1加法法则与乘法法则[乘法法则TheProductRule]设事件A有m种产生方式，事件B有n种产生方式，则事件A与B有mXn种产生方式。集合论语言：若|A|=m,|B|=n,AB={(a,b)|aA,bB},则|AB|=mXn。非文科班级，如果选一个男生做班长，一个女生做团支部书记，请问多少种不同的组合呢？第一步，选班长，25种第二步，选支部书记5种25×5=12561.1加法法则与乘法法则加法法则:分类乘法法则:分步注意为了加法法则和乘法法则运用时要注意事件的独立性班里有位男同学gfs，一位女同学bfm，双胞胎兄妹如果选一个男生做班长，一个女生做团支部书记，请问多少种不同的组合呢？71.1加法法则与乘法法则分类1.选gfs当班长，女生的选择有4个1×4=42.不选gfs当班长，男生的选择有24个，女生选择有5个4+24×5=12481.1加法法则与乘法法则更直观的算法？合理的要分情况讨论，那不合理的只有一种所以全部的方案数–不合理方案=125–1=1249USA•减法法则：A表示解的集合，U是包含A的一个全集•定义A的补集：ThecomplementofAinU:Ā=U\A={xU:xA}•计算A的个数就是•|A|=|U|-|Ā|101.1加法法则与乘法法则除法法则：25个男生分成5组，每组的男生数25/5=5加减乘除的计数法则我们都介绍了11组合数学Combinatorics2小乒乓球的组合之旅2-2点兵点将排列组合定义黑板上的排列组合，你舍得解开吗？清华大学马昱春乒乓球放盒子•排列和组合•编号的乒乓球：–4个乒乓球：1号，2号，3号，4号–取出其中的3个–如果考虑顺序，则称之为排列数P(4,3)•P(4,3)=4×3×2=24–如果不考虑顺序，则称之为组合数C(4,3)•C(4,3)=24/3！=412无重排列无重组合13排列与组合定义[排列Permutation]从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的个数用P(n,r)表示，或者。当r=n时称为全排列。一般不说可重即无重。(n≥r)定义[组合Combination]从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。(n≥r)组合的个数用C(n,r)表示或者rnPrnC14排列的模型[排列Permutation]从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。(n≥r)•第1个盒子有n种选择，第2个有n-1种选择，······，第r个有n-r+1种选择。故有P(n,r)=n(n-1)······(n-r+1)=有时也用[n]r记n(n-1)······(n-r+1)全排列：P(n,n)=n!)!(!rnn2P(n,r)=nP(n-1,r-1)•分步递推–选No.1盒子内的乒乓球•n种选择–从n-1个球中选出r-1个放入r-1个盒子内的排列•P(n-1,r-1)排列P(n,r)的递推关系15P(n,r)=P(n-1,r)+rP(n-1,r-1)•分类递推–不选第一个球？•P(n-1,r)–选择第一个球？•rP(n-1,r-1)12r13n……n-1个球r-1个盒子[][]212r13n……r-1个盒子16组合的模型若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)·r!=P(n,r)=)!(!!),(rnrnrnC)!(!rnnC(n,r)=C(n,n-r)n个乒乓球中选出r个的方法自然等于剩下n-r个的方法。C(n,l)C(l,r)=C(n,r)C(n-r,l-r)非文科班级共n位同学，选出l位班委，班委中选出r位为核心；先从n个同学中选出r个核心，再从剩下的n-r中选剩下的l-r班委组合模型•格路模型：•从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，其路径数是C(m+n,n).1717y(m,n)...0...x…xyx…xxyy…第n行第r列的数值是C(n,k)第n行对应(a+b)n的系数？组合数和多项式展开系数？0nr二项式定理•(a+b)n=C(n,0)an+C(n,1)an-1b+…+C(n,n)bn•(a+b)(a+b)…(a+b)n个(a+b)ab…a从n个位置中选出r个b,构成了an-rbr其个数C(n,r)即an-rbr•若a=b=1,则有–2n=C(n,0)+C(n,1)+…+C(n,n)•若a=1,b=-1,则有–0=C(n,0)-C(n,1)+…±C(n,n)18组合恒等式CombinatorialIndentities19•C(n,r)=C(n-1,r)+C(n-1,r-1)•等式左侧:(0,0)至(n-r,r)所有格路•等式右侧:–(0,0)至(n-r-1,r)–(0,0)至(n-r,r-1)nry(n-r,r)...0...x(n-r-1,r)(n-r,r-1)恒等式•C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+…+C(m,r)C(n,0)•即Vandermonde恒等式Vandermonde'sidentity•Alexandre-ThéophileVandermonde(28February1735–1January1796)法国音乐家，数学家•DonaldE.Knuth(高德納)在TheArtofComputerProgrammingVol.ii(1998)中,讲到实际上这个恒等式的变形体早在1303由朱世杰在《四元玉鉴》介绍了.•Chu-Vandermonde恒等式20乒乓球来证明恒等式21•C(m+n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+…+C(m,r)C(n,0)•C(m,0)C(n,r)+C(m,1)C(n,r-1)+…+C(m,r)C(n,0)。。。。。。。。。。。。mredballsnblueballsChooserballsfromthem22组合数学Combinatorics2小乒乓球的组合之旅2-3小乒乓球的大花样清华大学马昱春23排列组合问题的来源•排列组合问题，最早见于我国的《易经》一书．–所谓“四象”就是每次取两个爻(yáo)的排列，“八卦”是每次取三个爻的排列．•在汉代数学家徐岳的《数术记遗》（公元2世纪）中，也曾记载有与占卜有关的“八卦算”，即把卦按不同的方法在八个方位中排列起来．–它与“八个人围一张圆桌而坐，问有多少种不同坐法”这一典型的排列问题类似．24圆排列•圆排列：从n个中取r个的圆排列的排列数为P(n,r)/r,2≤r≤n•以4个元素为例1243123412432341124334121243412325项链排列•项链排列：排列的方法和项链一样,在圆排列的基础上，正面向上和反面向上两种方式放置各个数是同一个排列。•例下面两种方式实际上表示的都是3个元素的同一种排列。•从n个中取r个的项链排列的排列数为P(n,r)/2r,3≤r≤n11233226可重排列例26个英文字母能组成多少4位数的字符串？264例26个英文字母能组成多少4位数的字符串，其中每位字母都不相同？P(26,4)例26个英文字母能组成多少4位数的字符串，其中每位字母都不相同且b和d不相邻？P(26,4)–C(24,2)*3!*227多重全排列•多重排列：•请问“pingpang”8个字母有多少种不同的排列？–2个p,2个n，2个g，1个i，1个a，–其多重排列记为–加上下标以区别p1p2n1n2g1g2ia•p,n,g下标排列分别有2!112228！！！！8222112228！！！！222811222828多项式展开•求r1个1，r2个2，…，rt个t的排列数，设r1+r2+…+rt=n,设此排列数为P(n;r1,r2,…,rt)•对1，2，…，t分别加下标，得到P(n;r1,r2,…,rt)·r1!·r2!·…·rt!=n!•∴P(n;r1,r2,…,rt)·=•多项式展开nkknknkknknbaknCbaknknba00),()!(!!)(nraarrnaaairttrtnt...!!...!)...(11121!!....!!21trrrntrrrn...2129多重全排列例乒乓球入洞游戏：共有6个洞，洞口每次每次只能进入一个乒乓球，一组编号为1-9的9个乒乓球滚入洞口的方案有多少？[解]一进站方案表示成：XX11XX1X1X1XXX其中“X”表示某人，“1”表示门框，其中“X”是不同元，“1”是相同元。任意进站方案可表示成上面14个元素的一个排列。27145983630多重全排列XX11XX1X1X1XXX[解法1]给每个方案的门标号可产生5!个14个元的全排列。故若设x为所求方案数，则x·5!=14!∴x=14!/5!=726485760[解法2]在14个元的排列中先确定“1”的位置，有C(14,5)种选择，再确定球的位置，有9！种选择。故C(14,5)·9!即所求311.2排列与组合[解法3]把全部选择分解成若干步，使每步宜于计算。•1号有6种选择；•2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；•3号的选择方法同2号，故共有8种•。。。。•以此类推，9号有14种选择。故所求方案为6*7*8*….*14=14!/5!=72648576013232组合数学Combinatorics2小乒乓球的组合之旅2-4多样的组合清华大学马昱春准备果篮•苹果和梨两种水果，要选4个水果做果篮•多重集：元素可以多次出现的集合。ti=0,1,…∞表示元素ai可以出现的次数，含有n个不同元素的多重集可以记为{t1·a1,t2·a2…,tn·an}•ti=∞多重集•可重组合：从A={1,2,3….n}中取r个元素{a1,a2,…ar},ai∈A，i=1,2,..r,且允许ai=aj,i≠j，记为C(n,r)。33苹果梨13223140可重组合•A={1,2,3,4}中取5个元素构成组合，元素可以重复•可重组合：•{11334}•可重组合模型：取r个无标志的球，n个有区别的盒子，每个盒子允许放多于一个球，或者空盒。•无重组合的模型：n个球是有区别的，r个盒子是无区别的，取r个球放入盒子，每个盒子一个球。34123123435可重组合123401234{1，1，3，3，4}{1，2，5，6，8}构造相关的无重组合(1)(4+5-1)……C(8,5)在n个不同的元素中取r个进行组合，允许重复的组合数为C(n+r-1,r)01r-1{a1,a2……ar}(1)(n+r-1)a1,a2+1,a3+2…..ak+k-1,…ar+r-11≤a1≤a2≤…≤ar≤nr个数r个数是否无重？反证法：假设存在ij,ai+i-1=aj+j-1，则aiaj，但是ij时,aiaj,矛盾，因此必然是无重……36•在n个不同的元素中取r个进行组合，若允