《组合数学》教案1章(排列组合基础)

1、组合数学第一章组合数学基础第1章组合数学基础1.1绪论(一)背景起源：数学游戏幻方问题：给定自然数1,2,，n2,将其排列成n阶方阵，要求每行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行(或列、或对角线)之和称为幻方的和(简称幻和)。例：3阶幻方，幻和=(1+2+3+9)/3=15。关心的问题(1)存在性问题：即n阶幻方是否存在？(2)计数问题：如果存在，对某个确定的n,这样的幻方有多少种？(3)构造问题：即枚举问题，亦即如何构造n阶幻方。奇数阶幻方的生成方法：一坐上行正中央，依次斜填切莫忘,上边出格往下填，右边出格往左填,右上有数往下填，右上出格往下填例：将 2

2、, 4, 6, 8,10,12,14,16,18填入下列幻方:36/58 姜建国【例1.1.1】（拉丁方）36名军官问题：有1,2,3,4,5,6共六个团队，从每个团队中分别选出具有A、B、C、D、E、F六种军衔的军官各一名，共36名军官。问能否把这些军官排成6X6的方阵，使每行及每列的6名军官均来自不同的团队且具有不同军衔？本问题的答案是否定的。A1B2C3D4E5F6B2C3D4E5F6A1C3D4E5F6A1B2D4E5F6A1B2C3E5F6A1B2C3D4F6A1B2C3D4E5A1B2C3D4E5F6B3C4D5E6F1A2C5D6E1F2A3B4D2E3F4A5B6C1E4F5A

3、6B1C2D3F6【例1.1.2（计数一一图形染色）用3种颜色红（r）、黄（y）、蓝（b）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。求本质上不同的染色方案。举例：(a)(b)形式总数：34=81种。1实际总数（见第6章）：L=1（34+32+2m3）=244【例1.1.31（存在性）不同身高的26个人随意排成一行，那么，总能从中挑出6个人，让其出列后，他们的身高必然是由低到高或由高到低排列的（见第5章）。注意：不改变原来的相对顺序。（2） 研究内容算法分类：第一类：数值算法。主要解决数值计算问题，如方程求根、解方程组、求积分等，

4、其数学基础是高等数学与线性代数（解决建模问题，数值分析或称计算方法解决离散化问题，即在计算机上的求解方法问题）。第二类：组合算法。解决搜索、排序、组合优化等问题，其数学基础为组合数学。按所研究问题的类型，研究内容组合计数理论组合设计组合矩阵论组合优化本课程重点：以组合计数理论为主，部分涉及其它内容。（3） 研究方法分类：第一类：从组合学基本概念、基本原理出发解题的所谓常规方法（利用容斥原理、二项式定理、Pdya定理解计数问题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等）。第二类：通常与问题所涉及的组合学概念无关，而对多种问题均可使用。例如：(1)数学归纳法：前提是已知问题的结

5、果。(2)迭代法【例】已知数列n满足关系1hn=2hn-11,求hn的解析表n21达式。(解)直接迭代即得：hn=2hn.11=2(2hn/+1)+1=22hn二十2十1=22(2hn+1)+2+1=23h-+22+2+1=2n1h12nl2n4 222 12n1(3)一对应技术原理：建立两类事物之间的对应关系，把一个较复杂的组合计数问题A转化成另一个容易计数的问题B,从而利用对B的计数运算达到对A的各种不同方案的计数。思路：将未解决问题的模式转化为一种已经解决的问题模式。(4)殊途同归方法原理：从不同角度讨论计数问题，以建立组合等式。应用：组合恒等式的证明(也称组合意义法)。(5)数论方法特

6、别是利用整数的奇偶性、整除性等数论性质进行分析推理的方法。组合数学用的较多的方法：（3）与（4）。【例1.1.4有100名选手参加羽毛球比赛，如果采用单循环淘汰制，问要产生冠军共需要进行多少场比赛？（解）常规思路：50+25+12+6+3+2+1=99场10000名选手：5000+2500+1250+625+312+1采用一一对应方法：每场比赛产生一个失败者，且每个失败者只能失败一次（场次一失败者）。反之，要淘汰一个选手，必须恰好经过一场比赛（失败者一场次）。结论：失败者修比赛场次。应该比赛99场。一般情况：单循环淘汰制，n个选手，比赛n1场。【例1.1.51设某地的街道将城市分割成矩形方格，

