《组合数学》教案 1章（排列组合基础）

《组合数学》 第一章 组合数学基础

第1章 组合数学基础

1. 排列组合的基本计数问题 2. 多项式系数的计算及其组合意义 3. 排列组合算法 1.1 绪 论

（一） 背景

起源：数学游戏

幻方问题：给定自然数1, 2, …, n2，将其排列成n阶方阵，要求每

行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和（简称幻和）。

例：3阶幻方，幻和＝(1＋2＋3＋?＋9)/3＝15。

关心的问题 存在性问题：即n阶幻方是否存在？

计数问题：如果存在，对某个确定的n，这样的幻方有多少种？ 构造问题：即枚举问题，亦即如何构造n阶幻方。

8 3 4 1 5 9 6 7 2 2 9 4 7 5 3 6 1 8 奇数阶幻方的生成方法：

一坐上行正中央，依次斜填切莫忘， 上边出格往下填，右边出格往左填， 右上有数往下填，右上出格往下填。

例：将2，4，6，8，10，12，14，16，18填入下列幻方：

1/51 姜建国

《组合数学》 第一章 组合数学基础

【例1.1.1】（拉丁方）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 F6 B2 C3 D4 E5 F6 A1 B3 C4 D5 E6 F1 A2 C3 D4 E5 F6 A1 B2 C5 D6 E1 F2 A3 B4 D4 E5 F6 A1 B2 C3 D2 E3 F4 A5 B6 C1 E5 F6 A1 B2 C3 D4 E4 F5 A6 B1 C2 D3 F6 A1 B2 C3 D4 E5 F6

【例1.1.2】（计数——图形染色）用3种颜色红（r）、黄（y）、蓝（b）涂染平面正方形的四个顶点，若某种染色方案在正方形旋转某个角度后，与另一个方案重合，则认为这两个方案是相同的。求本质上不同的染色方案。

举例：

r y y b b b （a） r b （b） 2/51 姜建国

《组合数学》 第一章 组合数学基础

形式总数：34＝81种。 实际总数（见第6章）：L＝

14?3?32?2?3?＝24 4【例1.1.3】（存在性）不同身高的26个人随意排成一行，那么，总能从中挑出6个人，让其出列后，他们的身高必然是由低到高或由高到低排列的（见第5章）。

注意：不改变原来的相对顺序。

（二） 研究内容

算法分类： ? 第一类：数值算法。主要解决数值计算问题，如方程求根、解方程组、求积分等，其数学基础是《高等数学》与《线性代数》（解决建模问题，《数值分析》或称《计算方法》解决离散化问题，即在计算机上的求解方法问题）。

? 第二类：组合算法。解决搜索、排序、组合优化等问题，其数学基础为《组合数学》。 按所研究问题的类型，研究内容： ? 组合计数理论 ? 组合设计 ? 组合矩阵论 ? 组合优化

本课程重点：以组合计数理论为主，部分涉及其它内容。

（三） 研究方法

分类：

第一类：从组合学基本概念、基本原理出发解题的所谓常规方法（利用容斥原理、二项式定理、Pólya 定理解计数问题；解递推关系的特征根方法、母函数方法；解存在性问题的抽屉原理等）。

第二类：通常与问题所涉及的组合学概念无关，而对多种问题均可使用。例如：

（1） 数学归纳法：前提是已知问题的结果。 （2） 迭代法

?hn?2hn?1?1,【例】已知数列?hn?满足关系?，求hn的解析表

?h1?13/51 姜建国

《组合数学》 第一章 组合数学基础

达式。

（解）直接迭代即得：

hn?2hn?1?1

＝2?2hn?2?1?＋1＝22hn?2?2?1 ＝22?2hn?3?1??2?1＝23hn?3?22?2?1

?

＝2n?1h1?2n?2?2n?3???22?2?1

＝2n?1

（3） 一一对应技术 原理：建立两类事物之间的一一对应关系，把一个较复杂的组合计数问题A转化成另一个容易计数的问题B，从而利用对B的计数运算达到对A的各种不同方案的计数。

思路：将未解决问题的模式转化为一种已经解决的问题模式。

（4） 殊途同归方法

原理：从不同角度讨论计数问题，以建立组合等式。 应用：组合恒等式的证明（也称组合意义法）。 （5） 数论方法

特别是利用整数的奇偶性、整除性等数论性质进行分析推理的方法。

组合数学用的较多的方法：（3）与（4）。 【例1.1.4】有100名选手参加羽毛球比赛，如果采用单循环淘汰制，问要产生冠军共需要进行多少场比赛？

（解）常规思路：50＋25＋12＋6＋3＋2＋1＝99场 10000名选手：5000＋2500＋1250＋625＋312＋?＋1 采用一一对应方法：每场比赛产生一个失败者，且每个失败者只能失败一次（场次→失败者）。反之，要淘汰一个选手，必须恰好经过一场比赛（失败者→场次）。

结论：失败者?比赛场次。 应该比赛99场。

一般情况：单循环淘汰制，n个选手，比赛n－1场。 【例1.1.5】设某地的街道将城市分割成矩形方格，某人在其

4/51 姜建国

《组合数学》 第一章 组合数学基础

住处A?0,0?的向东7个街道、向北5个街道的大厦B?7,5?处工作（见图1.1.3），按照最短路径（即只能向东或向北走），他每次上班必须经过某12个街段，问共有多少种不同的上班路线？

（解）（1）将街道抽象为等长的。

B?7,5?

A?0,0? （2）对应为（元素可重复的）排列问题：

路径（蓝色）→ 排列ｘｙｙｘｘｙｙｘｘｘｘｙ 排列ｙｘｘｙｙｙｙｘｘｘｘｘ → 路径（红色） 结论：最短路径?7个x和5个y的排列

（3）求解：再对应为（元素不重复的）排列问题

12!55C＝C7＝N?12＝792 ?55!?7!（4）一般情形：从（0，0）点到达（m，n）点的不同的最短路径数为

mnN?Cm?n?Cm?n

1.2 两个基本法则

1. 2. 1 加法法则

（一） 加法法则

? 常规描述：如果完成一件事情有两个方案，而第一个方案

有m种方法，第二个方案有n种方法可以实现。只要选择任何方案中的某一种方法，就可以完成这件事情，并且这些方法两两互不相同。则完成这件事情共有m＋n种方法。

? 集合描述：设有限集合A有m个元素，B有n个元素，且A与B不相交，则A与B的并共有m＋n个元素。 ? 概率角度描述：设事件A有m种产生方式，事件B有n

5/51 姜建国

《组合数学》 第一章 组合数学基础

n!

n1!n2!?nt!例 a1a2a3b1b2c1c2与a1a2a3a1b2b1c1c2 a1b1a2b2c1a3c2与a2b1a1b2c1a3c2

RP?n,n??（3）t＝2，RP?n,n???n?n!? ????n1!n2!?n1?（4）ni＝1，即不重复的排列 （5）ni??，即重复排列

1. 3. 4 相异元素不允许重复的圆排列

（一） 圆排列

【例1.3.1】把n个有标号的珠子排成一个圆圈，共有多少种

不同的排法？

（解）称为圆排列（相对于线排列）。

条件：元素同时按同一方向旋转，绝对位置变化，相对位置未变，即元素间的相邻关系未变，视为同一圆排列。

结论：1个圆排列对应n个线排列。

P?n,n?＝(n－1)! CP?n,n??n32541 25413 54132 41325 13254

【例1.3.2】从n个相异元素中不重复地取r个围成圆排列，求不同的排列总数CP(n，r)。

n!Pnr（解） CP(n，r)＝ ＝

r?n?r?!r（二） 项链排列

11/51 姜建国

《组合数学》 第一章 组合数学基础

【例1.3.3】将5个标有不同序号的珠子穿成一环，共有多少种不同的穿法？

（解）称为项链排列。

