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

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

2、2，4，6，8，10，12，14，16，18 填入下列幻方：1/5143884921. 排列组合的基本计数问题2. 多项式系数的计算及其组合意义3. 排列组合算法第一章组合数学基础组合数学【例 1.1.1】（拉丁方）36 名军官问题：有 1，2，3，4，5，6 共六个团队，从每个团队中分别选出具有A、B、C、D、E、F 六种军衔的军官各一名，共 36 名军官。问能否把这些军官排成 6×6的方阵，使每行及每列的 6 名军官均来自不同的团队且具有不同军衔？本问题的是E5 F6 A1 B2 C3 D4的。F6 A1 B2 C3 D4 E5A1 B2 C3 D4 E5 F6B2 C3 D4

3、E5 F6 A1C3 D4 E5 F6 A1 B2D4 E5 F6 A1 B2 C3A1 B3 C5 D2 E4 F6B2 C4 D6 E3 F5C3 D5 E1 F4 A6D4 E6 F2 A5 B1E5 F1 A3 B6 C2F6 A2 B4 C1 D3【例 1.1.2】（计数图形染色）用 3 种颜色红（r）、黄（y）、蓝（b）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。求本质上不同的染色方案。举例：（a）（b）2/51ybrbrybb第一章组合数学基础组合数学形式总数： 34 81 种。实际总数（见第 6 章）：L 1 (3

4、4 + 32 + 2´ 3)244【例 1.1.3】（存在性）不同身高的 26 个人随意排成一行，那么，总能从中挑出 6 个人，让其出列后，他们的身高必然是由低到由高到低排列的（见第 5 章）。注意：不改变原来的相对顺序。（二） 研究内容算法分类：l 第一类：数值算法。主要解决数值计算问题，如方程求根、解方程组、求等，其数学基础是高等数学与线性代数（解决建模问题，数值分析或称计算方法解决离散化问题，即在计算机上的求解方法问题）。l 第二类：组合算法。解决搜索、排序、组合优化等问题， 其数学基础为组合数学。按所研究问题的类型，研究内容：llll组合计数理论组合设计组合矩阵论组合优化本课

5、程重点：以组合计数理论为主，部分涉及其它内容。（三） 研究方法分类：第一类：从组合学基本概念、基本原理出发解题的所谓常规方法（利用原理、二项式定理、Pólya 定理解计数问题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等）。第二类：通常与问题所涉及的组合学概念无关，而对多种问题均可使用。例如：（1） 数学归纳法：前提是已知问题的结果。（2） 迭代法3/51第一章组合数学基础组合数学= 2hn-1 + 1, ，求= 1【例】已知数列h 满足关系ìhníhh 的表nnî1。（解）直接迭代即得：hn = 2hn-1 + 1 2(2h)+ 12+

6、 2 + 11 2 hn-2n-2 2 ()+ 2 + 1 2 h+ 22 + 2 + 1+ 1232hn-3n-3M 2n-1 h + 2n-2 + 2n-3+ L+ 22 + 2 + 11 2n - 1（3） 一一对应技术原理：建立两类事物之间的一一对应关系，把一个较复杂的组合计数问题 A 转化成另一个容易计数的问题 B，从而利用对 B的计数运算达到对 A 的各种不同方案的计数。思路：将未解决问题的模式转化为一种已经解决的问题模式。（4） 殊途同归方法原理：从不同角度讨论计数问题，以建立组合等式。应用：组合恒等式的证明（也称组合意义法）。（5） 数论方法特别是利用整数的奇偶性、整除性等数论

7、性质进行分析推理的方法。组合数学用的较多的方法：（3）与（4）。【例 1.1.4】有 100 名选手参加羽毛球比赛，如果采用单循环淘汰制，问要产生冠军共需要进行多少场比赛？（解）常规思路：502512632199 场10000 名选手：5000250012506253121采用一一对应方法：每场比赛产生一个失败者，且每个失败者只能失败一次（场次失败者）。反之，要淘汰一个选手，必 须恰好经过一场比赛（失败者场次）。结论：失败者« 比赛场次。应该比赛 99 场。4/51第一章组合数学基础组合数学一般情况：单循环淘汰制，n 个选手，比赛n - 1场。【例 1.1.5】设某地的街道将城市分割

