组合数学 1章排列组合基础

1、第1章 组合数学基础1. 排列组合的基本计数问题2. 多项式系数的计算及其组合意义3. 排列组合算法1.1 绪 论（一） 背景起源：数学游戏幻方问题：给定自然数1, 2, , n2，将其排列成n阶方阵，要求每行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和（简称幻和）。例：3阶幻方，幻和(1239)/315。关心的问题 （1） 存在性问题：即n阶幻方是否存在？ （2） 计数问题：如果存在，对某个确定的n，这样的幻方有多少种？ （3） 构造问题：即枚举问题，亦即如何构造n阶幻方。816276357951492438奇数阶幻方的生成方法

2、：一坐上行正中央，依次斜填切莫忘，上边出格往下填，右边出格往左填，右上有数往下填，右上出格往下填。例：将2，4，6，8，10，12，14，16，18填入下列幻方：【例】（拉丁方）36名军官问题：有1，2，3，4，5，6共六个团队，从每个团队中分别选出具有A、B、C、D、E、F六种军衔的军官各一名，共36名军官。问能否把这些军官排成6×6的方阵，使每行及每列的6名军官均来自不同的团队且具有不同军衔？本问题的答案是否定的。A1 B2 C3 D4 E5 F6 A1 B2 C3 D4 E5 F6B2 C3 D4 E5 F6 A1 B3 C4 D5 E6 F1 A2C3 D4 E5 F6 A1

3、 B2 C5 D6 E1 F2 A3 B4D4 E5 F6 A1 B2 C3 D2 E3 F4 A5 B6 C1E5 F6 A1 B2 C3 D4 E4 F5 A6 B1 C2 D3F6 A1 B2 C3 D4 E5 F6【例】（计数图形染色）用3种颜色红（r）、黄（y）、蓝（b）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。求本质上不同的染色方案。举例：ryybbbrb（a）（b）形式总数：81种。实际总数（见第6章）：L24【例】（存在性）不同身高的26个人随意排成一行，那么，总能从中挑出6个人，让其出列后，他们的身高必然是由低

4、到高或由高到低排列的（见第5章）。注意：不改变原来的相对顺序。（二） 研究内容算法分类：l 第一类：数值算法。主要解决数值计算问题，如方程求根、解方程组、求积分等，其数学基础是高等数学与线性代数（解决建模问题，数值分析或称计算方法解决离散化问题，即在计算机上的求解方法问题）。l 第二类：组合算法。解决搜索、排序、组合优化等问题，其数学基础为组合数学。按所研究问题的类型，研究内容：l 组合计数理论l 组合设计l 组合矩阵论l 组合优化本课程重点：以组合计数理论为主，部分涉及其它内容。（三） 研究方法分类：第一类：从组合学基本概念、基本原理出发解题的所谓常规方法（利用容斥原理、二项式定理、P

5、43;lya 定理解计数问题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等）。第二类：通常与问题所涉及的组合学概念无关，而对多种问题均可使用。例如：（1） 数学归纳法：前提是已知问题的结果。（2） 迭代法【例】已知数列满足关系，求的解析表达式。（解）直接迭代即得：1（3） 一一对应技术原理：建立两类事物之间的一一对应关系，把一个较复杂的组合计数问题A转化成另一个容易计数的问题B，从而利用对B的计数运算达到对A的各种不同方案的计数。思路：将未解决问题的模式转化为一种已经解决的问题模式。（4） 殊途同归方法原理：从不同角度讨论计数问题，以建立组合等式。应用：组合恒等式的证明（也称组

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

7、7个街道、向北5个街道的大厦处工作（见图1.1.3），按照最短路径（即只能向东或向北走），他每次上班必须经过某12个街段，问共有多少种不同的上班路线？（解）（1）将街道抽象为等长的。（2）对应为（元素可重复的）排列问题：路径（蓝色） 排列排列 路径（红色）结论：最短路径7个x和5个y的排列（3）求解：再对应为（元素不重复的）排列问题792（4）一般情形：从（0，0）点到达（m，n）点的不同的最短路径数为 1.2 两个基本法则1. 2. 1 加法法则（一） 加法法则l 常规描述：如果完成一件事情有两个方案，而第一个方案有m种方法，第二个方案有n种方法可以实现。只要选择任何方案中的某一种方法，就可