条件：可以翻转的圆排列。即同一项链不用剪断重穿，翻过来仍是原项链。

结论：两个圆排列对应一个项链排列，故有24/2＝12种。

（a） （b）

图1.3.1 项链排列

一般情形：从n个相异珠子中取r个的项链排列数：

Pnrn! ＝ 2r2r?n?r?!

允许重复的圆排列：情况复杂，参见反演公式（第四章）。 1. 3. 5 相异元素允许重复的组合

（一） 问题

设S????e1,??e2,?,??en?，从S中允许重复地取r个

元素构成组合，称为r可重组合，其组合数记为RC(∞，r)。

（二） 抽象

记S为S????1,??2,?,??n?。 例：n＝5，r＝4： 1111，1122，1345，5555

（三） 计算公式

设所选r个元素为：1≤a1≤a2≤?≤ar≤n 令 bi?ai??i?1?， i＝1，2，?，r

12/51 姜建国

《组合数学》 第一章 组合数学基础

则 1≤b1＜b 2＜?＜br≤n＋(r－1) 反之 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，5 1111 部分组合 1122 2245 5555 1，2，3，，5，6，7，8 1234 1245 2368 5678 （四） 模型

将r个无区别的球放入n个不同的盒子，每个盒子的球数不

受限制。

（五） 应用

【例1.3.4】不同的5个字母通过通信线路被传送，每两个相邻字母之间至少插入3个空格，但要求空格的总数必须等于15，问共有多少种不同的传送方式？ （解）三步求解：

（1）先排列5个字母，排列数 P(5，5)＝5!。

（2）两个字母间各插入3个空格，将12个空格均匀地放入4个间隔内，有1种方案。

c △△△ b △△△ d △△△ e △△△ a （3）将余下的3个空格插入4个间隔：

分析：将3个相同的球放入4个不同的盒子，盒子的容量不限。 方案1：c△△△▲▲ b △△△ d △△△▲ e △△△ a 方案2：c△△△b △△△ d △△△e △△△▲▲▲ a 归纳：从4个相异元素中可重复地取3个元素的组合数RC??,3??C?4?3?1,3??20。

13/51 姜建国

《组合数学》 第一章 组合数学基础

（4）总方案数： L＝5！·1·20＝2400

1. 3. 6 不尽相异元素任取r个的组合问题

（一） 问题

设集合S??n1?e1,n2?e2,?,nt?et?（n1?n2???nt?n），从S中任取r个，求其组合数RC(n，r)。

（二） 组合数

中间工具：组合问题的母函数：

??x＝?1?x?x???xj2tnit?nii?1j?0i?1?＝?axrr?0nr

答案：RC(n，r)＝ar

（三） 应用

【例1.3.5】整数360有几个正约数？

（解）（1）标准素因数分解：360＝23×32×5 （2）正约数及其条件

1＝20×30×50，2＝2×30×50，3＝20×3×50，

5＝20×30×5，22＝22×30×50，6＝2×3×50＝3×2，

?

90＝2×32×5，180＝22×32×5，360＝23×32×5 结论：正整数d是360的正约数?d＝2a3b5c且0≤a≤

3，0≤b≤2，0≤c≤1。

故14不是约数，16＝24也不是约数。

（3）问题转化：求S??3?2,2?3,1?5?的所有组合数之和。 （4）求解：构造多项式

P6 (x)＝(1＋x＋x2＋x3)(1＋x＋x2)(1＋x) ＝1＋3x＋5x2＋6x3＋5x4＋3x5＋x6 系数求和： ???RC?6,i?＝1＋3＋5＋6＋5＋3＋1＝24

i?06方法化简：求P6(1)＝?RC?6,i?＝4×3×2＝24

i?06?k?1?2（5）一般规律：设正整数n分解为n?p1，则 p2?pk????1?1????2?1???k?1?

14/51 姜建国

《组合数学》 第一章 组合数学基础

习题：18，21

小结：课程任务；技巧性。

1.4 组合等式及其组合意义

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

n?rCr?Cnn

组合意义：?a1,a2,?,an?的r组合?n－r组合

【等式2】加法公式

rr?1Cr?C?Cnn?1n?1

（一）组合意义：?a1,a2,?,an?的r组合，分为两类：

?1（1） 取出的元素中含有a1：组合数为Crn?1。 （2） 不含元素a1，组合数为Crn?1。

r?1总数：Cr?Cn?1n?1

注意：①无第三种情形；②两类情况互不重复；③用加法法则。 （二）例：从{1，2，3，4，5}中取3个的组合情况： 第一类（包含元素“1”）： 123，124，125，134，135，145 第二类（不包含“1”）： 234，235，245，345 （三）路径问题：等价形式

15/51 姜建国

《组合数学》 第一章 组合数学基础

mmm?1Cm?C?C?nm?n?1m?n?1

组合意义：从（0，0）点到（m，n）点的路径数等于从（0，0）点分别到（m，n－1）点和（m－1，n）点的路径数之和。 ?m,n?

?0,0? 【等式3】乘法公式

krrk?rCnCk?CnCn?r n?kk?rrrn?kk?r等式变形： CnCkCr?CnCn?rCk?r 组合意义 （1） 左端：“将n个元素分为3堆：第一堆n?k个，第二堆

k?r个，则第三堆为r个”，求组合方案数。 （2） 右端：“将n个元素分为3堆：第三堆r个，第二堆n?k个，第一堆k?r个”，求组合方案数。 （3） 两个组合问题等价。

578785举例：n＝20＝5＋7＋8＝7＋8＋5，C20＝C20 C15C8C13C5推广：n个元素分为t堆，且可以若干堆个数相等

425294n＝20＝4＋2＋5＋9＝2＋9＋4＋5，C20＝C20 C18C16C18C9r【等式4】C(n＋r＋1，r)＝?C?n?i,i?

i?0＝C(n＋r，r)＋C(n＋r－1，r－1)＋C(n＋r－2，r－2)

＋C(n＋r－3，r－3)＋?＋C(n，0)

或 C(n＋r＋1，r)＝?C?n?i,n?

i?0r ＝ C(n＋r，n)＋C(n＋r－1，n)＋C(n＋r－2，n)

＋?＋C(n，n)

（一）组合意义：

16/51 姜建国

《组合数学》 第一章 组合数学基础

（二）说明：等式2的推广。

rr?1CrC?C＝n?r?1n?rn?r

rr?1r?2＝Cn?r?Cn?r?1?Cn?r?1

?rr?1r?2r?3＝Cn?r?Cn?r?1?Cn?r?2?Cn?r?2 ＝??

???rr?1r?210＝Cn?r?Cn?r?1?Cn?r?2???Cn?1?Cn?1

??＝Cn?r?Cn?r?1?Cn?r?2???Cn?1?Cn （三）相应的路径问题：

?r,n?1?

?0,0? 【等式5】Vandermonde（范德蒙）恒等式

r?m?n??n??m???r??＝???i????r?i?? ??i?0?????n??m??n??m??n??m?＝??0????r?????1????r?1???????r????0??, r≤min(m，n) ????????????rr?1r?210 ? ? ? ? ? 组合意义 n个相异的红球，m个相异的蓝球，选r个的组合。

?i分类统计：i个红球，r－i个蓝球的选法为CinCrm。 特例：m＝r

?n??r??n?r??n??r??n??r???0????r?????1????r?1???????r????0??， r≤n ?r??＝???????????????17/51 姜建国

《组合数学》 第一章 组合数学基础

?n??r??n??r??n??r?＝??0????0?????1????1???????r????r?? ????????????r?n??r?＝???i????i?? i?0????【等式6】和式公式：

?C?n,i??2n

i?0n组合意义：n个相异元素选i个的组合?两类元素的n可重排列

组合 φ e1e2e3e4e5e6 e1e3e6 e1 e2 e3 e4 e5 e6 e3e5e6 不 取 取 不 取 不 不 取 取 不 取 不 不 取 不 不 取 取 排列 000000 111111 101001 ?n??n??n?n?n?【等式7】??0?????1?????2???????1???n???0

