组合数学第三章(3)

2020/11/6计算机科学与技术学院1§3.5.1集合的分划与第二类Stirling数定义3.5.1集合S的子集族称为n元集S的一个k-分划，如果这个子集族满足1.每个Si非空；2.当i≠j时，3.其中每个Si称为一个分划块，也把这个k-分划记为：}{21k，S，，SSijSS集合的分划与Stirling数kSSSS21kSSSS212020/11/6计算机科学与技术学院2第二类Stirling数定义3.5.3一个n元集合的全部k分划的个数叫做第二类Stirling数，记作2(,)Snk或nk。例如，集合{1,2,3,4}A有7个2分划，它们是{1,2,3,4}{1}{2,3,4}{2}{1,3,4}{3}{1,2,4}{4}{1,2,3}{1,2}{3,4}{1,3}{2,4}{1,4}{2,3}故2(4,2)7S，在A的2分划{1,4}{2,3}A中，{1,4}与{2,3}是该2分划的两个块。2020/11/6计算机科学与技术学院3第二类Stirling数由2(,)Snk的定义易知：（1）2(,1)1Sn；（2）2(,)1Snn；（3）2(,)0()Snkkn；（4）2(,0)0,(0)Snn。2(,)Snk是一个重要的计数函数，对任何正整数n和k，2(,)Snk均有意义。2020/11/6计算机科学与技术学院4第二类Stirling数定理3.5.1第二类Stirling数2(,)Snk递推关系222(1,)(,1)(,)(1)SnkSnkkSnkkn。证明2(1,)Snk是集合121{,,,,}nnAaaaa的k分划的个数，这些k分划可以分成两类：第（1）类：1{}na是A的k分划中的一块，这时，只需对集合1{}nAa进行k–1分划，再加上1{}na这一块，就构成了A的k分划，因此，这类分划有2(,1)Snk。第（2）类：1{}na不是A的k分划中单独的一块，此时，先构造1{}nAa的k分划，共有2(,)Snk种方法，然后，对于1{}nAa的每个k分划，将1na加到该k分划的k个块中的某一块，从而构成A的k分划，因此，由乘法原则，集合A的此类k分划共有2(,)kSnk个。综上以上分析，由加法原则，有222(1,)(,1)(,)SnkSnkkSnk。2020/11/6计算机科学与技术学院5第二类Stirling数定理3.5.1的证明过程给出了构造所有k分划的方法。由定理3.5.1中的递推关系可以计算出任何2(,)Snk的值，例如集合{1,2,3,4,5}的2分划数为222(5,2)(4,1)2(4,2)12715,SSS2020/11/6计算机科学与技术学院6第二类Stirling数2020/11/6计算机科学与技术学院7第二类Stirling数定理3.5.2第二类Stirling数2(,)Snk满足下列性质：（1）12(,2)21nSn；（2）2(,1)2nSnn。证明:（1）由定理3.5.1中的递推关系，有2222222221(,2)(1,1)2(1,2)12[(2,1)2(2,2)]124(2,2)1222(2,2)21.nnSnSnSnSnSnSnS2020/11/6计算机科学与技术学院8第二类Stirling数组合意义（1）(,2)Sn是n元集合12{,,,}nAaaa的2分划数，先取出1a，则对于23,,,naaa，每个元素都有两种选择，即(2)iain与1a在同一块里或者ia与1a不在同一块里，不同的选择就构成了集合A的不同的2分划，但这里要排除掉23,,,naaa，都与1a在同一块中的情形（此时不构成集合A的2分划），由此可知，n元集合A的2分划数为121n。2020/11/6计算机科学与技术学院9第二类Stirling数（2）222222(,1)(1,2)(1)(1,1)(2,3)(2)(2,2)(1)(2,1)23(1)123(1)1(1)2.2SnnSnnnSnnSnnnSnnnSnnnnn2020/11/6计算机科学与技术学院10第二类Stirling数组合意义（2）2(,1)Snn是n元集合的n-1分划，由于分划中各块是非空的，所以每个n-1分划中必有一块为两个元素，其余各块都恰有一个元素，所以，对于n元集合的每个n-1分划，只要确定了有两个元素的那一块，整个n-1分划就确定了，因此，2(,1)Snn就是在n元集中选取2个元素的方法数2n。2020/11/6计算机科学与技术学院11作业3.20证明：（1）121,3(31)22nnSn（2）2,2334nnSnn；（3）2,31015.456nnnSnn2020/11/6计算机科学与技术学院12•第一类Stirling数也与集合的分划相关•集合有A={1,2,3,4}7个2-分划，但我们要求将每个分划块做成圆排列(或者轮换)，则共可构成11个不同的圆排列组,图示见书63页第一类Stirling数2020/11/6计算机科学与技术学院132020/11/6计算机科学与技术学院14定义3.5.3一个n元集合的全部k-分划所形成的不同的圆排列组的个数，即k-圆排列分划数记为第一类Stirling数，表示为或S1(n,k)kn性质(1)性质(2)性质(3)性质(4))!1(1nn1nn)(0nkkn21nnn2020/11/6计算机科学与技术学院15定理3.5.3第一类Stirling数满足如下递推关系),1()1()1,1(),()1(1)1(11111knSnknSknSnkknnknkn第一类Stirling数2020/11/6计算机科学与技术学院16证明：等式左边是将集合的k-圆排列分划数，这些圆排列组可以分成两类：第1类：{an}单独构成一个圆排列，只需对集合A-{an}进行(k-1)-圆排列分划，再加上{an}这个圆排列，就构成了A的k-圆排列分划，因此，这类分划有个。kn11kn第一类Stirling数2020/11/6计算机科学与技术学院17第2类：{an}不是A的k-圆排列分划中的单独一个圆排列，此时，先构造A-{an}的k-圆排列分划，共有种方法，然后对于A-{an}的每个k-圆排列分划，将an插入该k-圆排列分划的k个圆排列中的某一个圆排列中，共有n-1种不同的插入方法，因此集合A的此类k-圆排列分划共有个。综上以上分析，由加法原理，有kn1knn1)1(knnknkn1)1(112020/11/6计算机科学与技术学院18小结：S2(n,k)vs.S1(n,k)S2(n,1)=1S2(n,n)=1S2(n,n-1)=C(n,2)S2(n,k)=0(kn)S2(n+1,k)=S2(n,k-1)+kS2(n,k)S2(n,k)的生成函数为S1(n,1)=(n-1)!S1(n,n)=1S1(n,n-1)=C(n,2)S1(n,k)=0(kn)S1(n+1,k)=S1(n,k-1)+nS1(n,k)S1(n,k)的生成函数为P(x,n)(1)(12)(1)kxxxkx2020/11/6计算机科学与技术学院19正整数的分拆正整数的分拆就是将一个正整数分成几个正整数的和，分拆问题也是组合论的重要内容之一。定义3.6.1正整数n的一个k分拆是把n表示成k个正整数的和12(1)knnnnk（3.6.1）的一种表示法，其中0(1)inik，in叫做该分拆的分部量。2020/11/6计算机科学与技术学院20正整数的分拆如果表达式（3.6.1）是无序的，也就是说，对诸in任意换位后的表示法都只视为一种表示法，这样的分拆叫做无序分拆，或简称为分拆。若表达式（3.6.1）是有序的，即表达式（3.6.1）右边的和不仅与各项的数值有关，而且与各项的次序有关，不同的次序认为是不同的表示法，这样的分拆叫做有序分拆，这时，in叫做该有序分拆的第i个分部量，n的k分拆的个数称为n的k分拆数，n的所有分拆（k取遍所有可能的值）的个数称为n的分拆数。2020/11/6计算机科学与技术学院21正整数的分拆例如：4=2+1+1=1+2+1=1+1+2是4的所有3个有序3分拆，在4的第一个有序3分拆中，第1个分部量为2，第2个和第3个分部量均为1，而4=2+1+1是4的唯一一个3（无序）分拆。2020/11/6计算机科学与技术学院22有序无序不允许重复4=4，4=1+3，4=3+14=4，4=1+3允许重复4=4，4=1+3，4=3+14=2+2，4=2+1+1，4=1+2+14=1+1+2，4=1+1+1+14=4，4=1+34=2+2，4=1+1+24=1+1+1+14的分拆正整数的分拆2020/11/6计算机科学与技术学院23正整数的分拆集合的（无序）分划A={a,b,c,d}A={a,b}∪{c}∪{d}={a,c}∪{b}∪{d}={a,d}∪{b}∪{c}={b,c}∪{a}∪{d}={b,d}∪{a}∪{c}={c,d}∪{a}∪{b}S2(4,3)=C(4,2)=6A={1,1}∪{1}∪{1}B(4,3)=12020/11/6计算机科学与技术学院24有序分拆定理3.6.1正整数n的有序k分拆的个数为11nk。证明正整数n分成k个分部量的一个有序分拆12knnnn等价于方程12kxxxn的正整数解12()knnn，由3.3节定理3.2.5的证明知，正整数n的有序k分拆的个数为11nk。由定理3.2.5和定理3.6.1知，正整数n的有序k分拆数等于多重集合12{,,}kMaaa的12,,,kaaa至少出现一次的n组合数，均为11nk。2020/11/6计算机科学与技术学院25有序分拆12knnnn12(1)(1)(1)knknnn1111nkknkk2020/11/6计算机科学与技术学院26有序分拆定理3.6.2（1）正整数n的有序k分拆，要求第i的分部量大于等于ip，其个数为111kiinkpk；2020/11/6计算机科学与技术学院2712knnnn11221()()()kikkinpnpnpnp111kiinpkk2020/11/6计算机科学与技术学院28有序分拆证明（1）设12knnnn（3.6.2）是n满足条件(1)iinpik（3.6.3）的一个有序k分折，令(1)iiiynpik，则0(1)iyik，且满足方程1211221()()()kkkkiiyyynpnpnpnp，即12,,,kyyy是上式的一组非负整数解。2020/11/6计算机科学与技术学院29有序分拆反之，若给定方程（3.6.4）的一组非负整数解12,,,kyyy，令(1)iiinypik，则构成n的一个有序k分拆（3.6.2），且满足条件（3.6.3）。所以，n的满足条件（3.6.3）的有序k分拆与方程（3.6.4）的非负整数解之间构成一一对应，由定理3.2.4的证明知，其个数为111kiinkpk202