8、以完成这件事情，并且这些方法两两互不相同。则完成这件事情共有mn种方法。l 集合描述：设有限集合A有m个元素，B有n个元素，且A与B不相交，则A与B的并共有mn个元素。l 概率角度描述：设事件A有m种产生方式，事件B有n种产生方式，则事件“A或B”有mn种产生方式。当然A与B各自所含的基本事件是互相不同的。（二） 应用【例】某班又男生18人，女生12人，从中选出一名代表参加会议，问共有多少种选法？（解）（1）两个选择方案：男生（18种选法）或女生（12种选法）。由加法法则，有181230选法。（2）设集合：A男生，B女生。该班中的学生要么属于A，要么属于B，且AB，故181230。（3）事件A

9、选男生（18种可能），事件B选女生（12种可能）。事件“A或B”选男生或女生，由加法法则，有181230种可能。【例】用一个小写英文字母或一个阿拉伯数字给一批机器编号，问总共可能编出多少种号码？（解）261036个。其中英文字母共有26个，数字09共10个。1. 2. 2 乘法法则（一） 乘法法则l 常规描述：如果完成一件事情需要两个步骤，而第一步有m种方法、第二步有n种方法去实现。则完成该件事情共有m·n种方法。l 集合描述：设有限集合A有m个元素，B有n个元素，且A与B不相交，记为一有序对。所有有序对构成的集合称为A和B的积集（或笛卡儿乘积），记作。那么，共有个元素。l 概率角度

10、描述：设离散型随机变量X有m个取值，Y有n个取值，则离散型随机向量（X，Y）有种可能的取值。（二） 应用【例】仍设某班有男生18人，女生12人，现要求从中分别选出男女生各一名代表全班参加比赛，问共有多少种选法？（解）（1）分两步挑选，先选女生（12种选法），再选男生（18种选法）。由乘法法则，有12×18216种选法。（2）设集合：A男生，B女生。由乘法法则，A×B18×12216。（3）变量X男生（18种取值），变量Y女生（12种取值）。由乘法法则，随机向量（X，Y）有18×12216种可能的值。【例】给程序模块命名，需要用3个字符，其中首字符要求用字

11、母AG或UZ，后两个要求用数字19，问最多可以给多少种程序命名？（解）首字符选法：7613种（加法法则）。总数： 13×9×91053种（数字可重复使用）（乘法法则）。【例】从A地到B地有条不同的道路，从A地到C地有条不同的道路，从B地到D地有条不同的道路，从C地到D地有条不同的道路，那么，从A地经B或C到达目的地D共有多少种不同的走法? （解）路线ABD：×种走法（乘法法则） 路线ACD：×种走法（乘法法则）总数：种走法（加法法则）2×33×4181.3 排列与组合1. 3. 1 相异元素不允许重复的排列数和组合数（一） 计算公式从

12、n个相异元素中不重复地取r个元素的排列数和组合数：（1）排列： 推导：反复利用加法法则与乘法法则（2）组合： 推导：利用组合与排列的异同（3）例：n5，r3，即元素为1，2，3，4，5 排列：134，143，314，341，413，431；254，425，组合：134，245，（4）特点：排列考虑顺序，组合不然。（二） 数学模型（1）排列问题：将r个有区别的球放入n个不同的盒子，每盒不超过一个，则总的放法数为P(n，r)。（2）组合问题：将r个无区别的球放入n个不同的盒子，每盒不超过一个，则总的放法数为C(n，r)。对应关系元素盒子位置球元素和位置编号12345A B C排列1ABC1 3 4

