Skip to content

《组合数学》缩写(三)

第6章

加法原理的应用条件是分类后的集合是不相交的,但如果这个条件不满足呢?这就是容斥原理隆重登场的时候了。容斥原理是这样的A_1到A_n是对于需计数的集合分类后的集合,它们之间能有相交,总的元素个数就是|A_1∪A_2∪… ∪A_n| = ∑|A_i| – ∑|A_i∩A_j| + ∑|A_i∩A_j∩A_k| + …+ (-1)^m |A_1∩A_2∩…∩A_n|。它可以这样解释:首先加上所有集合的大小,然后减去每两个的集合并的大小,然后加上每三个集合的并的大小,然后减去每四个集合的并的大小,……,最后加或减所有集合的并的大小。它的证明可以通过计算某一元素对于等式每一项的贡献的方法来得到。

值得注意的是,如果和式中的每一项都需要直接计算的话,那么利用容斥原理的计算的复杂度关于n是指数级的。例如它用来计算一般的多重集的r-组合的个数就是如此。所以多重集的r-组合个数当元素的种数较多时似乎还是后面介绍的生成函数的方法更高效,它是伪多项式的。

错位排列(即元素i不在第i个位置上的排列)问题很有意思,它的特点是公式右边每一个和式里面的每一项是相同的,可以简化推导过程。最后的公式是:Dn = n! (1- 1/1! + 1/2! – … + (-1)^n 1/n!)。它有一个递推关系:D_n=(n-1)(D_(n-2) + D_(n-1)),可以组合推导。然后这个关系可以进一步简化为D_n = n D_(n-1) + (-1)^n,这个关系就不好组合推导了。

对于更一般的带有禁止位置的排列,就用一般的容斥原理就好了。

(墨比乌斯反演暂无)

第7章

算术序列就是等差数列,几何序列就是等比数列。顺便说一下,这里用a0(第0项)定义通项公式可比数学课本上用a1定义的公式优美多了。

求解递推关系是一门学问。比如说Fibonacci数的通项公式的样子很容易令第一次看到的人感到困惑。(八卦一下,我初中的时候曾经“证明”过 Fibonacci数不可能存在通项公式。呃……天才少年也有小的时候嘛……)现在的考试中似乎Fibonacci数的直接应用不多了。不过线性递推关系还是要看的。

一般的求解线性齐次递推关系的方法在此略过。

生成函数这个名字看上去有点神秘。但其实它就是将一个数列转化成一个函数的方法,定义函数的i次项的系数为a_i,就是数列a的生成函数了。将数列用这种方法表示出来可以方便处理和计算。比如说常数数列1,1,…的生成函数是1+x+x^2+……,但是利用无穷级数的求和,它同时可以表示成1/(1-x)这个很紧凑的形式,就方便接下来的处理了。

生成函数的首要用途是用来解元素的取法有限制的组合问题。比如说某元素只能取偶数个、某元素至多取b个最少取a个之类。对于每个元素的取法写成一个生成函数,就是如果能取i个x^i的系数就是1,否则为0。把所有元素的生成函数乘起来,得到的函数中x^i的系数就是取i个元素的方法数。

利用生成函数可以求解所有的常系数线性齐次递推关系。但目前还没有看到OI上的应用,所以在这里略过。

可以说,生成函数是一个模型,一个数学概念,就像“关系”“集合”这种数学上定义出来的东西一样。灵活的运用生成函数可以求解很多递推关系,比如Catalan数,还有后面讨论的很多数列。

指数生成函数是另一种生成函数。数列a的指数生成函数中x_i的系数是a_i / i!。常数列1,1,…的指数生成函数是Σx^i/i!=e^x。一般的,几何序列a_i=a^i的指数生成函数经化简是e^(ax)。它是用来解决和排列有关的问题的,典型的就是集合划分(更好理解的表达方式是涂色),例如某集合要被划分成若干个(有序的)集合,满足第一个集合的元素数是偶数,第二个集合不能少于a……这样就可以把每个集合的要求写成一个指数生成函数,然后分别化简以后乘起来就得到了通项公式。

可以看到,不管是常规生成函数还是指数生成函数,之所以用途很大就在于它可以被转化为很简单的形式方便运算(特别是乘法),还表达了原来数列的本质信息。

One Comment

  1. lycdragon wrote:

    被卡在莫比乌斯反演那里了~~~
    就是对他那一节的前面一整页的内容一直有点吃不住~~
    就是总觉得有点问题卡在那里~~没有吃透~~

    有什么在莫比乌斯这里介绍的较透彻的资料不?

    Monday, February 16, 2009 at 23:25 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*