组合数学ch03-3.ppt

第三章基本计数方法及应用,一、集合的排列和组合(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.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-分划，共有种方法然后，对于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-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数，表示为或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种不同的插入方法，因此集合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的所有分拆的个数称为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-分拆，要求第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的一个有序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条直线上画个点，第一个点与前面各行的第一个点均在同一条竖线上，其他点依次与上面各行的点对齐，这样得到的点阵叫做n的k-分拆（3.6.8）的Ferrers图。,2，无序分拆的Ferrers图,共轭Ferrers图所对应的分拆叫做原分拆的共轭分拆,定理3.6.3n的k-分拆的个数等于n的最大分部为k的分拆数,证明上面定义的分拆的共轭运算是一个映射，它将n的最大分部为k的分拆映射到n的k-分拆，例如，分拆（3.6.9）是12的最大分部为5的分拆，其共轭分拆（3.6.10）是12的一个5分拆，并且这个映射显然是一一的，所以两者相等。,若n的一个分拆与其轭分拆相同，则该分拆称为n的自共轭分拆。,定理3.6.4n的自共轭分拆的个数等于n的各分部都是奇数且两两不等的分拆的个数。,证明我们将借助于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图一定是对称的，当然其对应的分拆是自共轭的。显然，上面建立的n的分部为奇数且两两不等的分拆与n的自共轭分拆之间的对应关系是一一的所以定理的结论成立。,定理3.6.5n的分部两两不等的分拆数等于n的各分部量都是奇数的分拆数。,证明我们采用的方法仍然是建立两类不同的分拆之间的一一对应。在一个n的各分部均为奇数的分拆中，假设数2k+1出现p次，我们将p写成2的幂次和的形式：根据数论的知识，这种表示法是唯一的。,我们将n的这个分拆的Ferrers图中这个小点按下列方法重排：各行的小点数分别为然后再将各行按小点数递减的顺序排列，就得到n的另一个分拆的Ferrers图。在新的Ferrers图中，各行的点数为的形式，在各行点数的表达式中，参数k和i中必有一个不同,所以各行的点数互不相同，因而它所对应的分拆的各分部不同。显然，上述建立了两类分拆之