8、成矩形方格，在其住处 A(0, 0)的B(7, 5)处工7 个街道、向北 5 个街道的作（见图 1.1.3），按照最短路径（即只能或向北走），他每次上班必须经过某 12 个街段，问共有多少种不同的上班路线？（解）（1）将街道抽象为等长的。B(7, 5)A(0, 0)（2）对应为（元素可重复的）排列问题：） 排列路径（排列 路径（红色） 结论：最短路径« 7 个x 和 5 个y 的排列（3）求解：再对应为（元素不重复的）排列问题12!N = C 5C 5 7927+55!×7!12（4）一般情形：从（0, 0）点到达（m, n）点的不同的最短路径数为N = Cm= Cnm +

9、 nm + n1.2 两个1. 2. 1加法法则（一） 加法法则l 常规描述：如果完成一件事情有两个方案，而第一个方案有 m 种方法，第二个方案有 n 种方法可以实现。只要选则择任何方案中的某法，就可以完成这件事情，并且这些方法两两互不相同。则完成这件事情共有 mn 种方法。5/51第一章组合数学基础组合数学l集合描述：设有限集合 A 有 m 个元素，B 有 n 个元素， 且 A 与 B 不相交，则 A 与 B 的并共有 mn 个元素。lA 有 m 种产生方式，B 有 n概率角度描述：设种产生方式，则“A 或 B”有 mn 种产生方式。当然 A 与 B 各自所含的基本（二） 应用是互相不同的。

10、【例 1.2.1】某班又男生 18 人，女生 12 人，从中选出一名代表参加会议，问共有多少种选法？（解）（1）两个选择方案：男生（18 种选法）或女生（12种选法）。由加法法则，有 181230 选法。（2）设集合：A男生，B女生。该班中的学生要么属于 A，要么属于 B，且 ABf ，故A + B 181230。（3） 种可能）。A选男生（18 种可能），B选女生（12“A 或 B”选男生或女生，由加法法则，有181230 种可能。【例 1.2.2】用一个小写英文字母或一个器编号，问总共可能编出多少种号码？（解）261036 个。其中英文字母共有 26 个，数字 09 共 10 个。1. 2

11、. 2乘法法则（一） 乘法法则l 常规描述：如果完成一件事情需要两个步骤，而第一数字给一批机m 种方法、第二有m × n 种方法。n 种方法去实现。则完成该件事情共l 集合描述：设有限集合 A 有 m 个元素，B 有 n 个元素， 且 A 与 B 不相交， a Î A, b Î B ，记(a, b)为一有序对。所有有序对的集合称为 A 和 B 的积集（或笛卡儿乘积），记作 A´ B 。那么， A ´ B 共有m × n 个元素。A ´ B = (a, b) a Î A, b Î B6/51第一章组合数学基

12、础组合数学l 概率角度描述：设离散型随量 X 有 m 个取值，Y 有 n个取值，则离散型随机向量(X , Y )有m × n 种可能的取值。（二） 应用【例 1.2.3】仍设某班有男生 18 人，女生 12 人，现要求从中分别选出男女生各一名代表全班参加比赛，问共有多少种选法？（解）（1）分两步挑选，先选女生（12 种选法），再选男生（18种选法）。由乘法法则，有 12×18216 种选法。（2） 设集合：A男生，B女生。由乘法法则， A ´ B18×12216。（3） 变量 X男生（18 种取值），变量 Y女生（12 种取值）。由乘法法则，随机向量（X

13、，Y）有 18×12216 种可能的值。【例 1.2.4】给程序模块命名，需要用 3 个字符，其中首字符要求用字母 AG 或 UZ，后两个要求用数字 19，问最多可以给多少种程序命名？（解）首字符选法：7613 种（加法法则）。总数： 13×9×91053 种（数字可重复使用）（乘法法则）。【例 1.2.5】从 A 地到 B 地有n1 条不同的道路，从 A 地到 C 地有n2 条不同的道路，从 B 地到 D 地有m1 条不同的道路，从 C地到 D 地有m2 条不同的道路，那么，从 A 地经 B 或 C 到达目的地 D 共有多少种不同的走法?（解）路线 A 