13、排列2CBA4 3 1排列3ACB1 4 3排列4ACB2 5 4排列5BAC4 2 5组合11 3 4组合22 4 51. 3. 2 相异元素允许重复的排列（一） 问题从n个不同元素中允许重复地选r个元素的排列，简称r元重复排列，排列数记为RP(，r)。（二） 模型将r个不相同的球放入n个有区别的盒子，每个盒子中的球数不加限制而且同盒的球不分次序。对应关系元素盒子位置球元素和位置编号12345A B C排列1ABC1 1 4排列2C BA4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4 2 5（三） 计算公式RP(，r)（四） 集合描述方式设无穷集合，从S中取r个元

14、素的排列数即为RP(，r)。不重复排列：S。1. 3. 3 不尽相异元素的全排列（一） 问题有限重复排列（或部分排列）：设（），从S中任取r个元素，求其排列数RP(n，r)。（二） 模型将r个有区别的球放入t个不同的盒子，每个盒子的容量有限，其中第i个盒子最多只能放入个球，求分配方案数。例： S2·1，4·2，1·3，3·4，2·51，1，2，2，2，2，3，4，4，4，5，5对应关系元素盒子位置球元素和位置编号12345A B C排列1ABC1 1 4排列2B C A4 3 3排列3A CB3 4 3排列4A B C2 2 2排列5BAC4

15、2 5说明：（1）极端情形：相异元素不重复的排列强调的是不重复，即盒子的容量为1；（2）极端情形：相异元素允许重复的排列强调的是无限重复，即盒子的容量无限；（3）一般情形：不尽相异元素的排列强调的是有限重复，即盒子的容量有限，介于两者之间。（三） 特例（1）1：RP(n, 1)t（2）n（全排列）例 与 与（3）t2，（4）1，即不重复的排列（5），即重复排列1. 3. 4 相异元素不允许重复的圆排列（一） 圆排列【例】把n个有标号的珠子排成一个圆圈，共有多少种不同的排法？（解）称为圆排列（相对于线排列）。条件：元素同时按同一方向旋转，绝对位置变化，相对位置未变，即元素间的相邻关系未变，视为同

16、一圆排列。结论：1个圆排列对应n个线排列。(n1)!32541 25413 54132 41325 13254【例】从n个相异元素中不重复地取r个围成圆排列，求不同的排列总数CP(n，r)。（解） CP(n，r) （二） 项链排列【例】将5个标有不同序号的珠子穿成一环，共有多少种不同的穿法？（解）称为项链排列。条件：可以翻转的圆排列。即同一项链不用剪断重穿，翻过来仍是原项链。结论：两个圆排列对应一个项链排列，故有24/212种。（a） （b）图 项链排列一般情形：从n个相异珠子中取r个的项链排列数： 允许重复的圆排列：情况复杂，参见反演公式（第四章）。1. 3. 5 相异元素允许重复的组合（一

17、） 问题设，从S中允许重复地取r个元素构成组合，称为r可重组合，其组合数记为RC(，r)。（二） 抽象记S为。例：n5，r4： 1111，1122，1345，5555（三） 计算公式设所选r个元素为：1a1a2arn令 ， i1，2，r则 1b1b 2brn(r1)反之 结论：与从nr1个相异元素中不重复地取r个元素的组合方案一一对应。 例：n5，r4分类重复组合不重复组合元素1，2，3，4，51，2，3，5，6，7，8部分组合11111234112212452245236855555678（四） 模型将r个无区别的球放入n个不同的盒子，每个盒子的球数不受限制。（五） 应用【例】不同的5个字母

18、通过通信线路被传送，每两个相邻字母之间至少插入3个空格，但要求空格的总数必须等于15，问共有多少种不同的传送方式？（解）三步求解：（1）先排列5个字母，排列数 P(5，5)5!。（2）两个字母间各插入3个空格，将12个空格均匀地放入4个间隔内，有1种方案。 b d e a（3）将余下的3个空格插入4个间隔：分析：将3个相同的球放入4个不同的盒子，盒子的容量不限。方案1： b d e a方案2：b d e a归纳：从4个相异元素中可重复地取3个元素的组合数。（4）总方案数： L5！·1·2024001. 3. 6 不尽相异元素任取r个的组合问题（一） 问题设集合（），从S中任

