组合数学课件：第三章 基本计数方法及应用3

1、定义3.5.1（分划或称划分,Partition） 设为n元集S的一个分划，若对i=1，2，k，S的子集Si的基数 ，则称为S的一个分划。其中Si称为分划块或分划类（由对应的等价关系的等价块、等价类而来），特别地，简称Si类为ri类。“类”必须是非空的.记作 3.5 集合的分划与第二类Stirling数定义3.5.2 设 为n元集S的(r1,r2,rn)分划，若各个分划类是可分辨的，则称 为n元集S的有序(r1,r2,rn)分划；否则称无序(r1,r2,rn)分划。例3.5.1 S=a,b,c,d, 1=a,b,c,d, 2=b,a,c,d,则1和2是S的两个不同的有序(1,1,2)分划，但是

2、它们是S的同一个无序(1,1,2)分划. 定义3.5.3一个n元集合X的全部k(无序)分划的个数叫做第二类Stirling数，记作S(n,k)或 .（第一类Stirling数记作 ）例如，集合 有7个2分划，它们是 故定理3.5.1第二类Stirling数的递推关系证明：S(n+1, k) 是集合A=a1,a2,an,an+1的k分划的个数，这些k分划可以分成两类：第1类：an+1是A的k分划中的一块，这时，只需要对集合A-an+1进行k-1分划，因此这类分划共有S(n, k-1)种 ；第2类： an+1不是A的k分划中的一块，这时，先构造A-an+1的k分划，共有S(n, k)种，然后对于A

3、-an+1的每个k分划，将an+1加入到k个块中的某一块，从而构成A的k分划，根据乘法原则，集合A的此类k分划共有kS(n, k)个。综上分析，根据加法原则，有今后可以根据定理3.5.1可以计算S(n,k)的值例如集合1,2,3,4,5的2分划数为：S(n,1)=1定理3.5.2 第二类Stirling数满足下列性质：证明：组合意义（1）S(n,2)是n元集A=a1,a2,an的2分划数.先取出a1,则对于a2,a3,an,每个元素都有两种选择，即ai(2in)与a1在同一块或者不在同一块里，不同的选择构成了集合A的不同的2分划. 但是要排除掉a2,a3,an与a1在同一块的情形（因为此时不能

4、构成A的2分划）。 所以总的分划数为2n-1-1.或将分块看作是不同的，有编号的。 1 2 空集 全集1 2,3,4 2 1,3,4. 2,3,4 21,3,4 1（2）S(n,n-1)是n元集的n-1分划，由于每个分划块都是非空的，所以每个n-1分划中必有一个分划块为2个元素，其余各块都恰有一个元素。 所以，对于n元集合的每个n-1分划，只要确定了含有两个元素的那块，整个n-1分划也就确定了. 因此， S(n,n-1)就是在n个元素中选取2个元素的方法数定理 第二类Stirling数满足：证明：S(n+1,k)是集合A=a1,a2,an,an+1的k分划数，设包含an+1的那块为B，则其余的

5、k-1块构成A-B的一个k-1分划.反过来，给定A的一个包含an+1的子集B,若|A-B|k-1,则A-B的一个k-1分划加上B就构成A的一个k分划.综上分析，按如下方案构造A的k分划：先取A的一个不包含an+1的子集C,使得|C|k-1;作出C的一个k-1分划，再加上A-C就构成了A的一个k分划，而|C|=m可以取k-1,k, ,n这些数，对于确定的m,从A中取出C,并使得|C|=m的方案数为：确定了C之后，C的k-1分划数为S(m,k-1)由加法原则和乘法原则：第一类Stirling数 第一类Stirling数也与集合的分划相关 4个元素的集合有7个2-分划，但我们要求将每个分划块做成圆排

6、列（或者轮换），则共可构成11个不同的圆排列组，如图所示 定义一个n元集合的全部k-分划所形成的不同的圆排列组的个数，即k-圆排列分划数记为第一类Stirling数，表示为 或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-圆排列