7、某人在其住处A（0,0）的向东7个街道、向北5个街道的大厦B（7,5）处工作（见图1.1.3）,按照最短路径（即只能向东或向北走），他每次上班必须经过某12个街段，问共有多少种不同的上班路线？（解）（1）将街道抽象为等长的。（2）对应为（元素可重复的）排列问题:路径（蓝色）一排列xyyxxyyxxxxy排列yxxyyyyxxxxx7路径（红色）结论：最短路径修7个x和5个y的排列（3）求解：再对应为（元素不重复的）排列问题12!N=C7=C12=7925!7!512（4） - 短路径数为般情形：从（0,0）点到达（m,n）点的不同的最mnN=Cmn=Cmn1.2两个基本法则1.2.1加法法则（

8、1） 力口法法则常规描述：如果完成一件事情有两个方案，而第一个方案有m种方法，第二个方案有n种方法可以实现。只要选择任何方案中的某一种方法，就可以完成这件事情，并且这些方法两两互不相同。则完成这件事情共有m+n种方法。集合描述：设有限集合A有m个元素，B有n个元素，且A与B不相交，则A与B的并共有m+n个元素。概率角度描述：设事件A有m种产生方式，事件B有n种产生方式，则事件“A或B”有m+n种产生方式。当然A与B各自所含的基本事件是互相不同的。（2） 应用【例1.2.11某班又男生18人，女生12人，从中选出一名代表参加会议，问共有多少种选法？（解）（1）两个选择方案：男生（18种选法）或女

9、生（12种选法）。由加法法则，有18+12=30选法。（2）设集合：A男生，B女生。该班中的学生要么属于A,要么属于B,且AB=*，故A+B=18+12=30。（3）事件A选男生（18种可能），事件B选女生（12种可能）。事件“A或B”一一选男生或女生，由加法法则，有18+12=30种可能。【例1.2.21用一个小写英文字母或一个阿拉伯数字给一批机器编号，问总共可能编出多少种号码？（解）26+10=36个。其中英文字母共有26个，数字。9共10个。1.2.2乘法法则（1） 乘法法则常规描述：如果完成一件事情需要两个步骤，而第一步有m种方法、第二步有n种方法去实现。则完成该件事情共有mn种方法。

10、集合描述：设有限集合A有m个元素，B有n个元素，且A与B不相交，a三A,beB,记（a,b）为一有序对。所有有序对构成的集合称为A和B的积集（或笛卡儿乘积），记作AMB。那么，AMB共有m,n个元素。AB=a,baA,bB概率角度描述：设离散型随机变量X有m个取值，Y有n个取值，则离散型随机向量（X,Y）有m，n种可能的取值。（2） 应用【例1.2.31仍设某班有男生18人，女生12人，现要求从中分别选出男女生各一名代表全班参加比赛，问共有多少种选法？（解）（1）分两步挑选，先选女生（12种选法），再选男生（18种选法）。由乘法法则，有12X18=216种选法。（2）设集合：A男生，B女生。由

11、乘法法则，AXB=18X12=216（3）变量X男生（18种取值），变量Y女生（12种取值）。由乘法法则，随机向量（X,Y）有18X12=216种可能的值。【例1.2.41给程序模块命名，需要用3个字符，其中首字符要求用字母AG或UZ,后两个要求用数字19,问最多可以给多少种程序命名？（解）首字符选法：7+6=13种（加法法则）。总数：13X9X9=1053种（数字可重复使用）（乘法法则）,【例1.2.51从A地到B地有弭条不同的道路，从A地到C地有电条不同的道路，从B地到D地有m1条不同的道路，从C地到D地有m2条不同的道路，那么，从A地经B或C到达目的地D共有多少种不同的走法？（解）路线A