14、4; B ® D： n1 × m1 种走法（）路线 A ® C ® D： n2 × m2 种走法（）总数： n1 m1 n2 m2 种走法（加法法则）7/51乘法法则乘法法则第一章组合数学基础组合数学2×33×418排列与组合1.31. 3. 1相异元素不（一） 计算公式重复的排列数和组合数从 n 个相异元素中不重复地取 r 个元素的排列数和组合数：n!= P(n, r ) = n(n - 1)L(n - r + 1) = (Pr（1）排列：n - r )!n推导：反复利用加法法则与乘法法则æ nöPrn

15、!= C(n, r ) = ç÷ =C r n r!（2）组合：()nn - rè r ø!r!推导：利用组合与排列的异同（3）例：n5，r3，即元素为 1，2，3，4，5排列：134，143，314，341，413，431；254，425， 组合：134，245，（4）特点：排列考虑顺序，组合不然。（二） 数学模型（1）排列问题：将 r 个有区别的球放入 n 个不同的盒子，每盒不超过一个，则总的放法数为P r 。n（2）组合问题：将 r 个无区别的球放入 n 个不同的盒子，每盒不超过一个，则总的放法数为C r 。n8/51第一章组合数学基础组合数学1.

16、 3. 2相异元素（一） 问题从 n 个不同元素中重复的排列重复地选 r 个元素的排列，简称 r 元重复排列，排列数记为 RP(, r)。（二） 模型将 r 个不相同的球放入 n 个有区别的盒子，每个盒子中的球数不加限制而且同盒的球不分次序。（三） 计算公式RP(, r) nr（四） 集合描述方式设无穷集合S = ¥ × e , ¥ × e ,L, ¥ × e，从 S 中取 r 个元素12n的排列数即为 RP(, r)。不重复排列：S1× e , 1× e , L, 1× e e , e , L, e 。

17、12n12n9/51对应关系元素« 盒子位置« 球元素和位置编号12345A B C排列 1ABC1 1 4排列 2C BA4 3 3排列 3A CB3 4 3排列 4A B C2 2 2排列 5BAC4 2 5对应关系元素« 盒子位置« 球元素和位置编号12345A B C排列 1ABC1 3 4排列 2CBA4 3 1排列 3ACB1 4 3排列 4ACB2 5 4排列 5BAC4 2 5组合 11 3 4组合 22 4 5第一章组合数学基础组合数学1. 3. 3不尽相异元素的列（一） 问题有限重复排列（部分排列）：设S = n1 × e1

18、 , n2 × e2 , L, nt × et （ n1 + n2 + L+ nt = n ），从 S 中RP(n, r )。（二） 模型r 个元素，求其排列数将 r 个有区别的球放入 t 个不同的盒子，每个盒子的容量有限，其中第 i 个盒子最多只能放入ni 个球，求分配方案数。例： S2·1，4·2，1·3，3·4，2·51, 1, 2, 2, 2, 2, 3, 4, 4, 4, 5, 5说明：（1）情形：相异元素不重复的排列强调的是不重复，即盒子的容量为 1；（2情形：相异元素重复的排列强调的是无限重复，即盒子的容量无限

19、；（3）一般情形：不尽相异元素的排列强调的是有限重复，即盒子的容量有限，介于两者之间。（三） 特例（1） r 1：RP(n, 1)t（2） r n（列）10/51对应关系元素« 盒子位置« 球元素和位置编号12345A B C排列 1ABC1 1 4排列 2B CA4 3 3排列 3A CB3 4 3排列 4A B C2 2 2排列 5BAC4 2 5第一章组合数学基础组合数学n!RP (n, n) =n1!n2!Lnt !例a1a2 a3 b1b2 c1c2 与a1a2a3a1b2b1c1c2a1b1a2 b2 c1a3 c2 与a2 b1a1b2 c1a3 c2

20、0; n ön!（3）t2， RP (n, n) = ç÷n1!n2 !è n1 ø（4） ni 1，即不重复的排列（5） ni = ¥ ，即重复排列1. 3. 4相异元素不（一） 圆排列重复的圆排列【例 1.3.1】把 n 个有标号的珠子排成一个圆圈，共有多少种不同的排法？（解）称为圆排列（相对于线排列）。条件：元素同时按同一方向旋转，绝对位置变化，相对位置未变，即元素间的相邻关系未变，视为同一圆排列。结论：1 个圆排列对应 n 个线排列。CP(n, n) = P(n, n) (n1)!n3254125413541324132513