????????组合意义：等式变形

0213Cn?Cn???Cn?Cn??

奇组合数＝偶组合数。

启发：存在一一对应关系。 例：n＝4 奇组合 a abc abd acd 偶组合 φ 2b ab 2c ac d bcd bc bd cd 2ad abcd 1??2?Cn2????n?Cnn??nC2nn??11 【等式8】?Cn组合意义：从n名先生、n名太太中选出n人，其中一人担任主席，且必须为太太，求选法数。

选法1：①选一名太太任主席；②再选n－1人。选法总数1n?1n?1为CnC2n?1?nC2n?1。

选法2：①从n名太太中选k人；②从此k人中选一人任主席；③再从n名先生中选n－k人（1≤k≤n）。

18/51 姜建国

《组合数学》 第一章 组合数学基础

1n?kk2?CkCC?kCnknn? k2? 选法总数＝?k?Cnk?1n【等式9】设r，M都是自然数，M≥r则有

rM?rrM?rM?r?1r

?????MMM?1MM?1M?2 ???M?r?M?r?1?1?r?1

MM?1r?1r组合意义（概率问题）：设袋中有M个大小相同的球，其中

白球r个，其余为黑球。每次摸出一个球，不放回，直至摸到白球为止。

是必然事件（迟早会摸到白球），概率为1。

r另法：第一次摸到白球概率。第二次摸到白球

MM?rr第k次才摸到白球（k＝2, 3, ?, M－r＋1） ?,??，

MM?1M?rM?r?1M?r??k?2?r ?????MM?1M??k?2?M??k?1?【等式10】当n≥m时，

n?mk?0m?kmn?mmCC?2?C?nm?kn

组合意义：从n人中选出m名正式代表及若干名列席代表

的选法（列席代表人数不限）。

统计方法一：先选正式代表，再从n?m人中选列席代表，

mn?m总的选法为Cn2。

统计方法二：先选m＋k人（k＝0, 1, ?, n－m） ，再从中

?kmCm?k种选选出m名正式代表，其余的k人为列席代表，有Cmn法。

n?m总数＝

k?0m?kmC?nCm?k

19/51 姜建国

《组合数学》 第一章 组合数学基础

1.5 多项式系数

（一） Newton二项式 (1) 二项展开式

Newton二项式定理（n是正整数）

?a?b?(2) 组合意义

nrrn?r??Cnab r?0nr右端称为二项式(a＋b)n的展开式，Cn叫做二项式系数。

分配问题：将n个相异的球放入两个盒子，a盒放入n1?r个，b盒放入n2?n?r个，同盒的球不分次序，方案数为

n!n!＝ n1!?n2!r!??n?r?!r即arbn?r项的系数为组合数Cn。

例 ?a?b?＝(a＋b)(a＋b)＝aa＋ab＋ba＋bb＝a2?2ab?b2

2?a?b?3＝(a＋b)(a＋b)(a＋b)＝(aa＋ab＋ba＋bb)(a＋b)

＝aaa＋aab＋aba＋abb＋baa＋bab＋bba＋bbb

＝a3?3a2b?3ab2?b3

产生系数的根源：同一单项式中有顺序，即排列问题（球不同的分配问题）。 排列问题：从两种元素中选n个的排列（a选r个，b选n?r个）

（二） 一般分配问题

问题：将n个相异的球放入t个盒子，要求第1个盒子放入n1个，第2个盒子放入n2个，??，第t个盒子放入nt个，且盒中的球无次序，求不同的分配方案数。

转化：求S??n1?e1,n2?e2,?,nt?et?（n1＋n2＋?＋nt＝n）的全排列数RP(n，n)：

n!RP?n,n??

n1!n2!?nt!n???n?仿照二项式系数??r??，记为??nn?n??。

??t??1220/51 姜建国

《组合数学》 第一章 组合数学基础

（三） 多项式系数

n??一般多项式系数与??nn?n??的关系：

t??12?x?y?z?3＝x3＋y3＋z3＋3x2y＋3xy2＋3x2z＋?＋6xyz

3!3!3!3!＝x3＋ y3＋ z3＋x2y 3!?0!?0!0!?3!?0!0!?0!?3!2!?1!?0!3!3!3! ＋xy2＋x2z＋?＋xyz

1!?2!?0!2!?0!?1!1!?1!?1!3?3 3?3?3?3??＝??003??z?300??x＋??030??y＋???????3?23?2?3?2??＋??210??xy＋??120??xy＋??201??xz ???????3?＋?＋??111??xyz

??【定理1.5.1】设n与t均为正整数，则有

n??n1n2nnt?x1?x2???xt?＝?? ?xx?x12t??n1n2?nt?t??ni?n?ni?0?i?1其中求和是在使?ni?n的所有非负整数数列（n1,n2,?,nt）上

i?1t进行。

＝?x1?x2???xt??x1?x2???xt???x1?x2???xt? （证）?x1?x2???xt?

n?????????????????????????共n个因子连乘n（1）所有项都具形式

xx?x，且?ni?n

n11n22ntti?1nnn（2）一般项的系数：ni个因式中选取xi，得x11x22?xtt项，其系数为

C?n,n1??C?n?n1,n2??C?nt,nt?

21/51 姜建国

《组合数学》 第一章 组合数学基础

＝

?n?n1?!?nt! n!?n1!??n?n1?!n2!??n?n1?n2?!nt!?0!n??n!?＝＝? ??n1!n2!?nt!?n1n2?nt?n??称??nn?n??为多项式系数。 ?12t?（四） 多项式展开的项数

【定理1.5.2】?x1?x2???xt?展开式的项数等于Ctn?n?1，

n而这些项的系数之和为tn.

nnn（证）展开式的项x11x22?xtt?从t种元素x1,x2,?,xt中取n个的n可重组合。

在定理1.5.1中令x1?x2???xt＝1得

n??n??n ???＝??1?1???1?tt?n1n2?nt?n?n?i?ni?0?i?1（五） 例

【例1.5.1】求?a?b?c?d?3的展开式。

（解）n＝3，t＝4，有RC(∞，3)＝C(4＋3－1，3)＝20（项）

?a?b?c?d?3

33??3??3??＝?＋＋?＋a?3000??0300??b????33??2??2???＋?＋＋ab?2100??0012??cd????33???????＋?＋abc?1110??0111??bcd ????＝a3＋b3＋c3＋d3＋3a2b＋3a2c＋3a2d＋?＋3cd2＋6abc＋6abd＋6acd＋6bcd

23【例1.5.2】?a1?a2?a3?a4?a5?的展开式中，项a1a3a4a5的

722/51 姜建国

《组合数学》 第一章 组合数学基础

系数。

7??7!??20131???2!?0!?1!?3!?1!＝420 ??32【例1.5.3】在?2x1?3x2?5x3?的展开式中，项x1的系x2x3数是什么？

（解）令a1?2x1，a2??3x2，a3?5x3。

6? 展开?a1?a2?a3?：

6?32a1a2a3的系数＝??66?? ??312?32＝?2x1?3x2?5x3?中?2x1???3x2??5x3?的系数

32? x1的系数： x2x36??36!2????2?35＝?8???3??25 ?312?3!?1!?2!??＝－36000

【例1.5.4】求证

kn?kk???????1Cn,kx1?x?n?1，n≥1

nk?0（证）（证明组合等式）在二项式中取a＝－x，b＝1＋x

1＝1n＝???x???1?x?? ＝

k?0?C?n,k???x??1?x?k100nn?k

【例1.5.5】今天是星期日，再过10（解）（求余数，同余运算）

天是星期几？

5010100＝10050＝?14?7?2?

50?50?r50?r50???14?72＝2??? ?r??r?1?等价问题：10100除以7的余数＝250除以7的余数 250＝22?3?16＝4?816＝4?7?1?

