noip初赛中组合数学

noip初赛中的组合数学排列和组合：怎么排，怎么组合？研究的意义在于统计排列和组合的个数。四个基本的计数原理：加法原理、乘法原理、减法原理、除法原理。排列：全排列P(n,n)=n!部分排列P(n,r)=n*(n-1)*(n-2)*……*(n-r+1)=n！/(n-r)!圆排列:Q(n,n)=P(n,n)/n=(n-1)!组合:C(n,r)=n!/((n-r)!*r!)学习提示：每条公式都要给出它的物理意义。第一章加法原理与乘法原理1.加法原理:完成一个工程可以有n类办法，a[i](1=i=n)代表第i类方法的数目。那么完成这件事共有S=a[[1]+a[2]+...+a[n]种不同的方法。2.乘法原理:完成一个工程需要分n个步骤，a[i](1=i=n)代表第i个步骤的不同方法数目。那么完成这件事共有S=a[[1]*a[2]*...*a[n]种不同的方法。3.两个原理的区别:一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”。练习1.由数字1，2，3，4，5可以组成多少个三位数（分别讨论各位上的数字允许重复和不允许重复的情况）？题解：乘法原理，重复：125，不重复：602.由数字0、1，2，3，4，5可以组成多少个三位数（讨论各个位上数字允许重复和不重复的情况）？题解：先区分首位是否为0（加法原理），再分别用乘法原理。重复：180，不重复？3.由数字0，1，2，3，4，5可以组成多少个十位数字大于个位数字的两位数？154.一个三位密码锁,各位上数字由0,1,2,3,4,5,6,7,8,9十个数字组成,可以设置多少种三位数的密码(各位上的数字允许重复)？1000首位数字不为0的密码数是多少种？900首位数字是0的密码数又是多少种？1005.如图，要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不同的颜色，不同的涂色方案有多少种？66.某班有22名女生，23名男生.选一位学生代表班级去领奖，有几种不同选法？45选出男学生与女学生各一名去参加智力竞赛，有几种不同的选法？5067.105有多少个约数？8并将这些约数写出来.约数的计算公式s=(p1+1)*(p2+1)…*(pk+1)（pi为第i个质约数的幂）8.从5幅不同的国画、2幅不同的油画、7幅不同的水彩画中选不同画种的两幅画布置房间有几种选法？题解：59，这题是加法原理和乘法原理的结合。9.若x、y可以取1，2，3，4，5中的任一个，则点(x，y)的不同个数有多少？2510.一个口袋内装有5个小球另一个口袋内装有4个小球，所有这些小球的颜色各不相同，从两个口袋内任取一个小球，有几种不同的取法?9从两个口袋内各取一个小球，有几种不同的取法.2011.乘积(a1+a2+a3)*(b1+b2+b3+b4)*(c1+c2+c3+c4+c5)展开共有几个项。题解：60，展开的每一项必定含有一个a一个b一个c，那么我们可以认为我们挑一个a再挑一个b再挑一个c，所以结果是3*4*5=60。12.有四位考生安排在5个考场参加考试.有几种不同的安排方法。625第二章排列与组合的概念与计算公式1．排列（在乎顺序）全排列：n个人全部来排队，队长为n。第一个位置可以选n个，第二位置可以选n-1个，以此类推得：P(n,n)=n(n-1)(n-2)……3*2*1=n!(规定0!=1).部分排列：n个人选m个来排队(m=n)。第一个位置可以选n个，第二位置可以选n-1个，以此类推，第m个（最后一个）可以选(n-m+1)个，得：P(n,m)=n(n-1)(n-2)……(n-m+1)=n!/(n-m)!(规定0!=1).2．组合（不在乎顺序）n个人m(m=n)个出来，不排队，不在乎顺序C(n,m)。如果在乎排列那么就是P(n,m)，如果不在乎那么就要除掉重复，那么重复了多少？同样选出的来的m个人，他们还要“全排”得到P(n,m)，所以得：C(n,m)*m!=P(n,m)C(n,m)=P(n,m)/m!=n!/((n-m)!*m!)组合数的性质1:)(,nmCCmnnmn组合数的性质２:)(,111nmCCCmnmnmn如果编程实现,以上两个公式有没有帮助？练习：311P、811P、311C、811C、9991001C3．其他排列与组合（1）圆排列：n个人全部来围成一圈为Q(n,n)，其中已经排好的一圈，从不同位置断开，又变成不同的队列。所以：Q(n,n)*n=P(n,n)Q(n)=P(n,n)/n=(n-1)！由此可知，部分圆排Q(n,r)＝P(n,r)/r=n!/(r*(n-r)!).（2）重复排列(有限)：k种不一样的球，每种球的个数分别是a1,a2,...ak,设n=a1+a2+…+ak，这n个球的全排列数，为n!/(a1!*a2!*...*ak!).（3）重复组合(无限)：n种不一样的球，每种球的个数是无限的,从中选k个出来，不用排列，是组合，为C(n+k-1,k).证明：假设选出来的数（排好序）1=b1=b2=b3…….=bk=n这题的难点就是=号，现在去掉=号，所以有：1=b1b2+1b3+2b4+3…….bk+k-1=n+k-1中间还是k个数！不过已经不是b系列，而是c系列假设c[i]:=b[i]+i-1，所以1=c1c2c3c4…….ck=n+k-1所以问题就开始转换为无重复组合问题，即在n+k-1个元素中选中k个的组合数C(n+k-1,k)。(4)不相邻排列：1~n这n个自然数中选k个，这k个数中任何两个数不相邻数的组合有C(n-k+1,k).证明和（3）相同，同学们马上证明吧。(5)第二类stirling数（子集划分）：要背（**2007普及）、将n个数（1，2，…，n）分成r个部分。每个部分至少一个数。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为{(1),(234)}，{(2),(134)}，{(3),(124)}，{(4),(123)}，{(12),(34)}，{(13),(24)}，{(14),(23)}。当n=6，r=3时，S(6,3)=_____________。（提示：先固定一个数，对于其余的5个数考虑S(5,3)与S(5,2)，再分这两种情况对原固定的数进行分析。）题解：90.递推的解法近几年很重要。S(6,3)=3*S(5,3)+S(5,2)S(5,3)=3*S(4,3)+S(4,2)S(5,2)=2*S(4,2)+S(4,1)第二类stirling数，显然拥有这样的性质：①S(n,m)=m*S(n-1,m)+S(n-1,m-1)②S(n,1)=1,S(n,0)=0,S(n,n)=1而这些性质就：▲S(n,3)=1/2*(3^(n-1)+1)-2^(n-1)(6)错位排列（简称:错排）先做一个小问题：5本书，编号分别是1，2，3，4，5，现在要把这5本书是放在编号1，2，3，4，5的书架上，要求书的编号和书架的编号不一样，请问有多少种不一样的放置方法？例：胸口贴着编号为1,2,....n的n个球员分别住在编号为1,2,....n的n个房间里面。现规定每个人住一个房间，自己的编号不能和房间的编号一样。这就是错排问题。当n=3时，只能为312或231这两种。题解：递推。刚开始所有球员都住在和自己编号一样的房间里面。然后错排开始了，第n个球员从第出来。第一种情况：n想和i（)1(1ni）其中任何一个球员换房间，其他n-2个人换房间的事情，他们就不管了。其他n-2个球员的的错排数为d[n-2]，n可以和前面1~（n-1）对换，所以有（n-1）个d[n-2]。第二种情况：n想和i（)1(1ni）其中任何一个球员换房间，但是n只想i住在第N个房间，而n不想住第I个房间。可能你会这样想：那么n可以让j住在第I号房间里面，然后n住在房间J。抱歉，jijnj),1(1生气n为什么一开始就去找i不直接来找j，~~(╯﹏╰)~~没办法，n把自己胸口的编码N换成了I，他假装自己是i，然后错排１～ｎ－１（也就是d[n-2]）。的时候参与进去，这样自己就不会呆在第I号房间了。所以有（n-1）个d[n-１]。如果理解了上面两个加蓝色的地方，那么错排的公式就出来了3)(n)d1)(d-(nd1-n2-nn同时也有n1-nn(-1)d*nd错位排列数列为0，1，2，9，44，265，．．．．．．(7)Catalan数列（重点）以下问题属于Catalan数列1：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？2：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？3：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?4：对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数?5：一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?6：n个结点可够造多少个不同的二叉树?7：n个不同的数依次进栈，求不同的出栈结果的种数？8：n个+1和n个-1构成2n项a1,a2,...,a2n其部分和满足a1+a2+...+ak=0(k=1,2,3,..,2n)对与n该数列为其对应的序列为1,1,2,5,14,42,132,....===Catalan数列。H0H1H2H3H4H5H6该递推关系的解为1,2,3,...)(n1CHnn2nn练习1．（1）用0，1，2，3，4组合多少无重复数字的四位数？分类+组合（96）（2）这四位数中能被4整除的数有多少个？分类+组合（30）（3）这四位数中能被3整除的数有多少个？分类+组合（36）2．用0，1，2，3，4五个数字组成无重复数字的五位数从小到大依次排列.（1）第49个数是多少？（30124）（2）23140是第几个数？（40）3．求下列不同的排法种数：（1）6男２女排成一排，2女相邻；(p(7,7)*p(2,2))（2）6男２女排成一排，2女不能相邻；(p(6,6)*p(7,2))（3）5男3女排成一排，3女都不能相邻;(p(5.5)*p(6,3))（4）4男4女排成一排，同性者相邻；(p(4,4)*p(4,4)*p(2,2))（5）4男4女排成一排，同性者不能相邻。(p(4,4)*p(4,4)*p(2,2))4．有四位医生、六位护士、五所学校。(1)若要选派三位医生到五所学校之中的三所学校举办健康教育讲座，每所学校去一位医生有多少种不同的选派方法？(c(5,3)*p(4,3))(2)在医生或护士中任选五人，派到五所学校进行健康情况调查，每校去且仅去一人，有多少种不同的选派方法？(p(10,5))(3)组成三个体检小组，每组一名医生、两名护士，到五所学校中的三所学校为老师体检，有多少种不同的选派方法？(c(5,3)*p(4,3)*c(6,2)*c(4,2)*c(2,2))5．平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？(2250)6．平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？(751)7．将N个红球和M个黄球排成一行。例如:N=2,M=2可得到以下6种排法:红红黄黄红黄红黄红黄黄红黄红红黄黄红黄红黄黄红红问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法)(35)8.用20个不同颜色的念珠穿成一条项链,能做多少个不同的项链.(20!/20)9.在单词MISSISSIPPI中字母的排列数是(11!/(1!*4!*4!*2!)10．求取自1,2,...k的