12、TBTd：n1xm1种走法（乘法法则）路线ATCTD：n2Xm2种走法（乘法法则）总数：n1m1+n2m2种走法（加法法则）2X3+3X4=181.3排列与组合1.3.1相异元素不允许重复的排列数和组合数(一)计算公式从n个相异元素中不重复地取r个元素的排列数和组合数:(1)排歹！J:P；=Pn,r=nn-1n-r1=n!nr!推导：反复利用加法法则与乘法法则(2)组合：C：=C(n,r)=n-=-lr,r!(n-r)!r!推导：利用组合与排列的异同(3)例：n=5,r=3,即元素为1,2,3,4,5排歹h134,143,314,341,413,431;254,425,组合：134,245,(

13、4)特点：排列考虑顺序，组合不然。(二)数学模型(1)排列问题：将r个有区别的球放入n个不同的盒子，每盒不超过一个，则总的放法数为P(n,r)。(2)组合问题：将r个无区别的球放入n个不同的盒子，每盒不超过一个，则总的放法数为C(n,r)。对应关系兀义9盒子位置H球兀素和位置编号12345ABC排列1ABC134排列2CBA431排歹U3ACB143排列4ACB254排列5BAC425组合1134组合22451.3.2相异元素允许重复的排列（1） 问题r个元素的排列，简称r元从n个不同元素中允许重复地选重复排列，排列数记为RP（s,r）。（2） 模型将r个不相同的球放入n个有区别的盒子，每个盒

14、子中的球数不加限制而且同盒的球不分次序。对应关系兀素1盒子位置球兀素和位置编号12345ABC排列1ABC114排列2CBA433排歹U3ACB343排列4ABC222排列5BAC425（3） 计算公式RP（oo,r）=nr（4） 集合描述方式设无穷集合S=%产。,产enL从S中取r个元素的排列数即为RP（s,r）。不重复排列：S=1e,10,，1a）=e1,e2，en。1.3.3不尽相异元素的全排列（一）问题有限重复排列（或部分排列）：设S=1n1e,n2e2,ntet（叫+“+%=n）,从S中任取r个元素，求其排列数RP（n,r)(二)模型将r个有区别的球放入t个不同的盒子，每个盒子的容量

15、有限，其中第i个盒子最多只能放入小个球，求分配方案数。例：S=21,42,13,34,25=1,1,2,2,2,2,3,4,4,4,5,5对应关系兀素1盒子位置H球兀素和位置编号12345ABC排列1ABC114排列2BCA433排歹U3ACB343排列4ABC222排列5BAC425说明：(1)极端情形：相异元素不重复的排列强调的是不重复，即盒子的容量为1;(2)极端情形：相异元素允许重复的排列强调的是无限重复，即盒子的容量无限；(3)一般情形：不尽相异元素的排列强调的是有限重复，即盒子的容量有限，介于两者之间。(三)特例(1) r=1:RP(n,1)=t(2) r=n(全排列)n!RPn,

16、n=nJm!nt!例a1a2a3b1b2clc2与aa2a3a8灯32aha2b2&a3c2与a2b1a1b2Ga3c2,、n!(3) t=2,RP(n,n)=-n-n1!n2!(4) nini=1,即不重复的排列 =如，即重复排列1. 3. 4相异元素不允许重复的圆排列(一)圆排列【例1.3.1】把n个有标号的珠子排成一个圆圈，共有多少种不同的排法？（解）称为圆排列（相对于线排列）。条件：元素同时按同一方向旋转，绝对位置变化，相对位置未变，即元素间的相邻关系未变，视为同一圆排列。结论：1个圆排列对应n个线排列。P n, n CP(n, n )= (n 1)!【例1.3.2从n个相异元素中不重