21、254【例 1.3.2】从 n 个相异元素中不重复地取 r 个围成圆排列，求不同的排列总数 CP(n, r)。n!P rCP(n, r)（解）nrr n - r )!(11/51第一章组合数学基础组合数学（二） 项链排列【例 1.3.3】将 5 个标有不同序号的珠子穿成一环，共有多少种不同的穿法？（解）称为项链排列。条件：可以翻转的圆排列。即同一项链不用剪断重穿，翻过来仍是原项链。结论：两个圆排列对应一个项链排列，故有 24/212 种。（a）（b）图 1.3.1项链排列一般情形：从 n 个相异珠子中取 r 个的项链排列数：P rn! n 2r2r(n - r )!重复的圆排列：情况复杂，参见

22、反演公式（第四章）。1. 3. 5相异元素（一） 问题重复的组合设S = ¥ × e, L, ¥ × e ，从 S 中, ¥ × e重复地取 r 个12n元素组合，称为 r 可重组合，其组合数记为 RC(, r)。（二） 抽象记S 为S = ¥ × 1, ¥ × 2, L, ¥ × n 。例：n5，r4：（三） 计算公式1111，1122，1345，555512/51第一章组合数学基础组合数学设所选 r 个元素为：1a1a2arnbi = ai + (i - 1)， i1，2

23、，r1b1b 2brn(r1)令则ai = bi - (i - 1)反之结论：与从 nr1 个相异元素中不重复地取 r 个元素的组合方案一一对应。 RC (¥, r ) = C (n + r - 1, r ) = (n + r - 1)!r!(n - 1)!例： n5，r4（四） 模型将 r 个无区别的球放入 n 个不同的盒子，每个盒子的球数不受限制。（五） 应用【例 1.3.4】不同的 5 个字母通过通信线路被传送，每两个相邻字母之间至少3 个空格，但要求空格的总数必须等于 15，问共有多少种不同的传送方式？（解）三步求解：（1）先排列 5 个字母，排列数 P(5, 5)5!。（2

24、）两个字母间各4 个间隔内，有 1 种方案。3 个空格，将 12 个空格均匀地放入c b d e a（3）将余下的 3 个空格4 个间隔：分析：将 3 个相同的球放入 4 个不同的盒子，盒子的容量不限。方案 1： c b d e a方案 2： c b d e a13/51分类重复组合不重复组合元素1, 2, 3, 4, 51, 2, 3, 4, 5, 6, 7, 8部分组合11111234112212452245236855555678第一章组合数学基础组合数学归纳：从 4RC(个相异元素中可重复地取 3 个元素的组合数¥, 3) = C= 20 。34+ 3-1（4）总方案数： L

25、5！·1. 3. 6不尽相异元素1·202400r 个的组合问题（一） 问题设集合S = n1 × e1 , n2 × e2 , L,nt × et （ n1 + n2 + L + nt= n ），从 S 中r 个，求其组合数 RC(n, r)。（二） 组合数中间工具：组合问题的母函数：ni()nttÕååÕxrj1 +nar =0x iri =1 j = 0i =1：RC(n, r) ar（三） 应用【例 1.3.5】整数 360 有几个正约数？（解）（1）标准素因数分解：36023×32&#

26、215;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结论：正整数 d 是 360 的正约数Û d 2a3b5c 且 0a 3，0b2，0c1。故 142×7 不是约数，16 24 也不是约数。（3） 问题转化：求S = 3×

27、; 2, 2× 3, 1× 5的所有组合数之和。（4） 求解：构造多项式P6 (x)(1xx2x3)(1xx2)(1x)13x5x26x35x43x5x6系数求和： t = å RC (6, i )135653124i=0方法化简：求 P6(1)å RC (6, i )4×3×224i =014/5166第一章组合数学基础组合数学aaa（5）一般规律：设正整数 n 分解为n = ppL p，则12k12kt = (a1+1)L(a 2+1)(a k+1)习题：18，21小结：课程任务；技巧性。1.4组合等式及其组合意义组合等式的证明方

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

29、a1 ,a2 ,L,an 的 r 组合，分为两类：（1） 取出的元素中含有a ：组合数为Cr-1 。n-11（2） 不含元素a ，组合数为Cr。n-11+ Cr -1总数：Crn-1n-1注意：无第三种情形；两类情况互不重复；用加法法则。（二）例：从1，2，3，4，5中取 3 个的组合情况：15/51第一章组合数学基础组合数学第一类（包含元素“1”）：第二类（不包含“1”）：123，124，125，134，135，145234，235，245，345（三）路径问题：等价形式+ Cm -1Cm= Cmm + nm + n-1m + n-1组合意义：从（0，0）点到（m，n）点的路径数等于从（0，

30、0）点分别到（m，n1）点和（m1，n）点的路径数之和。(m, n)(0, 0)【等式 3】乘法公式CkCr = CrCk - rnn- rnkCn- kCk - rCr = CrCn- kCk - r等式变形：组合意义nn- rk - rnkr（1） 左端：“将 n 个元素分为 3 堆：第一堆n - k 个，第二堆k - r 个，则第三堆为 r 个”，求组合方案数。（2） 右端：“将 n 个元素分为 3 堆：第三堆 r 个，第二堆n - k个，第一堆k - r 个”，求组合方案数。（3） 两个组合问题等价。举例：n20578785，C 5 C 7 C 8 C 7 C 8 C 520 15 8

31、20 13 5推广：n 个元素分为 t 堆，且可以若干堆个数相等n2042592945，C 4 C 2 C 5 C 2 C 9 C 420 18 1620 18 9rn + r + 1å+ Cr -1+ Cr - 2Cr+ L + C0【等式 4】Cr=Cin + in+ rn+ r -1n+ r - 2ni = 0rn + r + 1å=CCn+ Cn+ Cn+ L + CnCrn或n + in+ rn+ r -1n+ r - 2ni = 0（一）组合意义：16/51第一章组合数学基础组合数学（二）说明：等式 2 的推广。+ Cr-1 CrCrn+rn+rr -n+r +

32、1+ ()+ Cr -2 Cr1Cn+rn+r -1n+r -1+ ()+ Cr -1r -2+ Cr -3 CrCn+rn+r -1n+r -2n+r -2(+ C 0)+ Cr -1+ Cr -2 Cr+ L + C1n+rn+r -1n+r -2n+1n+1+ Cr -1+ Cr -2 Cr+ L + C 1+ C 0n+rn+r -1n+r -2n+1n（三）相应的路径问题：(r, n + 1)(0, 0)【等式 5】Vandermonde（蒙）恒等式æ m + nöræ nöæömåçè

33、7; ç÷ç÷øir - irøi =0 èmøèæ nöæ m öæ nöæöæ nöæ m öç÷ç÷ + ç÷ç÷ + L + ç÷ç÷ ,rmin(m，n)è 1 øè r - 1ø0rè r ø

34、32; 0 øèøèø组合意义 n 个相异的红球，m 个相异的蓝球，选 r 个的组合。分类统计：i 个红球，ri 个蓝球的选法为Ci Cr-i 。nm特例：mræ n + r öæ nöæ r öæ nöæöæ nöæ r örçè÷ ç÷ç÷ + ç÷ç÷ + L + ç÷&#

35、231;÷ ，rnè 1 øè r - 1ørøè 0 øè r øè r øè 0ø17/51第一章组合数学基础组合数学æ nöæ r öæ nöæ r öæ nöæ r öç÷ç÷ + ç÷ç÷ + L + ç÷ç÷

36、è 0 øè 0øè 1 øè 1øè r øè r øræ nöæ r öåç÷ç÷iii =0 èøèøn【等式 6】和式公式： åC(n, i ) = 2n组合意义：n 个相异元素选 i 个的组合« 两类元素的 n 可重排列i =0æ n öæ n öæ n ön

37、 æ n ö÷ - ç÷ + ç÷ - L + (- 1) ç÷ = 0【等式 7】çè 0 øè 1 øè 2 øè n ø组合意义：等式变形+ C 2 + L = C1 + C 3 + LC 0nnnn奇组合数偶组合数。启发：存在一一对应关系。例：n4()()()222n= nCn-11n+ 22n+ L +、nCCnC【等式 8】2n-1n组合意义：从 n中选出 n 人，其中一人担，且必须为太太，求选法数。选法

38、 1：选一；再选 n1 人。选法总数为C1Cn-1 = nC n-1。n2n-12n-1选法 2：从 n中选 k 人；从此 k 人中选一人18/51奇组合aabcabdacdbcdbcd偶组合bcbdcdabacadabcd组合e1e2e3e4e5e6排列不不不不不不000000e1 e2 e3 e4 e5 e6取取取取取取111111e1 e3 e6取不取不不取101001e3 e5 e6第一章组合数学基础组合数学席；再从 n中选 nk 人（1kn）。()CkC1 Cn-k= kk 2Cnknn()nåk 2选法总数k Cnk =1【等式 9】设 r，M 都是自然数，Mr 则有r

39、+ M - r ×r+ M - r × M - r - 1 ×rMMM - 1MM - 1M - 2+ L + M - r × M - r - 1L 1× r= 1M - 1r + 1 rM组合意义（概率问题）：设袋中有 M 个大小相同的球，其中r 个，其余为黑球。每次摸出一个球，不放回，直至摸到白球为止。是必然（迟早会摸到），概率为 1。r另法： 第一次摸到 概率。 第二次摸到MM - r ×r,LL，第 k 次才摸到k2, 3, , Mr1）MM - 1M - r × M - r - 1 ×L× M

40、- r - (k - 2) ×rM - (k - 2)M - (k - 1)M - 1M【等式 10】当 nm 时，n-må nm+km= 2n-m× CmCCm+knk=0组合意义：从 n 人中选出 m 名正式代表及若干名列席代表的选法（列席代表人数不限）。统计方法一：先选正式代表，再从n - m 人中选列席代表，2n-m 。总的选法为C mn统计方法二：先选 mk 人（k0, 1, , nm） ，再从中选出 m 名正式代表，其余的 k 人为列席代表，有Cm+kCm种选m+kn法。n-måk =0m+ kmm+ kCC总数n19/51第一章组合数学基础

41、组合数学1.5 多项式系数（一） Newton 二项式(1) 二项展开式Newton 二项式定理（n 是正整数）n(a + b)n =C a bår r n-rnr =0右端称为二项式(ab)n 的展开式，C r 叫做二项式系数。n(2) 组合意义分配问题：将 n 个相异的球放入两个盒子，a 盒放入n1 = r 个，b 盒放入n2 = n - r 个，同盒的球不分次序，方案数为n!n! r!×(n - r )!n1 !×n2 !rn-r即a b项的系数为组合数C 。rn(a + b)2 (ab)(ab)aaabbabb a 2 + 2ab + b2例(a + b)

42、3 (ab)(ab)(ab)(aaabbabb)(ab)aaaaababaabbbaababbbabbb a3 + 3a2b + 3ab2 + b3产生系数的根源：同一单项式中有顺序，即排列问题（球不同的分配问题）。排列问题：从两种元素中选 n 个的排列（a 选r 个，b 选n - r个）（二） 一般分配问题问题：将 n 个相异的球放入 t 个盒子，要求第 1 个盒子放入n1个，第 2 个盒子放入n2 个，第 t 个盒子放入nt 个，且盒中的球无次序，求不同的分配方案数。转化：求S = n × e , n × e ,L, n × e （ n + n + L + n

43、 = n ）1122列数 RP(n，n)：RP(n, n) =tt12t的n!n1!n2 !Lnt !æ n öænö仿照二项式系数ç÷ ，记为ç÷ 。è r øè n1n2 Lnt ø20/51第一章组合数学基础组合数学（三） 多项式系数æönç÷一般多项式系数与的关系：n n Lnè 1 2t ø(x + y + z)3 x3y3z33x2y3xy23x2z6xyz3!3!3!3!x3y3z33!x2y3!

44、15;0!×0!0!×3!×0!0!×0!×3!2!×1!×0!3!3!xy2x2zxyz1!×2!×0!32!×0!×1!1!×1!×1!3æöæöæ33öç÷ x ç÷ y ç÷ z333è 300ø3è 00ø32è 003ø30æöæö

45、30;öç÷ x yç÷ xy ç÷ x z222è 210øè10øè 21øæö3ç÷ xyzè 111ø【定理 1.5.1】设n 与t 均为正整数，则有ænö(å+ L +ç÷nn L212121Lnnnè21t øtåi = nni=1(ni ³0)t其中求和是在使ånii =1进行。=n 的所有非负

46、整数数列（n1,n2,nt）上（证） ()nt(t4)(具形式t )L(t )443共n个因子连乘（1）所有n，且å n= nn2n1L21ii =1nt 项，（2）一般项的系数： n 个因式中选取 x ，得tii其系数为)×, n )L)112t21/51第一章组合数学基础组合数学(n - n1 )!n!nt !×L(n - n )! n2 !×(n - n1 - n2 )!nt !×0!×n !11ænön!ç÷n n Lnn !n !Ln !è 1 2t ø12t