19、取r个，求其组合数RC(n，r)。（二） 组合数中间工具：组合问题的母函数：答案：RC(n，r)（三） 应用【例】整数360有几个正约数？（解）（1）标准素因数分解：36023×32×5（2）正约数及其条件120×30×50，22×30×50，320×3×50，520×30×5，2222×30×50，62×3×503×2，902×32×5，18022×32×5，36023×32×5结论：

20、正整数d是360的正约数d且0a3，0b2，0c1。故14不是约数，16也不是约数。（3）问题转化：求的所有组合数之和。（4）求解：构造多项式P6 (x)(1xx2x3)(1xx2)(1x)13x5x26x35x43x5x6系数求和： 135653124方法化简：求P6(1)4×3×224（5）一般规律：设正整数n分解为，则习题：18，21小结：课程任务；技巧性。1.4 组合等式及其组合意义组合等式的证明方法：（1） 归纳法（2） 组合意义法：借助于阐明等号两端的不同表达式实质上是同一个组合问题的方案数（殊途同归法），或者虽是两个不同组合问题的方案数，但二者的组合方案之间存

21、在着一一对应关系，因此等式两端必须相等，从而达到证明等式成立的目的。对于恒等式的实质揭露得更为深刻。（3） 母函数法：利用无穷级数（包括有限时的多项式）证明有关组合等式。是产生和证明组合恒等式的普遍方法。（4） 其它方法：二项式展开、反演公式等【等式1】对称关系式 组合意义：的r组合nr组合【等式2】加法公式 （一）组合意义：的r组合，分为两类：（1） 取出的元素中含有：组合数为。（2） 不含元素，组合数为。总数：注意：无第三种情形；两类情况互不重复；用加法法则。（二）例：从1，2，3，4，5中取3个的组合情况：第一类（包含元素“1”）： 123，124，125，134，135，145第二类（

22、不包含“1”）： 234，235，245，345（三）路径问题：等价形式组合意义：从（0，0）点到（m，n）点的路径数等于从（0，0）点分别到（m，n1）点和（m1，n）点的路径数之和。【等式3】乘法公式 等式变形： 组合意义 （1） 左端：“将n个元素分为3堆：第一堆个，第二堆个，则第三堆为r个”，求组合方案数。（2） 右端：“将n个元素分为3堆：第三堆r个，第二堆个，第一堆个”，求组合方案数。（3） 两个组合问题等价。举例：n20578785，推广：n个元素分为t堆，且可以若干堆个数相等n2042592945，【等式4】C(nr1，r) C(nr，r)C(nr1，r1)C(nr2，r2)C

23、(nr3，r3)C(n，0) 或 C(nr1，r) C(nr，n)C(nr1，n)C(nr2，n)C(n，n)（一）组合意义：（二）说明：等式2的推广。（三）相应的路径问题：【等式5】Vandermonde（范德蒙）恒等式, rmin(m，n) 组合意义 n个相异的红球，m个相异的蓝球，选r个的组合。分类统计：i个红球，ri个蓝球的选法为。特例：mr， rn【等式6】和式公式：组合意义：n个相异元素选i个的组合两类元素的n可重排列组合排列不不不不不不000000取取取取取取111111取不取不不取101001【等式7】组合意义：等式变形奇组合数偶组合数。启发：存在一一对应关系。例：n4奇组合a

24、abcabdacdbcdbcd偶组合bcbdcdabacadabcd【等式8】组合意义：从n名先生、n名太太中选出n人，其中一人担任主席，且必须为太太，求选法数。选法1：选一名太太任主席；再选n1人。选法总数为。选法2：从n名太太中选k人；从此k人中选一人任主席；再从n名先生中选nk人（1kn）。选法总数【等式9】设r，M都是自然数，Mr则有组合意义（概率问题）：设袋中有M个大小相同的球，其中白球r个，其余为黑球。每次摸出一个球，不放回，直至摸到白球为止。是必然事件（迟早会摸到白球），概率为1。另法：第一次摸到白球概率。第二次摸到白球，第k次才摸到白球（k2, 3, , Mr1）【等式10】当