17、复地取r个围成圆排歹U,求不同的排列总数CP（n,r）。Prn!（解）CP（n,r）=-rrn-r!（二）项链排列【例1.3.31将5个标有不同序号的珠子穿成一环，共有多少种不同的穿法？（解）称为项链排列。条件：可以翻转的圆排列。即同一项链不用剪断重穿，翻过来仍是原项链。结论：两个圆排列对应一个项链排列，故有24/2=12种。(a)(b)图1.3.1项链排列一般情形：从n个相异珠子中取r个的项链排列数：P：=n!2r2rn-r!允许重复的圆排列：情况复杂，参见反演公式（第四章）1. 3.5相异元素允许重复的组合（一）问题设$=Qe,2,00en从S中允许重复地取r个元素构成组合，称为r可重组合

18、，其组合数记为RC（s,r）。（二）抽象记S为S=001,002,8n例：n=5,r=4:1111,1122,1345,55557a)计算公式设所选r个元素为：1wa1aa2a-arn令bi=ai+(i-1),i=1,2,r则1b1cb2-brwn+(r1)反之ai=bi-i-1结论：与从n+r-1个相异兀素中不重复地取r个兀素的组合方案对应。,、，(n+r-1)!RC(/,r)=C(n+r-1,r)=.r!(n-1)!例：n=5,r=4分类重复组合不重复组合儿系1,2,3,4,51,2,3,5,6,7,8部分组合11111234112212452245236855555678(四)模型将r个

19、无区别的球放入n个不同的盒子，每个盒子的球数不受限制。(五)应用【例1.3.41不同的5个字母通过通信线路被传送，每两个相邻字母之间至少插入3个空格，但要求空格的总数必须等于15,问共有多少种不同的传送方式？(解)三步求解：(1)先排列5个字母，排列数P(5,5)=5!。(2)两个字母间各插入3个空格，将12个空格均匀地放入4个间隔内，有1种方案。cbdea(3)将余下的3个空格插入4个间隔：分析：将3个相同的球放入4个不同的盒子，盒子的容量不限。方案1:bdea方案2:bdAAAea归纳：从4个相异元素中可重复地取3个元素的组合数RC(g,3)=C(4+3-1,3)=20。(4)总方案数：L

20、=5!120=24001. 3.6不尽相异元素任取r个的组合问题(一)问题设集合S=nie,出e2,ntet(n1+n2+nt=n),从S中任取r个，求其组合数RC(n,r)。(二)组合数中间工具：组合问题的母函数：tnitnnzxj=n(1+x+x2+xni)=zarxri4j力i1r力答案：RC(n,r)=ar(三)应用【例1.3.51整数360有几个正约数？(解)(1)标准素因数分解：360=23X32X5(2)正约数及其条件1 =20X30X50,2=2X30X50,3=20X3X50,5=20X30X5,22=22x30X50,6=2X3X50=3X2,90=2X32X5,180=2

21、2X32X5,360=23x32X5结论：正整数d是360的正约数ud=2a3b5c且0WaW3,0b2,0WcW1。故14不是约数，16=24也不是约数。(3)问题转化：求S=132,23,15)的所有组合数之和。(4)求解：构造多项式P6(x)=(1+x+x2+x3)(1+x+x2)(1+x)=1+3x+5x2+6x3+5x4+3x5+x66系数求和：RC(6,i)=1+3+5+6+5+3+1=24i=06方法化简：求P6(1)=RC(6,i)=4X3X2=241 -05 5)一般规律：设正整数n分解为n=p；暧pkk,则=1121k1习题：18,21小结:课程任务；技巧性。6 .4组合等

22、式及其组合意义组合等式的证明方法(1)归纳法(2)组合意义法:借助于阐明等号两端的不同表达式实质上是同一个组合问题的方案数(殊途同归法)，或者虽是两个不同组合问题的方案数，但二者的组合方案之间存在着一一对应关系，因此等式两端必须相等，从而达到证明等式成立的目的。对于恒等式的实质揭露得更为深刻。(3)母函数法:利用无穷级数(包括有限时的多项式)证明有关组合等式。是产生和证明组合恒等式的普遍方（4）其它方法:二项式展开、反演公式等【等式1】对称关系式rn_rCn=Cn组合意义：Q,a2，an）的r组合nr组合【等式2加法公式rrr-1Cn二CnJCn1（一）组合意义：即汨2,，a0的r组合，分为两