1623/51 姜建国

《组合数学》 第一章 组合数学基础

16??16?r?＝4?1????r??7?≡4（mod 7）

??r?1??另法：10?100?r100?r ????r??7?3r?1??333100＝3?2733＝3?28???1??

33?33?r3333?r? ＝3????1??????r??28???1?r?1????333??1?＝－3≡4（mod 7）

100＝?7?3?100＝3100100（六） 问题

请给出多项式?a?2b???c??3d?的展开式中a2b2c2d2和2?8。 bc5d2两项的系数（答：22680，－189/2）

1.6 排列的生成算法

1. 6. 1 序数法

（一） 数的位权表示

（1）十进制数：小于10r的正整数n的位权形式：

n＝

k?02ka10?k， 0≤ak≤9＜10 r?1例 315＝3?10?1?101?5?100（r＝3）

（2）推广（p进制数）

n＝

kap?k， 0≤ak＜p r?1k?0（3）特点：①固定进制；②逢p进一；③十进制r位数最小为

0，最大为999?9＝10r－1＜10r；④将十进制换算为p进

制数方法：除p取余法。

（二） 变进制表示

（1）依据： n!＝(n－1)(n－1)!＋(n－1)!

递归：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)!

24/51 姜建国

《组合数学》 第一章 组合数学基础

??

＝(n－1)(n－1)!＋(n－2)(n－2)!＋?＋2·2!＋1·1!＋1!

n!＝

?k?k!＋1

k?1n?1n!－1＝(n－1)(n－1)!＋(n－2)(n－2)!＋?＋2·2!＋1·1!

n类似 10－1＝9?10n?1＋9?10n?2＋?＋9?101＋9?100 结论：从0到n!－1的任何整数m都可唯一地表示为 m＝an?1(n－1)!＋an?2(n－2)!＋?＋a22!＋a11!＝其中 0?ai?i（i＝1，2，?，n－1） 结论： m??an?1,an?2,?,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?1?n?1?!?an?2?n?2?!???a22!?a11!

记 n1?m

?n?2?!?n?1?!3!?n1?n2???＝an－1＋an－2＋?＋a3＋a2

222?2?m÷2!＝n1?2?n2????a1

?ak?k!

k?1n?1?n?1?!＋a?n?2?!＋?＋a4!＋a ?n2?n3＝??＝an?13n?243!3!3!?3?(m－a1)÷3!＝n2?3?n3????a2

算法：

?n1?m??ni??,i?1,2,?,n?1 ?ni?1????i?1????ai?ni??i?1?ni?1,i?1,2,?,n?1其中?x?表示不大于x的最大整数。

25/51 姜建国

《组合数学》 第一章 组合数学基础

（3）特点：① 变进制；② 从右向左，第i位逢i＋1进一；③

n－1位数最小为0，最大为：(n－1)(n－1)!＋(n－2)(n－2)!＋?＋2·2!＋1·1!＝n!－1＜n!；④将十进制换算为变进制数方法。

（三） 序数法 （1）规则

设n 个元素为1，2，?，n。

特点：n元排列?n－1位变进制数。 对应规则： 序列?an?1,an?2,?,a1??排列（p）＝?p1p2?pn?，其中ai为排列（p）中数i＋1所在位置后面比i＋1小的数的个数，即排列（p）中从数i＋1开始向右统计不大于i的数的个数 （2）实例

1）排列?数：n＝4

（p）＝（3124）??a3a2a1?＝(020)

2）数?排列

?a3a2a1?＝(111) ?（p）＝（2341）