7、分划，共有 种方法，然后对于A-an的每个k-圆排列分划，将an插入该k-圆排列分划的k个圆排列中的某一个圆排列中，共有n-1种不同的插入方法，因此集合A的此类k-圆排列分划共有 个。 综上以上分析，由加法原理，有 3.6 正整数的分拆将一个正整数分成几个正整数的和定义3.6.1 正整数n的一个k分拆是把n表示成k个正整数的和，表示为： n=n1+n2+nk (k1)其中ni0(1ik)，ni叫做该分拆的分部量.如果上式是无序的，即对诸ni任意换位后的表示法都看成是一种表示法，这样的分拆叫无序分拆.否则称为有序分拆.相应的ni叫做第i个分部量. n的k分拆个数称为n的k分拆数.n的所有分拆(k

8、取遍所有可能的值)的个数称为n的分拆数.例.4=2+1+1；4=1+2+1；4 =1+1+2；是4的所有3个有序3分拆；4=2+1+1，4的唯一一个无序3分拆。定理3.6.1 正整数n的有序k分拆的个数为证明：正整数n分成k个分部量的一个有序分拆n=n1+n2+nk (k1)等价于方程x1+x2+xk=n的一组正整数解(n1,n2,nk) ,根据定理3.2.5 正整数解的个数为3.6.1 有序分拆定理3.6.2 （1）正整数n的有序k分拆，要求第i个分部量大于或等于pi，个数为（2）正整数2n分拆成k个分部，各分部量都是正偶数的有序分拆个数为（3）正整数n的有序k分拆，若n与k同为奇数或同为偶

9、数，则n的各分部量都是奇数的有序分拆数为：（1） 证明：设 是n满足条件 nipi (1ik) 的一个有序k分拆， 令 yi=ni-pi (1ik) 则 yi0 (1ik) 且满足方程： 即y1,y2,yk是上面方程的一组非负整数解. 反之，给定方程的一组非负整数解 y1,y2,yk，令ni=yi+pi (1ik)，则构成n 一个满足条件的有序k分拆. 所以，正整数n的满足条件第i个分部量大于或等于pi的有序k分拆个数为： = （2）设2n的一个有序k分拆 满足条件：xi为偶数 (1ik)， 令： 则有： 即y1,y2,yk是n的一个有序k分拆.反之，给定n的一个有序k分拆y1,y2,yk，则

10、对应的x1,x2,xk是2n的一个满足方程的偶数解数.因此，正整数2n分拆成k个分部，各分部量都是正偶数的有序分拆个数为（3）n的各分部量为奇数的分拆与n+k各分部量为偶数的分拆显然构成一一对应.n+k=(n1+1)+(n2+1)+(nk+1)根据（2）结果为3.6.2 无序分拆用B(n,k)来表示n的无序k分拆数，用B(n)表示n的所有分拆的个数，显然有： 在n的无序k分拆中，各分部量ni (ni 0,称为第i个分部量)的次序无关紧要，一般按降序排列，即：若 n=n1+n2+nk则 n1n2nk特别的，如果在n的k分拆中有ki个分部量为i(1in)，那么该分拆记为： n=k11+k22+kn

11、n或者记为：例如，B(9,5)=5，9的所有5分拆为：9=5+1+1+1+1=15+41 =4+2+1+1+1=14+12+31 =3+3+1+1+1=23+31 =3+2+2+1+1=13+22+21 =2+2+2+2+1=42+113.6.3 无序分拆的Ferrers图n的一个无序k分拆为： n=n1+n2+nk (n1n2nk)例如15的4分拆：15=5+5+3+2，相应的Ferrers为点阵：n的Ferrers图与它的无序分拆是一一对应的 如果把一个Ferrers图的各行改成列，但相对位置不变，得到的Ferrers图称为原Ferrers图的共轭Ferrers图。 例如下面就是15的4分

12、拆所对应的Ferrers图的共轭Ferrers图： 共轭Ferrers图所对应的分拆叫做原分拆的共轭分拆.上图所对应的分拆15=4+4+3+2+2是分拆15=5+5+3+2的共轭分拆. 若n的一个分拆与其共轭分拆相同，则该分拆称为n的自共轭分拆.定理3.6.4 n的k分拆的个数等于n的最大分部量为k的分拆数.证明：上面定义的分拆的共轭运算是一个映射，它将n的最大分部量为k的分拆映射到n的k分拆，这个映射是一一对应的，所以两者的数量相等.例如:24 = 25 + 33 + 51我们将重复数2，3，5分别写成2的幂次和的形式： 2 = 21， 3 = 21 + 20， 5 = 22 + 20，任何一个自然数都可表示为2的几次幂之和上面建立的映射是单射，是满射。综合以上分析，n