23、类：（1）取出的元素中含有冉：组合数为Cnjo（2）不含元素四，组合数为C：。总数：Cn+Cn;注意：无第三种情形；两类情况互不重复；用加法法则。（二）例：从1,2,3,4,5中取3个的组合情况：第一类（包含元素“1”）：123,124,125,134,135,145第二类（不包含“1”）：234,235,245,345（三）路径问题：等价形式m_cmm_1CmnCmn-1Cmn-1组合意义：从（0,0）点到（m,n）点的路径数等于从（0,0）点分别到（m,n-1）点和（m1,n）点的路径数之和。m,n【等式3乘法公式krrk_rCnCk=CnCn-rn-kkrrrn-kkr苔工:CnCkCr

24、二CnCn_rCk_r组合意义(1)左端：“将n个元素分为3堆：第一堆n-k个，第二堆k-r个，则第三堆为r个”，求组合方案数。(2)右端：“将n个元素分为3堆:第三堆r个,第二堆n-k个，第一堆k-r个，求组合方案数。(3)两个组合问题等价。举例：n=20=5+7+8=7+8+5,c20c；5c8=C；0C3C5推广：n个元素分为t堆，且可以若干堆个数相等n=20=4+2+5+9=2+9+4+5,C40c28c156=C20c98c4等式4C(n+r+1,r)=C(n+i,i)i-0=C(n+r,r)+C(n+r1,r1)+C(n+r2,r2)+C(n+r3,r3)+C(n,0)r或C(n+

25、r+1,r)=ZC(n+i,n)i=0=C(n+r,n)+C(n+r1,n)+C(n+r2,n)+C(n,n)(一)组合意义：(二)说明：等式2的推广。CrrCr-1Cnr rCrl-iCr-2.1C：*：2Cr-3-2Cnr-1C r -2_ c 1 c 0Cn r2C n 1 Cn 1OlC r 一2C n r -2（三）相应的路径问题：r,n10,0等式5Vandermonde(范德蒙)恒等式rm+nrnm=ZIrii=0liJlr-iJr min(m, n)nmnmnm=+.0Ar)1Ar-1JJ人01组合意义n个相异的红球，m个相异的蓝球，选r个的组合分类统计：i个红球，ri个蓝球的

