函数真题全集

生成函数(也叫“生成函数”)就是构造这样一个多项式函数g(x)，使得x的n次方的系数为f(n)。

生成函数最奇妙的地方在于，有些生成函数可以化简为一个非常简单的函数。也就是说，并不是每一个生成函数都用一长串多项式来表示。比如这个函数f(n)=1 (n当然属于自然数)，那么它的生成函数应该是g(x)= 1+x+x ^ 2+x ^ 3+x ^ 4+...(每一项都是一，即使n=0，也有x ^ 0。仔细一看，这是一个无穷项的几何级数求和。如果-1

我们举个例子，说明一些实际的组合问题也可以用这样一个简单的函数来表示。

考虑一下这个问题:从二班选N MM有几种方法？学过简单排列组合的同学都知道答案是C(4，n)。也就是说。从n=0开始，问题的答案是1，4，6，4，1，0，0，...(当然从4 MM中选4人以上的方案数为0)。那么它的生成函数g(x)应该是G (x) = 1+4x+6x 2+4x 3+x 4。这不是...二项式展开？所以g (x) = (1+x) 4。

你大概应该知道(1+x) k = c (k，0) x 0+c (k，1) x 1+...+c (k，k)x k；但你可能不知道，即使当k为负数且为小数时，也有类似的结论:(1+x) k = c (k，0) x 0+c (k，1) x 1+...+c (k，k) x .公式看着别扭，自己写在草稿纸上吧，毕竟在这里输入数学公式很麻烦。其中，广义组合数C(k，I)等于k(k-1)(k-2)(k-I+1)/I！C (4，6)= 4 * 3 * 2 * 1 * 0 *(1)/6！=0，或c (-1.4，2) = (-1.4) * (-2.4)/2！=1.68。后一个被称为牛顿二项式定理。当k是整数时，所有i & gt“0”项必须在k处的C(k，I)中交叉，所以下面的C(k，k+1)，C(k，k+2)等都是0，这和我们经典的二项式定理是一样的。不同的是，牛顿二项式定理中的指数k可以是任意实数。

我们再举一个例子来说明一些更复杂的生成函数。N=x1+x2+x3+...+xk有多少个非负整数解？这个问题是学习排列组合的经典例子。每组解的每个数加上1，就成了n+k=x1+x2+x3+的正整数解的个数...+xk。课本上可能有这样一个难听的名字叫“分区法”:把n+k个东西排成一排，在n+k-1个空格中插入k-1个“分区”。我们一直知道的答案是C(n+k-1，k-1)。等于C(n+k-1，n)。它关于n的母函数是g (x) = 1/(1-x) k，这个母函数是怎么来的？其实就是(1-x)的-k次方。根据刚才的牛顿二项式展开(1-x) (-k)，我们得到x n的系数正好是C(n+k-1，n)，因为c (-k，n) * (-x) n = [(-65438)。在这里头晕也没关系。后面还有一种方法可以推导出同样的公式。其实我们有更简单的纯组合数学的解释方法。因为我们的几何级数1+x+x ^ 2+x ^ 3+x ^ 4+...= 1/(1-x)，那么(1+X+X ^ 2+X ^ 3+X ^ 4)仔细想想k的含义(1+X+X ^ 2+X ^ 3+X ^ 4+...)乘法。在(1+x+x 2+x 3+x 4+的展开式中...)k，第n项的系数就是我们的答案，因为它的系数是由原公式完全展开后，k个指数恰好等于n的项组合而成的。

现在让我们引用一个组合数学中经典的例子。很多书都会有这样的疑问。

我们需要从苹果、香蕉、橘子、梨中取一些水果，要求苹果只能取偶数，香蕉的个数要5的倍数，橘子最多可以取4，梨只能取一个或者不取。问按这样的要求取n果的方案数。

我们也可以结合K(1+X+X ^ 2+X ^ 3+X ^ 4+的乘法来计算这个问题的母函数...).

引用内容

g(x)=(1+x^2+x^4+...)(1+x^5+x^10+..)(1+x+x^2+x^3+x^4)(1+x)

=[1/(1-x ^ 2)]*[1/(1-x ^ 5)]*[(1-x ^ 5)/(1-x)]

第三个，(1+x+x 2+x 3+x 4) * (1-x)是1-x 5)。

= 1/(1-x) 2

= (1-x) (-2) = c (1，0)+c (2，1) x+c (3，2) x 2+c (4，3) x 3...

=1+2x+3x^2+4x^3+5x^4+....

所以n种水果有n+1种取法。我们用生成函数，完全用代数手段得到了答案！

如果你不熟悉1/(1-x) K的展开式，我们将介绍一种更简单、更微妙的手段来解释1/(1-x)2 = 1+2x 2+4x 3+。

1/(1-x)= 1+x+x2+x3+x4+...如前所述。我们在等号两边取这个公式的导数。所以，1/(1-x)2 = 1+2x+3x 2+4x 3+5x 4+...一步到位获得我们需要的东西！通过不断求导，也可以得到刚刚利用复杂的牛顿二项式定理得出的结论(自己试试)。还有很多其他的生成函数的方法，比如方程两边乘一个常数再除以一个常数(相当于方程右边每项乘一个常数再除以一个常数)，方程两边乘一个x再除以一个x(相当于方程右边系数移动一位)，求微分积分。神奇的生成功能。

我们通过两种方法得到了这样一个公式:1/(1-x)n = 1+c(n，1) x 1+c (n+1，2) x，这个公式非常有用，是将一个生成函数化简为一个序列的利器。还有核武器。

接下来，我们将演示如何使用生成函数来寻找斐波那契数列的通项公式。

斐波那契数列是一个递归数列:f(n)=f(n-1)+f(n-2)。现在我们需要找到它的母函数g(x)。G(x)应该是这样一个函数:

g(x)=x+x^2+2x^3+3x^4+5x^5+8x^6+13x^7+...

等式两边同时乘以x，我们得到:

x*g(x)=x^2+x^3+2x^4+3x^5+5x^6+8x^7+...

我们之前说过，这相当于等式右边的所有系数都向右移动了一位。

现在我们把前一个公式和后一个公式相加，我们得到:

g(x)+x*g(x)=x+2x^2+3x^3+5x^4+8x^5+...

把最后一个公式和第一个公式比较一下。如果第一个公式的系数左移一位，然后去掉多余的“1”，就成了最后一个公式。由于递归函数的性质，我们神奇地得到:g(x)+x*g(x)=g(x)/x-1。也就是说g (x)* x ^ 2+G(x)* x-G(x)=-x .把左边的G(x)拿出来，我们就有:G(x)(x ^ 2+x-1)=-x .所以，我们得到G(x)= x/(1-x-x ^ 2)。

现在的任务是把x/(1-x-x ^ 2)化简为一个通用公式。这不是1/(1-x) n的形式，我们需要把它改成这个形式。我们发现1-x-x2 =[1-(1-√5)x/2]*[1-(1+√5)x/2]((65438+)显然，它们应该是x 2-x-1 = 0的两个根。那么x/(1-x-x ^ 2)必须表示为？/[1-(1-√5)x/2]+？/[1-(1+√5)x/2]形式(再次抱歉，输入数学公式很麻烦，我们就随便看看)。这当然是可能的，因为这是适当的？的值可以使分子在两个分数相除后加起来正好是一个x。？值应该是多少？假设前一个？是c1，后者是c2，所以一般除法后的分子是c 1 *[1-(1+√5)x/2]+C2 *[1-(1-√5)x/。我们得到两个公式:常数项c1+c2=0，线性项-c 1 *(1+√5)/2-C2 *(1-√5)/2 = 1。这两个公式足够我们求解c1和c2的精确值了。你不用懂，我用的是Mathematica 5.0。求解方法是c1=-1/√5，c2=1/√5。不信你可以解决。现在，我们把X/(1-X-X ^ 2)变成了-(1/√5)/[1-(1-√5)X/2]+(1/√5)。我们已经知道，1/[1-(1-√5)x/2]的背后是以(1-√5)/2为公比的几何级数，1/[1-(65438)。然后，把每一个乘以一个常数，把它们加在一起，我们就得到了斐波那契数列的一般公式:f(n)=-(1/√5)*[(1-√5)/2]n+(1/√5)*【也许你会问，这么复杂的公式，还有根号，斐波那契数列不都是整数吗？神奇的是，这个充满根的公式对任意自然数n都是整数，熟悉用特征方程解线性递归方程的同学应该知道，上面的过程本质上和找特征根求解是一样的。实际上，用上面的方法，我们可以求出任何线性齐次递归方程的通项公式。什么是线性齐次递归？这是递归方程:f(n)等于多少个F(n-1)加上多少个F(n-2)加上多少个F(n-3)等等。斐波那契数列的递推关系是线性齐次递推关系。

最后来看一个例子。再说硬币兑换:我有1分，2分，5分。请问n分有多少种补法？考虑到刚才的果，我们很容易得到这个问题的母函数:g (x) = (1+x+x 2+x 3+...)(1+x 2+x 4+...)(1+x 5+。现在，我们需要把它变成一个通用公式。我们的步骤和刚才一模一样。我们展开(1-x)(1-x 2)(1-x 5)，得到1-x-x 2+x 3-x 5+x 6+x 7-。我们找到了-1+x+x ^ 2-x ^ 3+x ^ 5-x ^ 6-x ^ 7+x ^ 8 = 0的解，得到了以下八个解:-1，1，1。这个没算出来，还是用了Mathematica 5.0。不是我不想解，而是我根本不会解这个八次方程。这也是信息社会涉及这些东西的原因:次数略高，所以要用计算机解决。所以，(1-x)(1-x ^ 2)(1-x ^ 5)=(1+x)(1-x)3(1+(-)。注意那个(1-x) 3。由于等根的出现，我们不得不暂时将(1-x) 3中包含的因子(1-x) 2和(1-x)2写入分母，否则将无法求解出合适的c，你可以看到很多虚数。不过没关系，这些虚数也参与运算，就像刚才的求根公式一样，不会影响最终结果的合理性。然后，我们发现常数满足1/(1-x)(1-x ^ 2)(1-x ^ 5)= c 1/()+C2/(1-x ^ 5)。这个解决方案太复杂了。我用Mathematica解了几分钟，打印出了一个至少几十KB的公式。虽然复杂，但我确实得到了通式。有兴趣的可以尝试用Mathematica解决1/[(1-x)(1-x 3)](只有1和3分的硬币)。可以用SolveAlways[]函数求解c的值，你可以亲眼看到，一个四五行的充满虚数的公式，最后总会得到正确的整数答案。

关于母函数的东西有很多，比如求导Catalan级数，指数母函数等等。等我有空了再说。超过5000字。

胡一辰一直在问那个问题。很明显，那个话题和上面的硬币交换有关系。其实很多类似的题目都和生成函数有关。但是那个问题里没有用到生成函数的东西(可能是我没想到)。也许有某种方法可以通过生成函数来解决每个最大值，但整个问题不太可能通过生成函数来解决。

最近有个帖子问及“DP天牛”的话题。那个话题也是一样，很多类似的话题都和DP有关，但是那个话题不太可能改变规则。总觉得可以归结为包装问题(考虑到体积关系，至少需要几个箱子才能把所有物品放进去)，而后者似乎属于NPC。也许我错了。我现在只是在研究理论上的东西。很久没想过OI了，这方面的能力也开始退化了。