47、30;nö称ç÷为多项式系数。è n1n2 Lnt ø（四） 多项式展开的项数【定理 1.5.2】(+ L+展开式的项数等于C n，21t + n-1而这些项的系数之和为t n .（证）展开式的项中取 n 个的 n 可重组合。«从t 种元素n2n1LL,121=21= L =在定理 1.5.1 中令1 得æönåç÷ (1 + 1 + L+ 1)n = t nè n1n2 Lnt øtå ni =n(ni ³0)（五） 例i =1【例 1.5.1

48、】求(a + b + c + d )3 的展开式。（解）n3，t4，有 RC(, 3)C 320（项）4+ 3-1(a + b + c + d )3æöæö33çè÷a 0çè÷b 033300030øø3æöæö3çè 2÷a b ç÷cd22100øè 0012øæöæö33çè1÷a

49、bc ç÷bcd110øè 0111ø a 3 b3 c 3 d 3 3 a 2b 3 a2c 3 a 2d 3 cd 2 6abc6abd6acd6bcd【例 1.5.2】(a + a + a + a + a)723的展开式中，项a a a a 的123451 3 4 522/51第一章组合数学基础组合数学系数。æ71öçè 2【例 1.5.3】在(÷ =4202!×0!031ø+-531的展开式中，项系数是什么？（解）令a1 = 2 x1 ， a2 = -3 x2 ， a

50、3 = 5 x3 。l 展开(a + a + a )6 ：123æ61ö32ç÷2a aa 的系数ç12 33èø)3()-(5)中(+-5系数：的系数131læ6ö6!÷2 (- 3)5× 8 × (- 3)× 25çè 3323!×1!×2!12ø36000【例 1.5.4】求证nå(- 1)k C(n, k )xk，n1k =0（证）（证明组合等式）在二项式中取a = - x ， b = 1 + x1

51、1n (- x)+ (1 + x)n åC(n, k )(- x)k (1 +k = 0n日，再过10100 天是【例 1.5.5】今天是几？（解）（求余数，同余运算）10100 10050 (14´ 7 + 2)50050ö÷(14´ 7)ø 2+50rr =1 è等价问题：23/5110100 除以 7 的余数 250 除以 7 的余数第一章组合数学基础250 22+3´16 4 × 816 4(7 + 1)16组合数学éæ16ör ù16 4ê1 +

52、 åç÷7 ú 4（mod 7）rr =1 èøëûæ100rö100另法：10100 (7 + 3)100 å3+ç÷7 ×100rr =1 èø3100 3 × 2733 3(28 + (- 1)33é(æ 33333ê - 1+ åç33rër =1 è3(- 1)33 34（mod 7）（六） 问题ö8æc请给出多项式ç

53、 a - 2b + 3d ÷ 的展开式中a 2b2c 2d 2 和è2øbc5d 2 两项的系数（答：22680, 189/2）。1.61. 6. 1序数法（一） 数的位权表示（1）十进制数：小于10r 的正整数 n 的位权形式：r -1排列的生成算法n = åa 10k ， 0 a 910kkk = 0例 315 3 ´ 102 + 1´ 101 + 5 ´ 100 （r3）（2）推广（p 进制数）r -1n = å a pk ， 0 a pkkk = 0（3）特点：固定进制；逢 p 进一；十进制r 位数最小为0，最大为 999910r 110r ；将十进制换算为p 进制数方法：除 p 取（二） 变进制表示。（1）依据：n!(n1)(n1)!(n1)!递归：n!(n1)(n1)!(n2)(n2)!(n2)!24/51第一章组合数学基础组合数学(n1)(n1)!(n2)