25、nm时，组合意义：从n人中选出m名正式代表及若干名列席代表的选法（列席代表人数不限）。统计方法一：先选正式代表，再从人中选列席代表，总的选法为。统计方法二：先选mk人（k0, 1, , nm） ，再从中选出m名正式代表，其余的k人为列席代表，有种选法。总数1.5 多项式系数（一） Newton二项式(1) 二项展开式Newton二项式定理（n是正整数）右端称为二项式(ab)n的展开式，叫做二项式系数。(2) 组合意义分配问题：将n个相异的球放入两个盒子，a盒放入个，b盒放入个，同盒的球不分次序，方案数为即项的系数为组合数。例 (ab)(ab)aaabbabb(ab)(ab)(ab)(aaabb

26、abb)(ab)aaaaababaabbbaababbbabbb产生系数的根源：同一单项式中有顺序，即排列问题（球不同的分配问题）。排列问题：从两种元素中选n个的排列（a选r个，b选个）（二） 一般分配问题问题：将n个相异的球放入t个盒子，要求第1个盒子放入个，第2个盒子放入个，第t个盒子放入个，且盒中的球无次序，求不同的分配方案数。转化：求（n1n2ntn）的全排列数RP(n，n)：仿照二项式系数，记为。（三） 多项式系数一般多项式系数与的关系：x3y3z33x2y3xy23x2z6xyzx3 y3 z3x2y xy2x2zxyzx3y3z3x2yxy2x2z 【定理】设n与t均为正整数，则

27、有其中求和是在使的所有非负整数数列（n1,n2,nt）上进行。（证）（1）所有项都具形式，且（2）一般项的系数：个因式中选取，得项，其系数为称为多项式系数。（四） 多项式展开的项数【定理】展开式的项数等于，而这些项的系数之和为.（证）展开式的项从t种元素中取n个的n可重组合。在定理中令1得（五） 例【例】求的展开式。（解）n3，t4，有RC(，3)C(431，3)20（项）33336abc6abd6acd6bcd【例】的展开式中，项的系数。420【例】在的展开式中，项的系数是什么？（解）令，。l 展开：的系数中的系数l 的系数：36000【例】求证，n1（证）（证明组合等式）在二项式中取ax，

28、b1x1【例】今天是星期日，再过天是星期几？（解）（求余数，同余运算）等价问题：除以7的余数除以7的余数4（mod 7）另法：34（mod 7）（六） 问题请给出多项式的展开式中和两项的系数（答：22680，189/2）。1.6 排列的生成算法1. 6. 1 序数法（一） 数的位权表示（1）十进制数：小于的正整数n的位权形式：n， 0910例 315（r3）（2）推广（p进制数）n， 0p（3）特点：固定进制；逢p进一；十进制r位数最小为0，最大为99991；将十进制换算为p进制数方法：除p取余法。（二） 变进制表示（1）依据： n!(n1)(n1)!(n1)!递归：n!(n1)(n1)!(n

29、2)(n2)!(n2)!(n1)(n1)!(n2)(n2)!(n3)(n3)!(n3)!(n1)(n1)!(n2)(n2)!2·2!1·1!1!n!1n!1(n1)(n1)!(n2)(n2)!2·2!1·1!类似 19991019结论：从0到n!1的任何整数m都可唯一地表示为m(n1)!(n2)!2!1!其中 （1，2，n1）结论： m将十进制转换为变进制：203*3!1*2!0*1!(310)301*4!1*3!0*2!0*1!(1100)1004*4!0*3!2*2!0*1!(4020)200(13110)，8005(143201)（2）的计算记 a

30、n1an2a3a2m÷2!(m)÷3!算法：其中表示不大于x的最大整数。 （3）特点： 变进制； 从右向左，第位逢1进一；n1位数最小为0，最大为：(n1)(n1)!(n2)(n2)!2·2!1·1!n!1n!；将十进制换算为变进制数方法。（三） 序数法（1）规则设n 个元素为1，2，n。特点：n元排列n1位变进制数。对应规则：序列排列（p），其中ai为排列（p）中数i1所在位置后面比i1小的数的个数，即排列（p）中从数i1开始向右统计不大于i的数的个数（2）实例1）排列数：n4 （p）（3124）(020)2）数排列 (111) （p）（2341）3）

