03-3 第三章 基本计数方法及应用3.pptx

第1页：封面

第三章基本计数方法及应用一、集合的排列和组合(§3.1 ,§3.2.1 )二、圆排列（环排列）(§3.2.1 )三、排列和组合的生成(§3.2.2 )四、多重集的排列和组合(§3.3 )五、二项式系数(§3.4 )六、Stirling数(§3.5 )七、分拆问题(§3.6 )八、分配问题(§3.7 )

第2页：集合的分划与第二类内容导览

§3.5集合的分划与Stirling数§3.5.1集合的分划与第二类Stirling数1,集合的分划的定义

第3页：3.其中每个Si称为一个分划块

3.其中每个Si称为一个分划块，也把这个k-分划记为：定义3.5.1集合S的子集族称为n元集S的一个k-分划，如果这个子集族满足1.每个Si非空；

2.当i≠j时，

第4页：例3.5.1 集合A={

例3.5.1集合A={1,,3,4}的2-分划有7个，它们是：

第5页：定义3.5.2 一个n元集合的全部k

定义3.5.2一个n元集合的全部k-分划的个数记为第二类Stirling数，表示为或S2(n,k)2，第二类Stirling数

第6页：（1）（2）几条性质

（1）（2）几条性质：

第7页：证明等式左边是集合的k-分划

证明等式左边是集合的k-分划的个数，这些k-分划可以分成两类：第1类：{an}是A的k-分划中的一块，这时，只需对集合A-{an}进行(k–1)-分划，再加上{an}这一块，就构成了A的k-分划，因此，这类分划有个定理3.5.1第二类Stirling数满足如下递推关系

第8页：第2类：{an}不是A的k-分划

• 第2类：{an}不是A的k-分划中单独的一块，此时，先构造A-{an}的k-分划，共有种方法
• 然后，对于A-{an}的每个k-分划，将an加到该k-分划的k个块中的某一块，从而构成A的k-分划
• 因此由乘法原理，集合A的此类k-分划共有个
• 综上以上，由加法原理

第9页：

本页源文件未提取到正文文字，仅有图片。该页位于「第2类：{an}不是A的k-分划」与「定理3.5.2（1） （2）」之间，建议对照原课件图片补充本页要点说明。

第10页：定理3.5.2（1） （2）

定理3.5.2（1）（2）

第11页：证明由定理3.5.1中的递推关系

证明由定理3.5.1中的递推关系，有（1）

第12页：证明由定理3.5.1中的递推关系（续）

证明由定理3.5.1中的递推关系（续）：（2）

第13页：这两条性质也可以用组合意义来解释

• 这两条性质也可以用组合意义来解释：（1）是n元集合的2-分划数，先取出a1,则对于a2,a3,…, an，每个元素都有两种选择，即与a1在同一块里或者ai与a1不在同一块里，不同的选择就构成了集合A的不同的2-分划，但这里要排除掉a2,a3,…,an，都与a1在同一块中的情形（此时不构成集合A的2-分划
• 由此可知，n元集合A的2-分划数为2n-1-1

第14页：（2）是n元集合的(n-1)-分

• （2）是n元集合的(n-1)-分划，由于分划中各块是非空的，所以每个(n-1)-分划中必有一块为两个元素，其余各块都恰有一个元素，所以，对于n元集合的每个(n-1)-分划，只要确定了有两个元素的那一块，整个(n-1)-分划就确定了
• 因此，就是在n元集中选取2个元素的方法数

第15页：第一类Stirling数

• §3.5.2第一类Stirling数
• 第一类Stirling数也与集合的分划相关
• 集合有7个2-分划，但我们要求将每个分划块做成圆排列（或者轮换），则共可构成11个不同的圆排列组，如图3.5.1所示

第16页：

本页源文件未提取到正文文字，仅有图片。该页位于「第一类Stirling数」与「定义3.5.3 一个n元集合的全部k」之间，建议对照原课件图片补充本页要点说明。

第17页：定义3.5.3 一个n元集合的全部k

定义3.5.3一个n元集合的全部k-分划所形成的不同的圆排列组的个数，即k-圆排列分划数记为第一类Stirling数，表示为或S1(n,k)性质(1)性质(2)性质(3)性质(4)

第18页：定理3.5.3 第一类Stirling数

定理3.5.3第一类Stirling数满足如下递推关系证明：等式左边是将集合的k-圆排列分划数，这些圆排列组可以分成两类：第1类：{an}单独构成一个圆排列，只需对集合A-{an}进行(k-1)-圆排列分划，再加上{an}这个圆排列，就构成了A的k-圆排列分划，因此，这类分划有个。

第19页：第2类：{an}不是A的k-

第2类：{an}不是A的k-圆排列分划中的单独一个圆排列，此时，先构造A-{an}的k-圆排列分划，共有种方法，然后对于A-{an}的每个k-圆排列分划，将an插入该k-圆排列分划的k个圆排列中的某一个圆排列中，共有n-1种不同的插入方法，因此集合A的此类k-圆排列分划共有个。

综上以上分析，由加法原理，有

第20页：正整数的分拆概述

• §3.6正整数的分拆
• 正整数的分拆，就是把一个正整数表成若干个正整数之和。
• 整数分拆成若干整数的和，办法不一，不同拆分法的总数叫做分拆数。

第21页：定义3.6.1 正整数n的一个k-分拆是

• 定义3.6.1正整数n的一个k-分拆是把n表示成k个正整数的和，即（3.6.1）的形式
• 其中，叫做该分拆的分部
• 如果表达式（3.6.1）是无序的，叫做无序分拆，或简称为分拆

第22页：若表达式

• 若表达式（3.6.1）是有序的，即表达式（3.6.1）右边的和不仅与各项的数值有关，而且与各项的顺序有关，
• 这样的分拆叫做有序分拆
• 相应的，叫做该有序分拆的第i个分部，
• n的k-分拆的个数称为n的k-分拆数，
• n的所有分拆的个数称为n的分拆数。

第23页：例如：4=

例如：4=4，4=1+3，4=3+1，4=2+2，4=2+1+1，4=1+2+1，4=1+1+2，4=1+1+1+1是4的所有有序分拆，对于4的有序3-分拆4=2+1+1而言，第1个分部为2，第2个和第3个分部均为1。

若考虑无序分拆，则4有如下5个无序分拆，4=4，4=1+3，4=2+2，4=2+1+1，4=1+1+1+1

第24页：有序分拆

§3.6.1有序分拆定理3.6.1正整数n的有序k-分拆个数为证明正整数n分成k个分部的一个有序分拆等价于方程的一组正整数解由定理3.3.4正整数n的有序k分拆个数为

第25页：定理3.6.2（1） 正整数n的有序k-

定理3.6.2（1）正整数n的有序k-分拆，要求第i个分部大于等于pi，分拆个数为（2）正整数2n分拆成k个分部，各分部都是正偶数的有序分拆个数为

第26页：证明（1）设

证明（1）设（3.6.2）是n满足条件（3.6.3）的一个有序k-分折，令则且满足方程（3.6.4）即是方程（3.6.4）的一组非负整数解。

第27页：反之，若给定方程

反之，若给定方程（3.6.4）的一组非负整数解令则构成n的一个有序k-分拆（3.6.2），且满足条件（3.6.3）。

所以，n的满足条件（3.6.3）的有序k-分拆与方程（3.6.4）的非负整数解之间构成一一对应，由定理3.3.3可知，其个数为

第28页：（2）设2n的一个有序k-分拆满

（2）设2n的一个有序k-分拆满足条件（3.6.5）令，则有即是n的一个有序k-分折。

反之，是n的一个有序k-分拆，令，则是2n的一个满足条件（3.6.5）的有序k-分拆。

所以，2n满足条件（3.6.5）的有序k-分拆数等于n的有序k-分拆数，为

第29页：无序分拆与Ferrers图

§3.6.2无序分拆与Ferrers图来表示n的k分拆的个数。

来表示n的所有分拆个数。

1，无序分拆

第30页：几个性质

几个性质（1）（2）

第31页：Ferrers图

• Ferrers图，设n的一个k-分拆为（3.6.8）我们在水平直线上画个点，在其下面一条直线上画个点，且使这两条直线上的第一个点在同一条竖线上，其他点依次与上一行的点对齐；依此类推，最后在第k条直线上画个点，第一个点与前面各行的第一个点均在同一条竖线上，其他点依次与上面各行的点对齐，
• 这样得到的点阵叫做n的k-分拆（3.6.8）的Ferrers图。2，无序分拆的Ferrers图

第32页：共轭Ferrers图所对应

共轭Ferrers图所对应的分拆叫做原分拆的共轭分拆

第33页：定理3.6.3 n的k-分拆的个数等

定理3.6.3n的k-分拆的个数等于n的最大分部为k的分拆数证明上面定义的分拆的共轭运算是一个映射，它将n的最大分部为k的分拆映射到n的k-分拆，例如，分拆（3.6.9）是12的最大分部为5的分拆，其共轭分拆（3.6.10）是12的一个5分拆，并且这个映射显然是一一的，所以两者相等。

第34页：若n的一个分拆与其轭分拆相同

若n的一个分拆与其轭分拆相同，则该分拆称为n的自共轭分拆。

第35页：定理3.6.4 n的自共轭分拆的个数

定理3.6.4n的自共轭分拆的个数等于n的各分部都是奇数且两两不等的分拆的个数。

证明我们将借助于Ferrers图建立一个n的各分部为奇数且两两不等的分拆到n的自轭分拆之间的一一对应。

设n的一个分部为奇数且两两不等的分拆为（3.6.11）

第36页：其中由n的分拆

• 其中由n的分拆（3.6.11），我们构造n的一个自共轭分拆的Ferrers图。
• 在第1行与第1列都画n1+1个点，共有2n1+1个点；
• 画完第1行和第1列后，在第2行与第2列再各画n2+1个点，共2n2+1个点；
• ……；
• 在第k行与第k列再画nk+1个点，共2nk+1个点，

第37页：因为所以如此画出的n个点的点

• 因为所以如此画出的n个点的点阵图的每一行都不比下一行的点数少
• 因而是n的一个分拆的Ferrers图，且由上面的构造过程知道，该Ferrers图一定是对称的，当然其对应的分拆是自共轭的。
• 显然，上面建立的n的分部为奇数且两两不等的分拆与n的自共轭分拆之间的对应关系是一一的
• 所以定理的结论成立。

第38页：定理3.6.5 n的分部两两不等的分

定理3.6.5n的分部两两不等的分拆数等于n的各分部量都是奇数的分拆数。

证明我们采用的方法仍然是建立两类不同的分拆之间的一一对应。

在一个n的各分部均为奇数的分拆中，假设数2k+1出现p次，我们将p写成2的幂次和的形式：根据数论的知识，这种表示法是唯一的。

第39页：我们将n的这个分拆的Ferr

• 我们将n的这个分拆的Ferrers图中这个小点按下列方法重排：各行的小点数分别为
• 然后再将各行按小点数递减的顺序排列，就得到n的另一个分拆的Ferrers图。
• 在新的Ferrers图中，各行的点数为的形式，在各行点数的表达式中，参数k和i中必有一个不同

第40页：所以各行的点数互不相同

• 所以各行的点数互不相同，因而它所对应的分拆的各分部不同。
• 显然，上述建立了两类分拆之间的一一对应。
• 因此，n的分部两两不等的分拆的个数等于n的分部都是奇数的分拆的个数。

第41页：分配问题

• §3.7分配问题
• 所谓分配问题，就是把一些球放入一些盒子中的放法问题
• 分配问题的一般陈述为，把n个球分放到k个盒子里，共有多少种不同的方案？我们假定球在盒内是无序的，但需要考虑如下三个因素：1）n个球是完全相同的还是完全不同的；2）k个盒是完全相同的是完全不同的；3）是否允许有空盒。