组合数学ch03-3

1、第三章 基本计数方法及应用,一、集合的排列和组合(3.1 ,3.2.1 ) 二、圆排列（环排列） (3.2.1 ) 三、排列和组合的生成 (3.2.2 ) 四、多重集的排列和组合(3.3 ) 五、二项式系数 (3.4 ) 六、Stirling数 (3.5 ) 七、分拆问题 (3.6 ) 八、分配问题 (3.7 ),3.5 集合的分划与Stirling数,3.5.1 集合的分划与第二类Stirling数,1, 集合的分划的定义,3. 其中每个Si称为一个分划块，也把这个k-分划记为：,定义3.5.1 集合S的子集族 称为n元集S的一个k-分划，如果这个子集族满足 每个Si非空； 当ij时，,例3

2、.5.1 集合A=1,3,4 的2-分划,有7个，它们是：,定义3.5.2 一个n元集合的全部k-分划的个数记为第二类Stirling数，表示为 或 S2(n,k),2，第二类Stirling数,（1）,（2）,几条性质：,证明 等式左边 是集合 的k-分划的个数，这些k-分划可以分成两类： 第1类：an是A的k-分划中的一块，这时，只需对集合A -an进行(k1)-分划，再加上an这一块，就构成了A的k-分划，因此，这类分划有 个,定理3.5.1 第二类Stirling数 满足如下递推关系,第2类： an不是A的k-分划中单独的一块，此时，先构造A -an的k-分划， 共有 种方法 然后，对

3、于A -an的每个k-分划，将an加到该k-分划的k个块中的某一块，从而构成A的k-分划 因此由乘法原理，集合A的此类k-分划共有 个 综上以上，由加法原理,定理3.5.2,（1）,（2）,证明 由定理3.5.1中的递推关系，有,（1）,（2）,这两条性质也可以用组合意义来解释：,（1）,是n元集合 的2-分划,数，先取出a1,则对于 a2,a3, an，每个元素都有两种选择，即 与a1在同一块里或者ai与a1不在同一块里，不同的选择就构成了集合A的不同的2-分划，但这里要排除掉a2,a3, an，都与a1在同一块中的情形（此时不构成集合A的2-分划,由此可知，n元集合A的2-分划数为2n-1

4、-1,（2） 是n元集合的(n-1)-分划，由于分划中各块是非空的，所以每个(n-1)-分划中必有一块为两个元素，其余各块都恰有一个元素，所以，对于n元集合的每个(n-1)-分划，只要确定了有两个元素的那一块，整个(n-1)-分划就确定了 因此， 就是在n元集中选取2个元素的方法数,3.5.2 第一类Stirling数,第一类Stirling数也与集合的分划相关 集合有7个2-分划，但我们要求将每个分划块做成圆排列（或者轮换），则共可构成11个不同的圆排列组，如图3.5.1所示,定义3.5.3 一个n元集合的全部k-分划所形成的不同的圆排列组的个数，即k-圆排列分划数记为第一类Stirling

5、数，表示为 或S1(n,k),性质(1) 性质(2) 性质(3) 性质(4),定理3.5.3 第一类Stirling数满足如下递推关系,证明：等式左边 是将集合的k-圆排列分划数，这些圆排列组可以分成两类： 第1类：an单独构成一个圆排列，只需对集合A-an进行(k-1)-圆排列分划，再加上an这个圆排列，就构成了A的k-圆排列分划，因此，这类分划有 个。,第2类： an不是A的k-圆排列分划中的单独一个圆排列，此时，先构造A-an的k-圆排列分划，共有 种方法，然后对于A-an的每个k-圆排列分划，将an插入该k-圆排列分划的k个圆排列中的某一个圆排列中，共有n-1种不同的插入方法，因此集合

6、A的此类k-圆排列分划共有 个。 综上以上分析，由加法原理，有,3.6 正整数的分拆,正整数的分拆，就是把一个正整数表成若干个正整数之和。,整数分拆成若干整数的和，办法不一，不同拆分法的总数叫做分拆数。,定义3.6.1 正整数n的一个k-分拆是把n表示成k个正整数的和，即 （3.6.1） 的形式 其中 ， 叫做该分拆的分部 如果表达式（3.6.1）是无序的，叫做无序分拆，或简称为分拆,若表达式（3.6.1）是有序的，即表达式（3.6.1）右边的和不仅与各项的数值有关，而且与各项的顺序有关， 这样的分拆叫做有序分拆 相应的，叫做该有序分拆的第i个分部， n的k-分拆的个数称为n的k-分拆数， n