31、数 (7 3 5 2 3 3 2 2 0) 排列 3 5 A 8 6 4 9 7 1 2 数 (987654321) 排列A 9 8 7 6 5 4 3 2 14）排列 3, 5, 7, 9, A, 8, 6, 4, 2, 1 数 (5 5 4 4 3 3 2 2 1)（3）例：4元排列的生成ma3 a2 a1p1 p2 p3 p4ma3 a2 a1p1 p2 p3 p401234567891011000001010011020021100101110111120121123421341324231431243214124321431342234131423241121314151617181

32、9202122232002012102112202213003013103113203211423241314322431341234214123421341324231431243211. 6. 2 字典序法（一） 算法将所有n元排列按照“字典顺序”排成队。初始排列： 设当前排列为（1） 求满足关系式的k的最大值，设为i，即（2） 求满足关系式的k的最大值，设为j，即（3） 与互换位置得（4） 中部分的元素顺序逆转，得新排列。（二） 例（1）设3421：i2，j2，p1与p2交换得q1 q2 q3 q4 4321，321逆转得下一排列4123 。n4的全部排列：1234 1243 1324

33、1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321说明：第（4）步的必要性（2）85376421 i4，j6 85476321 8541236785412367 i8，j8 85412376 85412376 i7，j8 85412673 8541263785413726 i8，j8 8541376285413762 i6，j7 85416732 854167231. 6. 3 邻位互换生成算法初始排列：（当一个数上方箭头所指的一侧相邻的

34、数比该数小时，称该数处于活动状态）初始排列：设当前排列为 （1） 若排列中无一数处于活动状态，则停止，否则转（2）；（2） 求所有处于活动状态的数中的最大者，设为k，k和它的箭头所指的一侧的相邻数互换位置，转（3）;（3） 令比k大的所有数的箭头改变方向，转（1）。举例（n4）： 规律：4从一端移到另一端，共进行了3次换位，然后暂停一次，3开始活动。3和4不能动时换2，依次类推。1.7 组合的生成算法【例】从6个元素1, 2, 3, 4, 5, 6中取3个的组合：123 124 125 126 134 135 136 145 146 156 234 235 236 245 246 256 34

35、5 346 356 456规律：低位累加，逐位前移。（1）设组合c1c2cr满足 c1c2cr则 crn，cr1n1，c1nr1即 cinri，i1, 2, , r（2）当cjnrj时，令imax，并令得新组合d1d2dr 。若每个cj nrj，则已经达到最后一个组合，生成完毕。算法：初始组合： 当前组合：（1） 若imax存在，转（2），否则，停止；（2） cici1;（3） ，ji1, i2, , r。输出，转（1）。例：n10，r514678 14679 1467A 14689 1468A 1469A 147891.8 应用举例【例】试确定由1，2，3，4，5这五个数字能组成多少个大于4

36、3500的五位数？（解）（有限制条件的RP(，5)的问题）。分类统计：（1） 万位上数字是5：有1×5 4个符合要求的数；（2） 万位4，千位4，5：有1×2×53个；（3） 万、位、百位分别为4、3、5：有1×1×1×52个。总数： 542×5352900 （个）【例】从2，1，0，1，2，3共6个数中不重复地选3个数作为二次函数的系数，使得抛物线的开口方向向下，共可作出多少个二次函数？（解）（不重复排列）抛物线开口向下a0。第一步：a从2、1中选一个，有种方法；第二步：在余下的五个数中选b和c，有种方法。函数个数 40（

37、个）【例】满足的正整数解有多少组？（解）（组合问题）方法思路：长度为100的线段被分为4段，每段的长度均为正整数，记为，。例：10，35，40，15，10354015100。 问题转化：在99个空位置上放3个“”号，未放“”号的线段合成一条线段，求放法总数。首尾和两“”之间至少一段。分配模型：将3个相同的球放入99个相异的盒子，每盒最多放一个球。排列组合问题：从99个相异元素中不重复地选3个。156849（组）方法：分配模型：将100个相同的“1”放入4个不同的盒子，每个盒子至少放一个。求不同的放法数。排列组合问题：从4种相异元素中可重复地选100个，每种元素至少选一个。第一步：每个盒子先放一