26、选法为cnc1特例：m=rr n0A0J1J1J0；=zi=0【等式6】和式公式：ZC(n,i)=2ni=0组合意义：n个相异元素选i个的组合两类元素的n可重排列组合eie2e3e4e5e6排列不不不不不不000000eie2e3e4e5比取取取取取取111111eie3e6取不取不不取101001e3e5e6【等式71n一n十n一十(.1)nn=0wm组合意义：等式变形C0c2=clc3nnnn奇组合数=偶组合数。启发：存在一ii对应关系。例：n=4奇组合aabcabdacdbcdbcd偶组合bcbdcdabacadabcd【等式8(C：2+2(C12f+n(C：2=门二组合意义：从n名先生

27、、n名太太中选出n人，其中一人担任主席，且必须为太太，求选法数。选法1:选一名太太任主席；再选n-1人。选法总数为CEEnCMi选法2：从n名太太中选k人；从此k人中选一人任主席；再从n名先生中选nk人（1kn）。cnckcn _k n二 k cn2n选法总数=.kCk2k1【等式9】设r,M都是自然数，MAr则有rM-rrM-rM-r-1r+,+,.MMM-1MM-1M-2M-rM-r-11r1MM-1r1r组合意义（概率问题）：设袋中有M个大小相同的球，其中白球r个，其余为黑球。每次摸出一个球，不放回，直至摸到白球为止。是必然事件（迟早会摸到白球），概率为1。另法：第一次摸到白球概率工。第

28、二次摸到白球MM-11,，第k次才摸到白球（k=2,3,，M-r+1）MM1MrMr1Mrk2rMM1M-k-2M-k-1【等式10】当nnm时，n-mVcmkcm=2n-mcmnnwmk/nnk巾组合意义：从n人中选出m名正式代表及若干名列席代表的选法（列席代表人数不限）。统计方法一：先选正式代表，再从n-m人中选列席代表，总的选法为Cm2n统计方法二：先选m+k人（k=0,1,，n-m），再从中选出m名正式代表，其余的k人为列席代表，有cmcm林种选n-m总数八cmkcmkk=01.5多项式系数(一)Newton二项式(1)二项展开式Newton二项式定理(n是正整数)nabn八C：arb

29、nrd0右端称为二项式(a+b)n的展开式，cr叫做二项式系数。(2)组合意义分配问题：将n个相异的球放入两个盒子，a盒放入n1=r个,b盒放入n2=n-r个，同盒的球不分次序，方案数为n!n!n1!n2!r!n-r!即arbnT项的系数为组合数c例(a+b=(a+b)(a+b)=aa+ab+ba+bb=a2+2ab+b2-3(a+b)=(a+b)(a+b)(a+b)=(aa+ab+ba+bb)(a+b)=aaa+aab+aba+abb+baa+bab+bba+bbb=a33a2b3ab2b3产生系数的根源：同一单项式中有顺序，即排列问题(球不同的分配问题)。排列问题：从两种元素中选n个的排列

30、(a选r个，b选n-r个)(二)般分配问题问题：将n个相异的球放入t个盒子，要求第1个盒子放入n1个，第2个盒子放入“个，第t个盒子放入nt个，且盒中的球无次序，求不同的分配方案数。转化：求S=%e,n2e2,，nt,ej(0+电+%=n)的全排列数RP(n,n)：仿照二项式系数RP n,n =n!n1!n2!n(三)多项式系数般多项式系数与的关系:33!y 0!0!3!33!2z3x2y2!1!0!3!2 ,+xy2 +1!2! 0!3!2x2z+2! 0!1!3!xyz 1!1!1!3xyz0)y3+3)z3x2z(x+y+z=x3+y3+z3+3x2y+3x+3x2z+6xyz3!33!

31、x3!0!0!0!3!0!【定理1.5.1设n与t均为正整数，则有,nZnn(X1+x2+xt)=ZXl1X2Xtt二0叫nt;yni=ni36-0t其中求和是在使ni=n的所有非负整数数列(”，后,nJ上i=1进行。(证)(Xi+X2+Xt)n=X1X2XtX1X2XtX1x2xt-=-V-，共n个因子连乘(1)所有项都具形式nnin2ntX1x2Xt,且ni=ni=1(2)一股项的系数：ni个因式中选取Xi,得x；*；2X；项，其系数为Cn,n1Cn-n1,n2Cnt,ntn!n-n1!nt!n1!n-n1!n2!n-n1n2!nt!0!n!nn1!n2!nt!、n1n2nt)/称n为多项

32、式系数。【叫；2nJ(四)多项式展开的项数【定理1.5.2(x1+x2+xt)n展开式的项数等于C.1,而这些项的系数之和为tn.(证)展开式的项x；1x；2xtnt1从t种元素X,X2，中取n个的n可重组合。在定理1.5.1中令x1=x2=xt=1得Ztni印i .1瓦,0=111 n(五)例【例1.5.1】求(a +b + c + d )3的展开式。(解)n = 3, t= 4,有 RC(oo3)= C(4+ 3- 1,3)=20(项)2 1 0= a3+ b3 +0；0)a2b 010 0 12)cd2|abc + 0bcdc3+ d3+3a2b + 3a2c + 3a2d +，+ 3c

33、d2 + 6abc+6abd+6acd+6bcd【例 1.5.21a1a2 a3 系数。a4 + a5 )7的展开式中，项a；a3a：a5的7!2013=4202!0!1!3!1!【例1.5.3在(2x1-3x2+5x3)6的展开式中，项X3X2X2的系数是什么？(解)令 a1 = 2x1展开a1a2，a26a3):a13a2a2的系数=1 2)6,32,=(2xi-3x2+5x3)中(2xi)(-3x2)(5x3)的系数X3x2x2的系数：623(-352=6!8(一3)25312；3!1!2!=36000【例1.5.4】求证n工(-1)kC(n,k)xk(1+x尸k=1,nA1k=0(证)

34、(证明组合等式)在二项式中取a=-x,b=1+x1=1n=(-x)+(1+x)nn=C(n,kM-x)k(1+x)n-kk=0【例1.5.51今天是星期日，再过10100天是星期几？(解)(求余数，同余运算)10100=10050=(14乂7+2严r50r50、=2+(14父7)r25r=1r等价问题：110100除以7的余数=250除以7的余数250=2243M16=4816=4(7+1)16一16(16、J=411+7r=4(mod7)-r=1rJ-100另法：10100=(7+3)=3100十1007r，3100一r=11rJ10033333=327=3(28+(T)2333333r33

35、3一3|(-1)+!128r(-1)一r=11rJ_3(-1)33=3=4(mod7)(六)问题cc18请给出多项式a-2b+3dl的展开式中a2b2c2d2和2)bc5d2两项的系数(答：22680,189/2)。1.6排列的生成算法1) 6.1序数法(1) 数的位权表示(1)十进制数：小于10r的正整数n的位权形式：r-1n=Zak10k,0ak910k=0例315=3M102+1父101+5父100(r=3)(2)推广(p进制数)r-1n=akpk,0akpk=0(3)特点：固定进制；逢p进一；十进制r位数最小为0,最大为9999=10r110r;将十进制换算为p进制数方法：除p取余法。

36、(2) 变进制表示(1)依据：n!=(n1)(n1)!+(n1)!递归：n!=(n-1)(n-1)!+(n-2)(n-2)!+(n-2)!=(n-1)(n-1)!+(n-2)(n-2)!+(n-3)(n-3)!+(n-3)!=(n-1)(n-1)!+(n-2)(n-2)!+22!+11!+1!n-1n!=kk!+1k=1n!-1=(n-1)(n1)!+(n2)(n2)!+22!+11!类似10n1=910n，+910nl+-+9101+9100结论：从0到n!1的任何整数m都可唯一地表示为n-1m=an(n1)!+an/(n2)!+az2!+a11!=Zakk!k=1其中0waiwi(i=1,

37、2,n-1)结论：m(an，anJ,a1)将十进制转换为变进制：20=3*3!+1*2!+0*1!=(310)30=1*4!+1*3!+0*2!+0*1!=(1100)100=4*4!+0*3!+2*2!+0*1!=(4020)200=(13110),8005=(143201)2) )ai的计算m=an=n-1!an4n-2!a22!a11!记n1Vmn1n-1!,n-2!,3!,电=I-2J=an1-an2-a3a2m+2!=n12=n2a1%n-1!,n-2!,4!n3=,lYl=an-+an-+“所+_33!3!3!(ma1)+3!=n2+3=0a2算法：i=1,2,n1-i 1 ni

38、i,i = 1,2, ,n -1其中.x表示不大于x的最大整数。(3)特点：变进制；从右向左，第i位逢i+1进一；n1位数最小为0,最大为：(n1)(n1)!+(n2)(n2)!+22!+11!=n!-1n!;将十进制换算为变进制数方法。(三)序数法(1)规则设n个元素为1,2,，n。特点：n元排列修n-1位变进制数。对应规则：序列回，am,，耳)排列(p)=(PiP2，Pn),其中ai为排列(p)中数i+1所在位置后面比i+1小的数的个数，即排列(p)中从数i+1开始向右统计不大于i的数的个数(2实例1)排列二数：n=4(p)=(3124)=(a3a2a1)=(020)2)数二排列(a3a2

39、a，=(111)=(p)=(2341)3)数(735233220)=排歹U35A8649712数(987654321)=排歹UA9876543214)排列3,5,7,9,A,8,6,4,2,1=数(554433221)（3）例：4元排列的生成ma3a2a1p1p2p3p4ma3a2a1p1p2p3p400001234122001423100121341320124132010132414210143230112314152112431402031241622034125021321417221342161001243183004123710121431930142138110134220310

