组合数学（二）VIP免费

组合数学（二）李子星内容提要•容斥原理•递推关系与母函数与矩阵快速幂•特殊计数–Catalan数–Stirling数–Bell数容斥原理【问题一】某大班有n个学生，选了课程A的学生有a个，选了课程B的学生有b个，有c人既选了课程A又选了课程B，问有多少人两门课都没选。容斥原理选了A的选了B的AB都选了的AB都没选的由上图易知，结果应该是：n-a-b+c容斥原理如果用表示选了课程A的学生的集合，用表示选了课程B的学生的集合，同时选了课程A和B的学生的集合则是选了课程A或课程B的学生的集合就是于是：ABABABABABAB容斥原理如果有三门课程呢？ABCABACBCABCABCABCABACBCABC容斥原理如果有n门课程呢？结论就是容斥原理了。容斥原理容斥原理简而言之就是这样一个公式：112123112112132121211123111111111111211xxxnnnnnnniiiiiiiiiiiiiiinnnxiiiiiiiinnAAAAAAAAAAAAAAAA………………………………容斥原理易知此公式中第x个和式共包含项所以等号右边一共是项xnC21n容斥原理【问题二】对于一个正整数x，若x是2的倍数、或是3的倍数、或是5的倍数，那么x是一个幸运数。问在1~n这n个正整数中，有多少个幸运数。容斥原理设1~n中所有2的倍数在A2集合中，3的倍数在A3集合中，5的倍数在A5集合中问题便是求：而：所以最终的结果就是：n/2+n/3+n/5-n/6-n/10-n/15+n/30235AAA/gcd(,)/iijijijAniAAA容斥原理【问题三】错排问题对于1~n的任意一个排列，若对任意的i有：排列中的第i项不是i，则称这个排列是一个“错排”。问1~n的全排列中有多少个错排。容斥原理假设第i位正好是i的所有排列在集合中，那么易知：于是关键就是根据容斥原理计算减去的那一部分了。iA12!nnAAA错排数……容斥原理而在错排问题中，易知：于是：12x!iiiAAAnx……1201121111111!12!1!1!1!!!!1!1!2!3!!!nnnxnxnnninniAAACnCnCnxCnnnnnnnni……………………递推关系与母函数母函数即生成函数，是组合数学中尤其是计数方面的一个重要理论和工具。瑞士数学家雅各布·伯努利在考虑当投掷n粒骰子时，加起来点数总和等于m的可能方式的数目这个问题时首先使用了母函数方法，并得出可能的数目是(x+x2+x3+x4+x5+x6)n的展开式中xm这一项的系数。递推关系与母函数母函数有很多种，包括：•普通母函数•指数母函数•泊松母函数•L级数母函数•贝尔级数母函数•狄利克雷级数母函数递推关系与母函数普通母函数简而言之就是：对你关注的数列f(n)，构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)。递推关系与母函数【问题四】我们要从苹果、香蕉、橘子和梨中拿一些水果出来，要求苹果只能拿偶数个，香蕉的个数要是5的倍数，橘子最多拿4个，梨要么不拿，要么只能拿一个。问按这样的要求拿n个水果的方案数。递推关系与母函数实际上符合要求的方案数就应该是展开后的系数。可以看出这里的值本身没有意义，是多少也完全不用在乎，需要在乎的只是的形式，即各项的指数和系数。指数对水果的个数，系数则是方案数。02405100123401gxxxxxxxxxxxxxx…………nxgxxgx递推关系与母函数母函数的中心思想就是这样的。它就是这样一个工具。母函数本身就像是个“模具”，它并不能直接给出我们想要“铸造”的结果，但是结果可以在这个“模具”之中展现出来。一旦展现，只要想办法从中“取出”结果就可以了。母函数就是一列用来展示一串数字的挂衣架——赫伯特·维尔夫递推关系与母函数【问题五】问有多少个非负整数解。123mxxxxn……递推关系与母函数运用同样的思想，可知其非负整数解应该有中的系数个解。012mgxxxx……nx递推关系与母函数我们都知道但若n不是正整数呢？实际上这样写就与n是不是正整数无关了。这就是广义组合数的定义。!!!...