38、个，共有一种放法。第二步：将余下的96个1放入，有变异一：求非负整数解（即）。用方法求解： 答：176851用方法求解：将100个相同的球放入4个不同的盒子，每个盒子的容量无限。求不同的放法数。答：176851变异二：求解。，。思想：将问题转化为变异一。原方程 变换 ，转化 （）答：解数为 166650问题：将原题用变异二的思路求解。【例】把r个相异物体放入n不同的盒子里,每个盒子允许放任意个物体,而且要考虑放入同一盒中的物体的次序,求这种分配方案有多少?特点：既不是相异元素的不重复排列，也不是简单的重复排列。思路：放一个物体增加一个隔板（盒子）。方案数 n(n1)(n2)(nr1)12345

39、n1n说明：不考虑盒中相异物体的次序，方案数为应用：A、B、C、D、E共5位同学由两个门排队进入教室，每个门每次只能同时进一人，问有多少种进法？答：2×3×4×5×6720种前门人数后门人数方法备注051×5!120×0!×5!14×1×4!120×1!×4!23×2!×3!12032×3!×2!12041×4!×1!12050×5!×0!120若不考虑次序，总数为32。问题1：设前门宽大，可以同时进2人，

40、那么又有多少种不同的进法？答：有 3×4×5×6×72520种。问题2：火车站外有100名乘客，欲从4个门排队进入候车室，问有多少种进门的排队方式？问题3：大楼共有19层，今有12人从一楼进入电梯上楼，每层都可能有人出电梯，且电梯的门同时只能容许一个人出入，问有多少种方式出电梯？【例】把元集S划分成个无序非空子集（n4），共有多少种分法？ （解）（球不同盒子相同）模型：分配问题：将n个不同的球放入n3个相同的盒子，每个盒子最少一个球求解：分三类情况： (1) 一个子集为4元集，其余子集为一元集，等于n元集的不重复的4组合数；(2) 一个子集3元，一个子集

41、2元，其余子集1元：n元集S的5组合数为，把5元集划分成一个3元子集和一个2元子集的方法有10种，由乘法法则，此类划分方法有10种；(3) 3个子集2元，其余子集1元：n元集的6组合数为，把6元子集划分成3个2元子集的方法有 属于此类的划分方法有种。总数 L【例】设是能够从集合中选出两两之差均大于r的k元子集的方案数，试求。（解）（更一般的组合问题）集合A中取k个两两之差超过r的数构成组合，设r1， 1ijk令 ， 则 1， 1ijk且 1n(k1)r结论：从A中选k个元素的方案从集合B不重复地选取k个元素的方案（B） 说明：r0，不重复组合-1，重复组合1，间隔1个选m，间隔m个选例：【例】

42、有7位科学家从事一项机密工作，他们的工作室装有电子锁，每位科学家都有打开电子锁的“钥匙”。为了安全起见，必须同时有4人在场时才能打开大门。试问该电子锁至少应具备多少个特征？每位科学家的“钥匙”至少应有多少种特征？（解）（秘密共享）分析：任意3个人在一起，至少缺一种特征，不能打开电子锁。结论1：电子锁最少特征数：C(7，3)35原因：每一组合所形成的3人小组缺少的特征必须不一样的。1ABC8ACF15AFG22BDG29CEF2ABD9ACG16BCD23BEF30CEG3ABE10ADE17BCE24BEG31CFG4ABF11ADF18BCF25BFG32DEF5ABG12ADG19BCG2