7、的所有分拆的个数称为n的分拆数。,例如：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,3.6.1 有序分拆 定理3.6.1正整数n的有序k-分拆个数为,证明 正整数n分成k个分部的一个有序分拆 等价于方程 的一组正整数解 由定理3.3.4正整数n的有序k分拆个数为,定理3.6.2 （1）正整数n的有序k-

8、分拆，要求第i个分部大于等于pi，分拆个数为 （2）正整数2n分拆成k个分部，各分部都是正偶数的有序分拆个数为,证明（1）设 （3.6.2） 是n满足条件 （3.6.3） 的一个有序k-分折，令 则 且满足方程 （3.6.4） 即是方程（3.6.4）的一组非负整数解。,反之，若给定方程（3.6.4）的一组非负整数解 令 则构成n的一个有序k-分拆（3.6.2），且满足条件（3.6.3）。 所以，n的满足条件（3.6.3）的有序k-分拆与方程（3.6.4）的非负整数解之间构成一一对应，由定理3.3.3可知，其个数为,（2）设2n的一个有序k-分拆 满足条件 （3.6.5） 令 ，则有 即 是n的

9、一个有序k-分折。 反之， 是n的一个有序k-分拆，令 ，则是2n的一个满足条件（3.6.5）的有序k-分拆。 所以，2n满足条件（3.6.5）的有序k-分拆数等于n的有序k-分拆数，为,3.6.2 无序分拆与Ferrers图,来表示n的k分拆的个数。,来表示n的所有分拆个数。,1，无序分拆,几个性质,（1）,（2）,Ferrers图，设n的一个k-分拆为 （3.6.8） 我们在水平直线上画 个点，在其下面一条直线上画 个点，且使这两条直线上的第一个点在同一条竖线上，其他点依次与上一行的点对齐；依此类推，最后在第k条直线上画 个点，第一个点与前面各行的第一个点均在同一条竖线上，其他点依次与上面

10、各行的点对齐， 这样得到的点阵叫做n的k-分拆（3.6.8）的Ferrers图。,2，无序分拆的Ferrers图,共轭Ferrers图所对应的分拆叫做原分拆的共轭分拆,定理3.6.3 n的k-分拆的个数等于n的最大分部为k的分拆数,证明 上面定义的分拆的共轭运算是一个映射，它将n的最大分部为k的分拆映射到n的k-分拆，例如，分拆（3.6.9）是12的最大分部为5的分拆，其共轭分拆（3.6.10）是12的一个5分拆，并且这个映射显然是一一的，所以两者相等。,若n的一个分拆与其轭分拆相同，则该分拆称为n的自共轭分拆。,定理3.6.4 n的自共轭分拆的个数等于n的各分部都是奇数且两两不等的分拆的个数

11、。,证明 我们将借助于Ferrers图建立一个n的各分部为奇数且两两不等的分拆到n的自轭分拆之间的一一对应。 设n的一个分部为奇数且两两不等的分拆为 （3.6.11）,其中 由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个点，,因为 所以如此画出的n个点的点阵图的每一行都不比下一行的点数少 因而是n的一个分拆的Ferrers图，且由上面的构造过程知道，该Ferrers图一定是对称的，

12、当然其对应的分拆是自共轭的。 显然，上面建立的n的分部为奇数且两两不等的分拆与n的自共轭分拆之间的对应关系是一一的 所以定理的结论成立。,定理3.6.5 n的分部两两不等的分拆数等于n的各分部量都是奇数的分拆数。,证明 我们采用的方法仍然是建立两类不同的分拆之间的一一对应。 在一个n的各分部均为奇数的分拆中，假设数2k+1出现p次，我们将p写成2的幂次和的形式： 根据数论的知识，这种表示法是唯一的。,我们将n的这个分拆的Ferrers图中这 个小点按下列方法重排： 各行的小点数分别为 然后再将各行按小点数递减的顺序排列，就得到n的另一个分拆的Ferrers图。 在新的Ferrers 图中，各行的点数为 的形式，在各行点数的表达式 中，参数k和i中必有一个不同,所以各行的点数互不相同，因而它所对应的分拆的各分部不同。 显然，上述建立了两