40、4132911123412131142311012031422232043121112132412332143211.6.2字典序法（一）算法将所有n元排列按照“字典顺序”排成队。初始排列：12一n设当前排列为p）=1p1p2pn（1）求满足关系式pk_1pk的k的最大值，设为i,即i=maxk|pk.士pk）（2）求满足关系式pi_1pk的k的最大值，设为j,即j=maxk|pi-ipjp与pj互换位置得（q）=（qq2qn）（4）（q）=（qq2q_iqq小qn）中qq书qn部分的元素顺序逆转，得新排列qq2q-qnq句q。(二)例(1)设Rp2Rp4=3421:i=2,j=2,6与p2交

41、换得qi%中q4=4321,321逆转得下一排列4123。n=4的全部排列：123412431324134214231432213421432314234124132431312431423214324134123421412341324213423143124321说明：第(4)步的必要性(2)85376421=i=4,j=6=q1q2q8=85476321=8541236785412367=i=8,j=8=q1q2q8=8541237685412376=i=7,j=8=qqq8=85412673二8541263785413726=i=8,j=8=qq2q8=8541376285413762

42、=i=6,j=7=q1q2q8=85416732二854167231.6.3邻位互换生成算法初始排列：123n（当一个数上方箭头所指的一侧相邻的数比该数小时，称该数处于活动状态）一.一1，初始排列：123n设当前排列为p二p1p2pn（1）若排列（p）=（RP2Pn）中无一数处于活动状态，则停止，否则转（2）;（2）求所有处于活动状态的数中的最大者，设为k,k和它的箭头所指的一侧的相邻数互换位置，转（3）;（3）令比k大的所有数的箭头改变方向，转（1）。举例（n=4）:433334-22224111142-2-243-3-421-4-33-4-1-1-1一2一3-12一1,422.2-2-4-