43、6CDE33DEG6ACD13AEF20BDE27CDF34DFG7ACE14AEG21BDF28CDG35EFG结论2：科学家A的“钥匙”的特征个数至少为C(6，3)20原因：A须有其余6人缺的钥匙。例：A1635；B615，2635；C25，1015，2025，3235；【例】从（0，0）点到达（m，n）点（m<n），要求中间所经过的每一个格子点（a，b）恒满足b>a，问有多少条最短路径？（解）分析：第一步必须从（0, 0）到（0, 1）。等价于从（0, 1）点到（m, n）点的路径数（前提：满足条件）。从（1, 0）到（m, n）的路径从（0, 1）到（m, n）点但经过yx

44、线上的格子点的路径 （m, n） （0, 0）对应规则：最后一次离开对角线之前对称，之后重合。结论：所求路径数(0, 1)点到（m, n）点路径数(1, 0)点到（m, n）点路径数 N (mn1)! (mn1)! （nm） 【例】n, h, r都是非负整数，并且。证明 （） 等号何时成立？（解）构造问题：在中取kr个元，有种取法。一种特殊取法：先取前k个元素；再从其余的个元素中取r个，有种。结论：后一种取法是前者的部分情况。等号成立的条件：nkr（否则总有不全含的kr元子集）。反过来，当nkr时，确实有【例】（一） 二进制串的汉明距离位二进制码， 的个数为k，记为，称为a、b码的Hammin

45、g距离。例：(0000, 0000)0，(0000, 1001)2，(0101, 1010)4（二） 性质三角不等式 （三） 检错码与纠错码检错码：奇偶校验码、汉明码、BCH码等。纠错码：汉明码、BCH码、郭帕码等。（四） 汉明码（1） 思想：如若与码a的距离r，则认为是a的错误码而予以纠正。（2） 编码的距离要求：2r1否则可构造c，使之满足r而无法纠错。反之，设任何2r1。若r，则由三角不等式知对其它码字b，有(2r1)rr1r（3） 例：r1，n8字母码字相近码a0000000010000000，01000000，00000001b1110000001100000，10100000，11

46、100001c0001110010011100，01011100，00011101可编码字符数：n8，r1，M28n8，r2，M6n10，r2，M18n12，r2，M51（五） 编码量编码集：（n位二进制码）条件：与的距离小于等于r的数有个令Uia|d(a，ai)r，每个数最多只能属于U1，U2，UM中的一个编码量： M 1.9 习题1（1）基本题：19，14，16，19，2223，29，31（2）加强题：1112，17，18，21，28（3）提高题：13，15，20，2426，30，32（4）关联题：10，271-1. 在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？（解

47、）问题相当于求在相异元素1, 3, 5, 7, 9中不重复地取1个、2个、4个元素的所有排列数，答案为520601202051-2. 比5400小并具有下列性质的正整数有多少个？（1） 每位的数字全不同； （2） 每位数字不同且不出现数字2与7。（解）（1）分类统计：一位正整数有个；两位正整数有81个；三位正整数有9×9×8648个；千位数小于5的四位数有4×9×8×72016个；千位数等于5，百位数小于4的数有4×8×7224个。由乘法法则，满足条件的数的总个数为98164820162242978（2）仿（1），总个数为7

48、4929463015011301-3. 一教室有两排，每排8个坐位，今有14名学生，问按下列不同的方式入座，各有多少种坐法？（1） 规定某5人总坐在前排，某4人总在后排，但每人具体坐位不指定；（2） 要求前排至少坐5人，后排至少坐4人。（解）（1）5人在前排就座，其坐法数为 ，4人在后排就座，其坐法数为 ，还空7个坐位，让剩下的14545个人入坐，就座方式为 种，由乘法法则，就座方式总数为28 449 792 000（2）因前排至少需坐6人，最多坐8人，后排也如此。可分成三种情况分别讨论：.前排恰好坐6人，入坐方式有种；. 前排恰好坐7人，入坐方式有种；前排恰好坐8人，入坐方式有种。各类入坐方式互相不同，由加法法则，总的入坐方式总数为误：先选6人坐前排，再选4人坐后排，剩下的4人坐入余下的6个座位。故总的入坐方式共有种。但这样计算无疑是有重复的，例如恰好选6人坐前排，其余8人全坐后排，那么上式中的