3）数 (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 1

4）排列 3, 5, 7, 9, A, 8, 6, 4, 2, 1 ? 数 (5 5 4 4 3 3 2 2 1) （3）例：4元排列的生成

m 0 1 2 3 4 5 6 7 8 9 10 11 a3 a2 a1 p1 p2 p3 p4 000 1234 001 2134 010 1324 011 2314 020 3124 021 3214 100 1243 101 2143 110 1342 111 2341 120 3142 121 3241 m 12 13 14 15 16 17 18 19 20 21 22 23 a3 a2 a1 p1 p2 p3 p4 200 1423 201 2413 210 1432 211 2431 220 3412 221 3421 300 4123 301 4213 310 4132 311 4231 320 4312 321 4321 26/51 姜建国

《组合数学》 第一章 组合数学基础

1. 6. 2 字典序法

（一） 算法

将所有n元排列按照“字典顺序”排成队。 初始排列：?12?n? 设当前排列为?p???p1p2?pn? （1） 求满足关系式pk?1?pk的k的最大值，设为i，即 i?max?kpk?1?pk? （2） 求满足关系式pi?1?pk的k的最大值，设为j，即 j?max?kpi?1?pk? （3） pi?1与pj互换位置得?q???q1q2?qn? （4） ?q???q1q2?qi?1qiqi?1?qn?中qiqi?1?qn部分的元素顺序逆转，得新排列q1q2?qi?1qn?qi?1qi。 （二） 例

（1）设p1p2p3p4＝3421：i＝2，j＝2，p1与p2交换得q1 q2 q3

q4 ＝4321，321逆转得下一排列4123 。 n＝4的全部排列：

1234 → 1243 → 1324 → 1342 → 1423 → 1432 →

2134 → 2143 →2314 → 2341 → 2413 → 2431 → 3124 → 3142 → 3214 → 3241 →3412 → 3421 → 4123 → 4132 → 4213 → 4231 → 4312 → 4321 说明：第（4）步的必要性 （2）85376421 ? i＝4，j＝6 ?q1q2?q8＝85476321 ? 85412367

85412367 ? i＝8，j＝8 ?q1q2?q8＝85412376 85412376 ? i＝7，j＝8 ?q1q2?q8＝85412673 ?

85412637 85413726 ? i＝8，j＝8 ?q1q2?q8＝85413762 85413762 ? i＝6，j＝7 ?q1q2?q8＝85416732 ?

85416723

27/51 姜建国

《组合数学》 第一章 组合数学基础

1. 6. 3 邻位互换生成算法

???初始排列：123?n（当一个数上方箭头所指的一侧相邻的数比该数小时，称该数处于活动状态） ???初始排列：123?n 设当前排列为?p???p1p2?pn? （1） 若排列?p???p1p2?pn?中无一数处于活动状态，则停止，否则转（2）； （2） 求所有处于活动状态的数中的最大者，设为k，k和它的箭头所指的一侧的相邻数互换位置，转（3）; （3） 令比k大的所有数的箭头改变方向，转（1）。 举例（n＝4）：

28/51 姜建国

《组合数学》 第一章 组合数学基础

1221?????1?123??1??1????4????4???132???1??1???1??????3?312??3??3????4?????4?321??3??3????3??????2?231???2??2???4??????4?213??2??2????229/51 姜建国

232442121343343212144131324224213134432321411413433322244222111441113334 《组合数学》 第一章 组合数学基础

规律：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 → 345 → 346 → 356 → 456

规律：低位累加，逐位前移。

（1）设组合c1c2?cr满足 c1＜c2＜?＜cr

则 cr≤n，cr－1≤n－1，?，c1≤n－r＋1 即 ci≤n－r＋i，i＝1, 2, ?, r

（2）当cj＜n－r＋j时，令i＝maxjcj?n?r?j，并令

???dk?ck,1?k?i? ?di?ci?1,?d?d?1,i?k?r?kk?1得新组合d1d2?dr 。若每个cj ＝n－r＋j，则已经达到最后一个

组合，生成完毕。

算法： 初始组合：?12?r? 当前组合：c1c2?cr （1） 若i＝maxjcj?n?r?j存在，转（2），否则，停止； （2） ci←ci＋1ci?ci?1; ??cj?cj?1?1，（3） j＝i＋1, i＋2, ?, r。输出?c1c2?cr?，转（1）。 例：n＝10，r＝5 14678 → 14679 → 1467A → 14689 → 1468A → 1469A → 14789

1.8 应用举例

【例1.8.1】试确定由1，2，3，4，5这五个数字能组成多少个大于43500的五位数？

（解）（有限制条件的RP(∞，5)的问题）。分类统计：

30/51 姜建国

《组合数学》 第一章 组合数学基础

（1） 万位上数字是5：有1×5 4个符合要求的数； （2） 万位4，千位4，5：有1×2×53个；

（3） 万、位、百位分别为4、3、5：有1×1×1×52个。 总数： 54＋2×53＋52＝900 （个）

【例1.8.2】从－2，－1，0，1，2，3共6个数中不重复地选3个数作为二次函数y?ax2?bx?c的系数，使得抛物线

y?ax2?bx?c的开口方向向下，共可作出多少个二次函数？

（解）（不重复排列）抛物线开口向下?a＜0。 第一步：a从－2、－1中选一个，有P21种方法； 第二步：在余下的五个数中选b和c，有P52种方法。 函数个数 P21P52＝40（个）

【例1.8.3】满足x1?x2?x3?x4?100的正整数解有多少组？

（解）（组合问题）方法Ⅰ 思路：长度为100的线段被分为4段，每段的长度均为正整数，记为x1，x2，x3，x4。

例：x1＝10，x2＝35，x3＝40，x4＝15，10＋35＋40＋15＝100。

— — ? — ＋ — — ? — ＋— ?— — —＋ — ? —

问题转化：在99个空位置上放3个“＋”号，未放“＋”

号的线段合成一条线段，求放法总数。首尾和两“＋”之间至少一段。

分配模型：将3个相同的球放入99个相异的盒子，每盒最多放一个球。

排列组合问题：从99个相异元素中不重复地选3个。

99?98?973C99＝＝156849（组）

3?2?1方法Ⅱ：x1?x2?x3?x4?100

31/51 姜建国

《组合数学》 第一章 组合数学基础

分配模型：将100个相同的“1”放入4个不同的盒子，每个盒子至少放一个。求不同的放法数。

排列组合问题：从4种相异元素中可重复地选100个，每种元素至少选一个。

第一步：每个盒子先放一个，共有一种放法。

96963第二步：将余下的96个1放入，有C4?C?C?96?19999

变异一：求非负整数解（即xi?0）。

用方法Ⅰ求解：x1?x2?x3?x4?100

— — ? — — ? — ＋ — — ? — — ＋ — — ? —＋ — — ? — — ? — ＋＋ — — ? — — ＋ — — ? —

33?C答：C101?3?1103＝176851

用方法Ⅱ求解：将100个相同的球放入4个不同的盒子，每

个盒子的容量无限。求不同的放法数。

1001003?C?C答：C4?100?1103103＝176851

变异二：求解。x1??3，x2?5，x3?0，x4?0。 思想：将问题转化为变异一。

原方程 ?x1?3???x2?5??x3?x4?98

变换 y1?x1?3，y2?x2?5，y3?x3，y4?x4 转化 y1?y2?y3?y4?98 （yi?0）

98983?C?C答：解数为 C4?98?1101101＝166650

问题：将原题用变异二的思路求解。

y1?y2?y3?y4?96

【例1.8.4】把r个相异物体放入n不同的盒子里,每个盒子允

许放任意个物体,而且要考虑放入同一盒中的物体的次序,求这种分配方案有多少?

特点：既不是相异元素的不重复排列，也不是简单的重复排列。 思路：放一个物体增加一个隔板（盒子）。

32/51 姜建国

《组合数学》 第一章 组合数学基础

?n?r?1?!r方案数 n(n＋1)(n＋2)…(n＋r－1)＝＝Pn?r?1

?n?1?!1 2 3 4 5 ? n－1 n r说明：不考虑盒中相异物体的次序，方案数为n＝ ?n???nn?????r个应用：A、B、C、D、E共5位同学由两个门排队进入教室，每个门每次只能同时进一人，问有多少种进法？ 答：2×3×4×5×6＝720种

前门人数 0 1 2 3 4 5 后门人数 5 4 3 2 1 0 方法 1×5!＝120 1C5×1×4!＝120 备注 0C5×0!×5! 1C5×1!×4! 2C5×2!×3!＝120 3C5×3!×2!＝120 4C5×4!×1!＝120 5C5×5!×0!＝120 若不考虑次序，总数为25＝32。

问题1：设前门宽大，可以同时进2人，那么又有多少种不

同的进法？

答：有 3×4×5×6×7＝2520种。

问题2：火车站外有100名乘客，欲从4个门排队进入候车室，问有多少种进门的排队方式？

问题3：大楼共有19层，今有12人从一楼进入电梯上楼，每层都可能有人出电梯，且电梯的门同时只能容许一个人出入，问有多少种方式出电梯？

【例1.8.5】把n元集S划分成n?3个无序非空子集（n≥4），共有多少种分法？ （解）（球不同盒子相同）模型：分配问题：将n个不同的球放入n－3个相同的盒子，每个盒子最少一个球

33/51 姜建国

《组合数学》 第一章 组合数学基础

求解：分三类情况：

(1) 一个子集为4元集，其余子集为一元集，等于n元集的

4不重复的4组合数Cn；

(2) 一个子集3元，一个子集2元，其余子集1元：n元集S5的5组合数为Cn，把5元集划分成一个3元子集和一个32元子集的方法有C5＝10种，由乘法法则，此类划分方5法有10Cn种；

6(3) 3个子集2元，其余子集1元：n元集的6组合数为Cn，把6元子集划分成3个2元子集的方法有

6?16!1?????15 ??3!?222?3!2!2!2!?n? 属于此类的划分方法有15???6??种。

???n??n??n?总数 L＝??4???10??5???15??6??

??????【例1.8.6】设fr?n,k?是能够从集合?1,2,?,n?中选出两两之

差均大于r的k元子集的方案数，试求fr?n,k?。

（解）（更一般的组合问题）集合A＝?1,2,?,n?中取k个两两之差超过r的数构成组合a1,a2,?,ak，设a1?a2???ak

aj?ai≥r＋1， 1≤i＜j≤k 令 bi?ai??i?1?r， i?1,2,?,k 则 bj?bi≥1， 1≤i＜j≤k

且 1≤b1?b2???bk≤n－(k－1)r

结论：从A中选k个元素的方案?从集合B不重复地选取k个元素的方案（B＝?1,2,?,n??k?1?r?）

?n?rk?r??∴ fr?n,k??? ??k??说明：r＝0，不重复组合

r＝-1，重复组合 r＝1，间隔1个选

34/51 姜建国

《组合数学》 第一章 组合数学基础

r＝m，间隔m个选

例：

【例1.8.7】有7位科学家从事一项机密工作，他们的工作室装有电子锁，每位科学家都有打开电子锁的“钥匙”。为了安全起见，必须同时有4人在场时才能打开大门。试问该电子锁至少应具备多少个特征？每位科学家的“钥匙”至少应有多少种特征？

（解）（秘密共享）分析：任意3个人在一起，至少缺一种特征，不能打开电子锁。

结论1：电子锁最少特征数：C(7，3)＝7?6?5＝35

3?2原因：每一组合所形成的3人小组缺少的特征必须不一样的。 1 2 3 4 5 6 7 ABC ABD ABE ABF ABG ACD ACE 8 9 10 11 12 13 14 ACF ACG ADE ADF ADG AEF AEG 15 16 17 18 19 20 21 AFG BCD BCE BCF BCG BDE BDF 22 23 24 25 26 27 28 BDG BEF BEG BFG CDE CDF CDG 29 30 31 32 33 34 35 CEF CEG CFG DEF DEG DFG EFG 结论2：科学家A的“钥匙”的特征个数至少为

6?5?4C(6，3)＝＝20

3?2原因：A须有其余6人缺的钥匙。

例：A＝{16～35}；B＝{6～15，26～35}；C＝{2～5，10～15，20～25，32～35}；

【例1.8.8】从（0，0）点到达（m，n）点（ma，问有多少条最短路径？

（解）分析：第一步必须从（0, 0）到（0, 1）。等价于从（0, 1）点到（m, n）点的路径数（前提：满足条件）。 从（1, 0）到（m, n）的路径?从（0, 1）到（m, n）点但经过y＝x线上的格子点的路径

?m,n?

35/51 姜建国

《组合数学》 第一章 组合数学基础

?0,0? 对应规则：最后一次离开对角线之前对称，之后重合。： 结所求路径数＝ 论 (0, 1)点到（m, n）点路径数－(1, 0)点到（m, n）点路径数 ?m?n?1??m?1?n??? N＝? ??????m???m?1???11 ＝(m＋n－1)!? ???m!(n?1)!(m?1)!n!?m??n ＝(m＋n－1)!? ???m!n!m!n!?(m?n?1)!n?m?n?m??? ＝ （n—m）＝ ??m!n!n?m?m?【例1.8.9】n, h, r都是非负整数，并且n?k?r。证明

k?rrCn?Cn?k （1.8.1）

等号何时成立？

k?r（解）构造问题：在a1,a2,?,an中取k＋r个元，有Cn种取法。

一种特殊取法：先取前k个元素a1,a2,?,ak；再从其余的

n?k个元素ak?1,ak?2,?,an中取r个，有Cn?k种。

r结论：后一种取法是前者的部分情况。

等号成立的条件：n＝k＋r（否则总有不全含a1,a2,?,ak的

36/51 姜建国

《组合数学》 第一章 组合数学基础

k＋r元子集）。反过来，当n＝k＋r时，确实有

k?rrCn?1?Cn?k

【例1.8.10】

（一） 二进制串的汉明距离

n位二进制码

a?a1a2?an， b?b1b2?bn

ai?bi的个数为k，记为d?a,b??d?b,a??k，称为a、b码的Hamming距离。

例：(0000, 0000)＝0，(0000, 1001)＝2，(0101, 1010)＝4 （二） 性质

三角不等式 d?a,b??d?b,c??d?a,c? （三） 检错码与纠错码

检错码：奇偶校验码、汉明码、BCH码等。 纠错码：汉明码、BCH码、郭帕码等。

（四） 汉明码

（1） 思想：如若a?与码a的距离≤r，则认为a?是a的错误码而予以纠正。

（2） 编码的距离要求：d?a,b?≥2r＋1

否则可构造c，使之满足d?a,c?＝d?c,b?＝r而无法纠错。

反之，设任何d?a,b?≥2r＋1。若d?a,a??≤r，则由三角不等式知对其它码字b，有

d?a?,b?≥d?a,b??d?a,a??≥(2r＋1)－r＝r＋1＞r （3） 例：r＝1，n＝8

字母 码字 相近码 a 00000000 10000000，01000000，?，00000001 b 11100000 01100000，10100000，?，11100001 c 00011100 10011100，01011100，?，00011101 可编码字符数：

?28??256?n＝8，r＝1，M≤?0＝28 ??1???C8?C8??9?37/51 姜建国

《组合数学》 第一章 组合数学基础

???256?28n＝8，r＝2，M≤?0＝6 ??12???C8?C8?C8??37????1024?210n＝10，r＝2，M≤?0＝18 ??12???C10?C10?C10??56????4096?212n＝12，r＝2，M≤?0＝51 ??12???C12?C12?C12??79?（五） 编码量

编码集：?a1,a2,?,aM?（n位二进制码） 条件：d?ai,aj?≥2r?1

?n??n??n?与ai的距离小于等于r的数有??0?????1???????r??个

??????令Ui＝{a|d(a，ai)≤r}，每个数最多只能属于U1，U2，?UM

中的一个

??n??n??n??n≤ 2?????M????????0??1??r??????????n2编码量： M≤

?n??n??n????????...??0??1??r????????

38/51 姜建国

《组合数学》 第一章 组合数学基础

习题1

（1）基本题：1～9，14，16，19，22～23，29，31 （2）加强题：11～12，17，18，21，28 （3）提高题：13，15，20，24～26，30，32 （4）关联题：10，27

1-1. 在1到9999之间，有多少个每位上数字全不相同而且由奇

数构成的整数？

（解）问题相当于求在相异元素{1, 3, 5, 7, 9}中不重复地取1个、2个、?、4个元素的所有排列数，答案为

P51?P52?P53?P54＝5＋20＋60＋120＝205

1-2. 比5400小并具有下列性质的正整数有多少个？

（1） 每位的数字全不同；

（2） 每位数字不同且不出现数字2与7。 （解）（1）分类统计：①一位正整数有P91?9个；②两位正整数有P91?P91＝81个；③三位正整数有P91?P92＝9×9×8＝648个；④千位数小于5的四位数有P41?P93＝4×9×8×7＝2016个；⑤千位数等于5，百位数小于4的数有1?P41?P82＝4×8×7＝224个。由乘法法则，满足条件的数的总个数为

9＋81＋648＋2016＋224＝2978

（2）仿（1），总个数为

P71＋P71?P71＋P71?P72＋P31?P73＋1?P31?P62 ＝7＋49＋294＋630＋150＝1130

1-3. 一教室有两排，每排8个坐位，今有14名学生，问按下列

不同的方式入座，各有多少种坐法？

（1） 规定某5人总坐在前排，某4人总在后排，但每人具体坐位不指定；

（2） 要求前排至少坐5人，后排至少坐4人。

39/51 姜建国

《组合数学》 第一章 组合数学基础

（解）

（1）5人在前排就座，其坐法数为 P?8,5?，4人在后排就座，其坐法数为 P?8,4?，还空7个坐位，让剩下的14－5－4＝5个人入坐，就座方式为 P?7,5?种，由乘法法则，就座方式总数为

P?8,5?P?8,4?P?7,5?＝28 449 792 000

（2）因前排至少需坐6人，最多坐8人，后排也如此。可分成三种情况分别讨论：①.前排恰好坐6人，入坐方式有?14???6??P?8,6?P?8,8?种；②. 前排恰好坐7人，入坐方式有???14???7??P?8,7?P?8,7?种；③前排恰好坐8人，入坐方式有???14???8??P?8,8?P?8,6?种。各类入坐方式互相不同，由加法法则，总的??入坐方式总数为

?14??14??14???6??P?8,6?P?8,8?＋??7??P?8,7?P?8,7?＋??8??P?8,8?P?8,6? ??????误：先选6人坐前排，再选4人坐后排，剩下的4人坐入余下的6个座位。故总的入坐方式共有

?14??8???6??P?8,6???4??P?8,4?P?6,4? ????种。但这样计算无疑是有重复的，例如恰好选6人坐前排，其余8

?8?人全坐后排，那么上式中的??4??P?8,4?就有重复。

??

1-4. 一位学者要在一周内安排50个小时的工作时间，而且每天

至少工作5小时，问共有多少种安排方案？ （解）是重复组合问题。（1）每周按7天计算，先要拿出5×7＝35小时平均分配到每一天，再将其余的15小时安排到7天之中，每天的小时数不受限制，则安排方案数为

?7?15?1??21???????54264 ????15??15??40/51 姜建国

《组合数学》 第一章 组合数学基础

（2）若每周的工作日按6天计，则问题变成在平均分配完5×6＝30小时后，再将余下的20小时分配到这6天中，但此时每天最多只能分配19小时。或者更一般，每天在5小时外再最多工作ni小时?0?ni?19?，那么，答案是多项式

??1?x?xi?162???xni?＝?axrr?0nr

中x20的系数a20，其中n?n1?n2???n6。 （3）另外，设每周工作t天?3?t?7?，每天最少工作5小时，最多工作ni小时?5?ni?24?，可以不按照上边的两步分配方法求解，而是直接计算多项式

??xi?150t5?x?x???x67ni?＝?axrr?0nrt??n?n，??i???

i?1??中x的系数a50，即得答案。

1-5. 若某两人拒绝相邻而坐，问12个人围圆桌就坐有多少种方

式？

（答） 11！－2×10！＝9×10！ 1-6. 有15名选手，其中5名只能打后卫，8名只能打前锋，2

名能打前锋或后卫，今欲选出11人组成一支球队，而且需要7人打前锋，4人打后卫，试问有多少种选法？ （答） ?8??5??2???8??5??8??5????8??5??8??5??8??5????7????4?????1?????6????4?????7????3???????5????4?????7????2???2??6????3??? ??????????????????????????????＝40＋2×(140＋80)＋(280＋80＋2×280)＝1 400 1-7. 求?x?y?2z?w?展开式中x2y2z2w2项前的系数。

88??222?????（答） ? ?1??1?2?1?2222???8!?4＝10080 ＝

2!?2!?2!?2!41/51 姜建国

《组合数学》 第一章 组合数学基础

1-8. 求?x?y?z?的展开式。 （解）由多项式的展开式公式

4??n?x?y?z?4＝3???1n?4i??ni?0?i?1nn2?n1n2n3?xyz ?n3?4?4?4?4?4?4?4?3?＝??004??z＋??310??xy?400??x＋??040??y＋?????????4?3??4?3?4?3????＋?＋＋xyxz?301??031??yz＋?130???????4?224?22?4?3?4?3?????????＋＋＋xzyzxy?103??013??220??202??xz????????4?22?4?2??4?2????＋?＋＋yzxyz?211??022??121??xyz＋???????4?2??112??xyz ??4!4!4!4!4!x4＋y4＋z4＋x3y＋x3z＋＝

4!?0!?0!0!?4!?0!0!?0!?4!3!?1!?0!3!?0!?1!4!4!4!4!4!xy3＋y3z＋xz3＋yz3＋x2y21!?3!?0!0!?3!?1!1!?0!?3!0!?1!?3!2!?2!?0!4!4!4!4!x2z2＋y2z2＋x2yz＋xy2z＋＋

2!?0!?2!0!?2!?2!2!?1!?1!1!?2!?1!4!xyz2 1!?1!?2!＝x4＋y4＋z4＋4x3y＋4x3z＋4xy3＋4y3z＋4xz3＋4yz3＋

6x2y2＋6x2z2＋6y2z2＋12x2yz＋12xy2z＋12xyz2

可以验证，系数之和

1×3＋4×6＋6×3＋12×3＝81＝34

36x3x41-9. 求?x1?x2?x3?x4?x5?展开式中x2的系数。

10??10!?（答） ?＝?03160?0!?3!?1!?6!?0!＝840

??101-10. 试证任一正整数n可唯一地表成如下形式：

42/51 姜建国

《组合数学》 第一章 组合数学基础

n＝?aii! ，0≤ai≤i，i?1,2,?

i?11-11. 证明 nC(n－1，r)＝(r＋1)C(n，r＋1)。并给出组合意义。 意义：将n个人分为3组：一组1人，一组r人，另一组n??r?1?人。一种分法是先从n个人中选出r＋1人，剩下n??r?1?人为一组，再将所选的r＋1人分为两组，一组1人，一组r人。另一种分法是先选一人为一组，再从其余的n?1人中选r人为一组，剩下的n??r?1?人为一组。 1-12. 证明

n?1??kCn,k?n2。 ?k?1n（证）用殊途同归法。将n个不同的球放入标号为A、B、C

的3个盒子，其中要求A盒只放1个球，其余两盒的球数不限。那么，有两种思路：

（1） 先从此n个不同的球中选出1个，放入A盒，再将其

1?2n?1?n2n?1种放法； 余n?1个球放入另外两盒，有Cn（2） 先由n个球中选出k个?1?k?n?，再从所选的k个球中选出1个放入A盒，将其余的k－1个球放入B盒，所剩的nk1n?kk?Ck?Cn－k个球放入C盒，有Cn?k?kCn种放法。当

k?1,2,?,n，各种情况互不重复，且包含了所有放法，故对k求和，即得等式左端。

1-13. 有n个不同的整数，从中取出两组来，要求第一组数里的

最小数大于第二组的最大数，问有多少种方案？

（解） 设取的第一组数有a个，第二组有b个，而要求第一组数中最小数大于第二组中最大的，即只要从n个数中取出m＝a＋b个数，从大到小排序后取前a个作为第一组，剩余的为第二组，就满足题目的要求。此时从n个数中取m个的方案数为C(n，m)。从m个数中取第一组数共有m－1种取法。故总的方案数为

n?1m(n?2)2?1 ??＝m?1C?nni?21-14. 六个引擎分列两排，要求引擎的点火次序两排交错开来，

43/51 姜建国

《组合数学》 第一章 组合数学基础

试求从某一特定引擎开始点火有多少种方案？ （解）设两排引擎分别为a,b,c 和x,y,z。

（1）设特定的引擎是a，则点火的方案数为3×2×2×1×1＝12。

（2）如果只指定从a,b,c这一排先开始点火，不指定某一个，则方案数为

3×3×2×2×1×1＝36

（3）如果第一个引擎任意选，只要求点火过程是交错的，则方案数为

6×3×2×2×1×1＝72 1-15. 试求从1到1000000的整数中，0出现了多少次？ （解）先不考虑1 000 000本身，那么任一个000 000～999 999之间的数都可以表示成如下形式

d1d2d3d4d5d6

其中每个di是0到9的数字。因为每位数字可以有10种选择，根据乘法法则，共有106个“6位数”，又每个“6位数”由6个数字组成（包括无效0），那么共有6?106个数字，又每个数字出现的概率相等， 所以0出现的次数应是

6?106÷10＝6?105

但习惯上在计算0的个数时，不包括无效0（即高位的0），因而要从中去掉无效0，其中 1位数有9个（不包括0），其无效0共有5?9个； 2位数有90个，其无效0共4?90个。 余类推，这样，无效0的总数为

5?9?4?90?3?900?2?9000?1?90000

注意到d1d2d3d4d5d6全0时的6个0和1 000 000本身的6个0相互抵消，所以1到1 000 000之间的自然数中0出现的次数为

6?105??5?9?4?90?3?900?2?9000?90000?

＝488 895 注 1出现的次数为6?105?1（要考虑1 000 000这个数的首位1），2，3，?，9各自出现的次数为6?105。

44/51 姜建国

《组合数学》 第一章 组合数学基础

1-16. n个男n个女排成一男女相间的队伍，试问有多少种不同

的方案？若围成一圆桌坐下，又有多少种不同的方案？ 答 （1）2?n!?； （2）n!(n－1)!

21-17. n个完全一样的球，放到r个有标志的盒子，n≥r，要求无

?n?1?一空盒，试证其方案数为??r?1?? 。

??（证） 因为盒子不能空，所以每个盒子可先放一个球。然后

把剩下的n?r个球任意地放到r个盒子中，因为此时每盒的球数不限，这相当于求

S????e1,??e2,?,??er?

的n?r组合，其组合数为

?r??n?r??1??n?1??n?1????????? ??????n?r???n?r??r?1??k?1?2p2?pk1-18. 设n＝p1，p1、p2、…、pk是k个不同的素数，

试求能整除尽数n的正整数数目。 答 ??i?1???2?1????k?1?

1-19. 试求n个完全一样的骰子能掷出多少种不同的方案？

（解）等价于从6类相异元素集S????1,??2,?,??6?中可重复地选取n个元素的n－重组合数：

?6?n?1??n?5??n?1??n?2???n?5???? ???????n??n?5!?1-20. 凸十边形的任意三个对角线不共点，试求这凸十边形的对角线交于多少个点？又把所有的对角线分割成多少段？ （解）（1）求交点数：一个交点?两条对角线?四个顶点。

4∴ 交点数＝Cn

45/51 姜建国

《组合数学》 第一章 组合数学基础

?n??n??n?（2）交点总数×2＋对角线条数＝2??4?????2?????1??

??????

1-21. 试证一整数n是另一个整数的平方的充要条件是除尽n的

正整数的数目为奇数。

???（证）设n的标准分解式为n＝p1。 p2?pkn是一个完全平方数 ? ?i都是偶数 ? ?i＋1都是奇数? ??i?1???2?1????k?1?＝奇数，即n的正因子数，亦即除尽n的正整数有奇数个。

12k1-22. 统计力学需要计算r个质点放到n个盒子里去，并分别服

从下列假定之一，问有多少种不同的图象。假设盒子始终是不同的，

（1）Maxwell－Boltzmann假定：r个质点是不同的，任何盒子可以放任意个。

（2）Bose－Einstein假定：r个质点完全相同，每一个盒子可以放任意个。

（3）Fermi—Dirac假定：r个质点都完全相同，每盒不得超过一个。

（解）（1）重复排列问题，共有nr种不同图象； （2）重复组合问题，共有C?n?r?1，r?种不同图象； （3）不重复组合问题，共有C?n，r?种不同图象。 1-23. 从26个英文字母中取出6个字母组成一字，若其中有2或

3个母音，问分别可构成多少个字（不允许重复）？

1-24. 给出

?n??r??n?1??r?1??n?2??r?2???m????0?????m?1????1?????m?2????2????????????????46/51 姜建国

《组合数学》 第一章 组合数学基础

?n?m??r?m??n?r?1????0????m?????m?? ??????的组合意义。 1-25. 给出

?r??r?1??r?2??n??n?1???r?????r?????r???????r?????r?1?? ??????????的组合意义。

1-26. 证明：

?m??m??m??m?1??m??m?n?n?m???0????n?????1????n?1???????n????0???2??n?? ??????????????1-27. 对于给定的正整数n，证明在所有C(n，r)（r＝1,2, …,n）中，当

?n?1n?1,,n为奇数??22k＝? ?n，n为偶数??2k时，CnC(n，k)是最大值。

1-28.

(2n)!(3n)!（a）用组合方法证明n和nn都是整数。

2?32(n2)!（b）证明

(n!)n?1是整数。

（证）（a）方法一：把2n个不同的球放入n个相异的盒子中，

(2n)!(2n)!每个盒子中恰有2个球，其分配方案数即为＝n。

2!2!?2!2方法二：因为2n?2?2???2，所以 ???????n个47/51 姜建国

《组合数学》 第一章 组合数学基础

2n??(2n)!(2n)!?? ????n2!2!?2!?22?2?22n222x2?xn是多项式?x1?x2???xn?中x1项的系数。

方法三： 集合S??2?e1,2?e2,?,2?en?中2n个元素的

全排列的总数即为

(2n)!(2n)!?n

2!2!?2!2(3n)!(3n)!(3n)!其次，对nn，方法类似，关键是看出nn＝。

3!3!?3!2?32?3（b）仿（a），把kn个不同的球放入n个相异的盒子中，每个

(kn)!(kn)!盒子中恰有k个球，其分配方案数即为＝，但若nk!k!?k!(k!)(kn)!盒子相同，则分配方案数即为

(k!)n!n，再令k＝n，即得结果。

1-29.

（a）在2n个球中，有n个相同。求从这2n个球中选取n个的方案数。

（b）在3n＋1个球中，有n个相同。求从这3n＋1个球中选取n个的方案数。 （解）（a）视为从集合S??n?e0,e1,e2,?,en?中选取n个元素，分类统计，共有n＋1类取法：设第k类取法是指所取的n个元素中含有k个e0，n?k个其它的ei?1?i?n?（每个ei最多取一

n?k次），则此类取法共有1?Cn种?k?0,1,?,n?。所以，总的方案数为

?Ck?0nn?knk??Cn?2n k?0nn?k2n?1k＝?C2n?1 k?0nn（b）与（a）类似，方案数＝?Ck?01-30. 证明在由字母表{0，1，2}生成的长度为n的字符串中。

3n?1(a) 0出现偶数次的字符串有个；

248/51 姜建国

《组合数学》 第一章 组合数学基础

?n?n?n?n?2?n?n?q3n?1?n??????(b) ?其中q＝2. 2?2???2?,?0??2??q???2?2???????（证）（a）称满足条件的串为偶串，否则为奇串。并设满足条

件的串为 ?a1a2?an?。考虑诸ai中至少有一个为0或1的串，那么，从串的左边开始向右扫描，总是会碰到0或1，对扫描到的第一个0（或1），将其改为1（或0），从而将偶串变成了唯一的一个奇串，或将奇串变成了唯一的一个偶串。因此，在三进制串中，除了每一位都是2的偶串（22?2）之外，所有偶串与奇串一一对应，故

3n?1各有个，再加上全2的串，偶串的总数应为

2

3n?13n?1?1＝

22?n?（b）设偶串中有2k个0，则0?k???。可由两步来构造这

?2?样的n位串：

2k（1） 先在n个不同的位置放入2k个相同的0，有Cn种放法； （2） 再在其余的n?2k个位置放入1或2，其放法对应n?2k位

二进制串的个数，有2n?k个。

2kn?k所以，由乘法法则知有2k个0的偶串共有Cn2个。又知对于不同的k，相应的串之间没有重复。故由加法法则，全部偶串共有

?n?n?n?n?2?n?n?q??n????????，q?2?? 2?2???2?0??2??q????2?????????个。再结合（a），即得欲证的结论。 1-31. 5台教学仪器供m个学生使用，要求使用第1台和第2台

的人数相等，有多少种分配方案？

（解）由题目要求知5台仪器被视为是不同的。将分配过程分为三步：

2k（1）从m个学生中选出2k人，有Cm种选法；

（2）将选出的2k个学生分给1、2号仪器，且每台仪器k个

(2k)!k?C2人，有k种分法； k!k!49/51 姜建国

《组合数学》 第一章 组合数学基础

（3）将其余的m?2k名学生分给3、4、5号仪器，每台仪器所分人数不限，有3m?2k种分法。 由加法法则，总的分配方案数为

?m??0?m?m??2?m?2?m??4?m?4?m??2t?m?2t? ???????0????0??3???2????1??3?4????2??3?2t????t??3?????????????????m?其中t＝??。

?2?1-32. 由n个0及n个1组成的字符串，其任意前k个字符中，0

的个数不少于1的个数的字符串有多少？

（解）解法一：由n个1和n个0组成的2n位二进制数共有

(2n)!(n!)2个（2n个不尽相异元素的全排列） ，设所求的二进制

数共有bn个，不符合要求的数有rn个。而不合要求的数的特征是从左向右扫描时，必然在某一位首次出现0的个数大于1的个数，即从左向右累计到第2k＋1位时出现k＋1个0和k个1。此时，后2(n－k)－1位上有n－k个1，n－k－1个0。将后部分的0改写为1，1改写为0。结果整个数变成由n－1个1和n＋1个0组成的2n位数z。即一个不合要求的数唯一对应于这样的一个数z。

10000111 ? 11111000， 00011110 ? 00011111 01010110 ? 01010111， 00111001 ? 00111110 反之，给定一个由n－1个1和n＋1个0组成的2n位数z．由于0比1多2个，故一定在某一位首次出现0的累计数超过1的累计数。依同法将此位后的0与1互换，使z变成由n个1和n个0组成的2n位数。所以，这两种二进制数一一对应。即

rn故

?2n?!? ?n?1?!?n?1?!?2n?!bn??rn 2?n!??2n?!?2n?!1?2n?!1＝???C?2n,n? 22?n!??n?1?!?n?1?!n?1?n!?n?1解法二：见教材第3章。

50/51 姜建国

本文来源：https://www.bwwdw.com/article/ev5r.html