43、111,143-3334广一11rLt121311-1-422-4-134-2-243-3-3411114-3333-4233-3-41r1一41324-1-142-2-2一3一1一2规律：4从一端移到另一端，共进行了3次换位，然后暂停一次，3开始活动。3和4不能动时换2,依次类推。1.7组合的生成算法【例】从6个元素1,2,3,4,5,6中取3个的组合:12312412512613413513614571461562342352362452462567345346356456规律：低位累加，逐位前移。(1)设组合GQCr满足C1C2-Cr则crwn,cr产n1,，c1nr+1即cinr+i,

44、i=1,2,r(2)当qnr+j时，令i=maxjCjn-r+j并令dk=Ck,1kidi=Ci1,dk=dk-1+1,ikr得新组合d1d2dr。若每个Cj=n-r+j,则已经达到最后一个组合，生成完毕。算法：初始组合：12r当前组合：c1c2Cr(1)若i=maxj,jn-r+j,存在，转(2),否则，停止；CiCi+1CiCi+1;(3)Cj-Cj_1+1,j=i+1,i+2,，r。输出(C1C2八转(1)。例：n=10,r=514678146791467A-146891468A-1469A147891.8应用举例【例1.8.11试确定由1,2,3,4,5这五个数字能组成多少个大于43500的五位数？（解）（有限制条件的RP”，5）的问题）。分类统计：（1）万位上数字是5:有1X54个符合要求的数；（2） 万位4,千位4,5:有1X2X53个；（3） 万、位、百位分别为4、3、5:有1X1X1X52个。总数：54+2X53+52=900（个）【例1.8.2从一2,1,0,1,2,3共6个数中不重复地选3个数作为二次函数y=ax2+bx+c的系数，使得抛物线y=ax2+bx+c的开口方向向下，共可作出多少个二次函数？（解）（不重复排列）抛物线开口向下二a4),共有多少种分法？(解)(球不同盒子相同)模型：分配问题：将n个不同的球放入n3个相同的盒子，每个盒子最少一个