母函数(讲义)

讲课

---

普通型母函数：多重集组合问题

母函数是求解组合数学中计数问题的重要方法

在数学中，某个序列的母函数(又称生成函数)是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。

定义

给定数列$a_0,a_1,a_2,...,a_n,...$，构造一个函数$F(x)=a_0f_0(x)+a_1f_1(x)+...+a_nf_n(x)+...$,称$F(x)$为该数列的母函数，其中小f函数只作为标志用，称为标志函数

标志函数有一个重要的形式就是 $x^n$ ,这种情况下的母函数形式为

$$F(x)=a_0x^0+a_1x^1+a2x^2+...+a_nx^n+...$$

定理 $1$：设从 $n$ 集合元素$S=\{a_1,a_2,a_3...a_n\}$中取出 $k$ 个元素的组合是 $b_k$ ，若限定元素 $a_i$ 出现的次数集合为 $M_i(1\leq i \leq n)$，则该组合数序列的母函数为：

$$\prod^n_{i=1} (\sum_{m\in M_i}x^m)$$

由等比数列求和公式可知$G(x)=\dfrac{1}{1-x}$，我们称$\dfrac{1}{1-x}$为这个母函数的闭形式，该函数具有收敛性，即在$\left| x\right| \geq 1$时不成立，但由于母函数不用代入 $x$ 收敛性就不用考虑了

---

先举个例子吧

有重量为1克，3克，5克的砝码各两个，问：
1）可以称出多少种重量不同的物品》
2）若要称出质量为7克的物品，所使用的砝码有多少种本质上不同的情况？

解：
这里要用到上面的“定理 $1$”；
规模比较小，不妨手动模拟一下

称出物重	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
方法数	1	1	1	1	1	2	2	2	2	1	2	2	2	2	1	1	1	1	1

我们再按“定理 $1”，将该题的母函数列出来$$G(x)=(1+x+x^2)(1+x^3+x^6)(1+x^5+x^{10})$
再将其展开，得

$$G(x)=1+x+x^2+x^3+x^4+2x^5+2x^6+2x^7+2x^8+x^9$$ $$+2x^{10}+2x^{11}+2x^{12}+2x^{13}+x^{14}+x^{15}+x^{16}+x^{17}+x^{18}$$
跟上个表格对比一下，可以恰好发现，指数与称出物重相同,而系数就等于方法数

为什么呢

$$G(x)=(1+x+x^2)(1+x^3+x^6)(1+x^5+x^{10})$$

$(1+x+x^2)$实际上是$(x^0+x+x^2)$即质量为 $1$ 的砝码不取，取一个，和取两个
$x^2 \cdot x^6 = x^8$就是取了两个质量为一和一个两个质量为二的的砝码，同时，$x^8=x^3+x^5$,所以质量为8的称重方法有两种，系数为二

---

另一个例子

有无穷多个物品时，母函数也可以写出来，见下面

hdu1028

The problem is, given an positive integer N, we define an equation like this:
 N=a[1]+a[2]+a[3]+...+a[m];
 a[i]>0,1<=m<=N;N(1<=N<=120) 
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
  4 = 4;
  4 = 3 + 1;
  4 = 2 + 2;
  4 = 2 + 1 + 1;
  4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem.

这里的母函数为

$$G(x)=\prod^\infty_{i=1}(\sum^\infty_{j=0}x^{i*j})$$
怎么回事看代码就知道了，说是 $\infty$ 到 $n$ 就可以了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200
using namespace std;
int n;
int c1[MAXN],c2[MAXN];
int main(){
    while(scanf("%d",&n)!=EOF){
        int i,j,k;
        for(i=0;i<=n;i++){
            c1[i]=1;c2[i]=0;
        }
        for(i=2;i<=n;i++){//第i个式子
            for(j=0;j<=n;j++){//c[j]为系数
                for(k=0;j+k<=n;k+=i){//指数
                    c2[j+k]+=c1[j];
                }    
            }
            for(j=0;j<=n;j++){
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
        printf("%d\n",c1[n]);
    }
    return 0;
}

其实hdu还有几道题，都和这个类似，不说了，见附①

---

母函数的一些基本操作

都是有一定用处的
1.放缩：

$$cG(x)=cg_0+cg_1x+cg_2x+\cdots\leftrightarrow<cg_0,cg_1,cg_2,\cdots>$$

2.加减法：

$$F(x)\pm G(x)=(f_0\pm g_0)+(f_1\pm g_1)x+(f_2\pm g_2)x^2+\cdots\leftrightarrow<f_0\pm g_0,f1\pm g_1,f2\pm g_2,\cdots>$$

3.右移
将序列向右平移 $k$ 位，并在前面补 $0$

$$G(x)=g_0x^k+g_1x^{k+1}+g_2x^{k+2}+\cdots\leftrightarrow<\underbrace{0,\cdots,0}_{\rm k},g_0,g_1,g_2,\cdots>$$

4.求导

$$G'(x)=g_1+2g_2x+3g_3x^2+\cdots\leftrightarrow<g_1,2g_2,3g_3,\cdots>$$
其操作效果就是将序列左移一位并使每一项乘以它的下标。

5.卷积规则：

$$H(x)=G(x)\cdot F(x)=(g_0+g_1x+g_2x^2+\cdots)(f_0+f_1x+f_2x^2+f_3x^3+\cdots)$$

则 $H(x)$ 中 $x^n$ 的系数 $h_n=g_0f_n+g_1f_{n-1}+g_2f_{n-2}+\cdots+g_nf_0$

当 $G(x)$ 对应在 $A$ 中选择元素的母函数，而 $F(x)$ 对应在 $B$ 中选择元素的母函数，则 $G(x)\dot F(x)$ 对应在 $A\cup B$ 选择元素的母函数。

---

简单序列所对应的母函数

通式：

$$G(x)=\dfrac{1}{(1-ax)^m}=1+aC^{m-1}_mx+a^2C^{m-1}_{m+1}x^2+a^3C^{m-1}_{m+2}x^3+\cdots$$

推导手写吧

---

指数型母函数：多重集排列问题

定理 $2$ : 从多重集和 $M=\{\infty\cdot a_1,\infty\cdot a_2,\infty\cdot a_3,\cdots,\infty\cdot a_n,\}$中选取 $k$ 个元素的 $k$-排列中，若限定元素$a_i$出现的次数集合为 $M_i(1\leq i\leq n)$ ，则该组合数序列的母函数为

$$\prod^n_{i=1}(\sum_{m\in M_i}\dfrac{x^m}{m!})$$

所以指数型母函数可以长成这个样子

$$G_e(x)=1+\dfrac{x}{1!}+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\cdots+\dfrac{x^n}{n!}$$
对于其中的$\dfrac{x^j}{j!}$表示在一个方案中某个元素出现了 $j$ 次，而在不同位置中的 $j$ 次出现是相同的，所以在计算排列总数时只应算作一次，所以应该除以 $j!$。

在应用指数母函数时应注意：展开式

$$G_e(x)=a_0+a_1x+a_2x+a_3x+\cdots$$
应化为如下形式 $$G_e(x)=b_0+b_1\cdot\dfrac{x}{1!}+b_1\cdot\dfrac{x^2}{2!}+b_3\cdot\dfrac{x^3}{3!}+\cdots$$
真正我们需要的地方实际上是 $b_0,b_1,b_2,b_3,\cdots$

举个例子

设有三个数字 $1$ ，两个数字 $6$，一个数字 $8$，问能组成多少个四位数？

解：指数型母函数为

$$G(x)=(1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!})(1+x+\dfrac{x^2}{2!})(1+x)$$
$$=1+3x+8\dfrac{x^2}{2!}+19\dfrac{x^3}{3!}+38\dfrac{x^4}{4!}+60\dfrac{x^5}{5!}+60\dfrac{x^6}{6!}$$
故可以组成38个四位数

---

$e^x$的Taylor展开式

$$e^x=\sum^{\infty}_{n=0}\dfrac{x^n}{n!}=1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\cdots+\dfrac{x^n}{n!}+\cdots$$

$$\dfrac{e^x+e^{-x}}{2}=\sum^{\infty}_{n=0}\dfrac{x^{2n}}{{2n}!}=1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+\cdots+\dfrac{x^{2n}}{{2n}!}+\cdots$$

$$\dfrac{e^x-e^{-x}}{2}=\sum^{\infty}_{n=0}\dfrac{x^{2n+1}}{(2n+1)!}=1+x+\dfrac{x^3}{3!}+\dfrac{x^5}{5!}+\cdots+\dfrac{x^{2n+1}}{(2n+1)!}+\cdots$$

求解指数型母函数时经常使用

比如说

红色病毒问题

医学界发现的新病毒因其蔓延速度和Internet上传播的"红色病毒"不相上下,被称为"红色病毒",经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。
现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,T,C,G四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:TT,TG,GT,GG,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.

Input：

    每组输入的第一行是一个整数T,表示测试实例的个数,下面是T行数据,每行一个整数N(1<=N<2^64),当T=0时结束. 

Output：

    对于每个测试实例,输出字符串个数的最后两位,每组输出后跟一个空行.

Sample Input：

    4
    1
    4
    20
    11
    3
    14
    24
    6
    0

Sample Output：

    Case 1: 2
    Case 2: 72
    Case 3: 32
    Case 4: 0

    Case 1: 56
    Case 2: 72
    Case 3: 56

Solution：

由于 $A,C$ 只能出现偶数次，而 $T,G$ 没有限制，所以可以构造母函数

$G(x)=(1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+\cdots)^2\times(1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\cdots)^2$

$=(\dfrac{e^x+e^{-x}}{2})^2\times e^{2x}$

$=(\dfrac{e^{2x}+1}{2})^2\\=\dfrac{e^{4x}+2e^{2x}+1}{4}$

$=\dfrac{\sum^{\infty}_{n=0}4^n\dfrac{x^n}{n!}+2\times\sum^{\infty}_{n=0}\dfrac{2^n\times x^n}{n!}+1}{4}$

$=\dfrac{1}{4}+\sum^{\infty}_{n=0}\dfrac{4^n+2\times 2^n}{4}\times\dfrac{x^n}{n!}$

$1+\sum^{\infty}_{n=1}\dfrac{4^n+2\times 2^n}{4}\times \dfrac{x^n}{n!}$

$\therefore a_n=\dfrac{4^n+2\times 2^n}{4}=4^{n-1}+2^{n-1}(n\in N^*)$

然后快速幂求解即可，注意所求 $b_n=a_n mod 100$

代码见附②

---

指数型母函数的基本操作与普通型类似，但求导不同

$$G(x)=g_0+\dfrac{g_1}{1!}x+\dfrac{g_2}{2!}x^2+\cdots$$

则

$$G' (x)=g_1+\dfrac{g_2}{1!}x+\dfrac{g_3}{2!}x^2+\cdots$$

上述求导也就是左移的过程

右移操作需要积分，哪位大神会可以来说说，没有也无所谓，好像今天用不上。。。

乘积也不同：
设$G(x)=g_0+\dfrac{g_1}{1!}x+\dfrac{g_2}{2!}x^2+\cdots$是序列$<g_0,g_1,g_2,\cdots>$的指数型母函数，$F(x)=f_0+\dfrac{f_1}{1!}x+\dfrac{f_2}{2!}x^2+\cdots$是序列$<f_0,f_1,f_2,\cdots>$的指数型母函数。

那么，

$$H(x)=G(x)\cdot F(x)=\sum^{}_{n\geq 0}\dfrac{x^n}{n!}\sum^{}_{k\geq 0}(\dfrac{g_k}{k!}\times\dfrac{f_{n-k}}{(n-k)!})=\sum_{n \geq 0}\dfrac{x^n}{n!}\sum(g_k\times f_{n-k} \times C^k_n)$$

$\therefore H(x)$的$x^n$的系数为$h_n=\sum(g_k\times f_{n-k}\times C^k_n)$

---

下面来一道概率题，用到指数型母函数

ST之前讲过的，不过是用dp

一个口袋中装有巧克力，巧克力的颜色有c种。先从口袋中取出一个巧克力，若取出巧克力与桌上已有的巧克力颜色相同，则将两个巧克力都取走，否则将取出的巧克力放在桌上。设从口袋中取出每种颜色的巧克力的概率相等。求取出 $n$ 个巧克力后桌面上剩余 $m$ 个巧克力的概率。

For each case, there are three non-negative integers: C (C <= 100), N and M (N, M <= 1000000).

dp不优化 $O(Nc)$ 而母函数只是展开了一个多项式，复杂度 $O(c^2)$

Solution:

首先，若 $2|(n-m)$ 则解不为 $0$ ，否则解为 $0$

所有可能的情况为 $c^n$
这种分发考虑到不同颜色的巧克力之间的排列关系，所以可以用指数型母函数求解

剩余 $m$ 个巧克力可以转化为 $c$ 种巧克力种有 $m$ 种取出了奇数次，$c-m$ 种巧克力出现了偶数次

所以

$$G(x)=(\dfrac{e^x-e^{-x}}{2})^m\times(\dfrac{e^x+e^{-x}}{2})^{c-m}$$

然后展开
再把展开的多项式乘一下

注：公式太多不打了，参见国家集训队论文2009--毛文杰

代码见附③

---

附：

①：
1.题目UVA674
2.题目：http://acm.hdu.edu.cn/showproblem.php?pid=1398
代码：http://www.wutianqi.com/?p=590
3. 题目：http://acm.hdu.edu.cn/showproblem.php?pid=1085
代码：http://www.wutianqi.com/?p=592
4. 题目：http://acm.hdu.edu.cn/showproblem.php?pid=1171
代码：http://www.wutianqi.com/?p=594
//出自http://www.wutianqi.com/

②:

#include<cstdio>
#define LL long long
using namespace std;
LL n;
LL a;
int kase;
LL qpow(LL x,LL k){
    LL ans=1;LL mul=x;
    LL i;
    for(i=1;i<=k;i<<=1){
        if(k&i){
            ans*=mul;
            ans%=100;
        }
        mul*=mul;
        mul%=100;
    }
    return ans;
}
int main(){
    while(scanf("%d",&kase)!=EOF){
        if(kase==0)return 0;
        for(int i=1;i<=kase;i++){
            scanf("%I64d",&n);
            a=qpow(4,n-1)+qpow(2,n-1);
            a%=100;
            printf("Case %d: %I64d\n",i,a);
        }
        printf("\n");
    }
    return 0;
}

③：

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
const int MAXN=107;  
const int MOD=100;  
int c,n,m;  
double tp1[MAXN],tp2[MAXN],tp1_[MAXN],tp2_[MAXN];//tp1[k]表示{[e^x-e^(-x)]/2}^m展开式中e^kx的系数，tp1_[k]表示其展开式中e^(-kx）的系数；tp2[k]、tp2_[k]同理  
double p[MAXN],p_[MAXN];//p[k]表示{[e^x-e^(-x)]/2}^m*{[e^x+e^(-x)]/2}^(c-m)展开式中e^kx的系数，p_[k]则表示其展开式烦人才中e^(-kx)的系数  
double quickPow(double a,int b) {  
    double res=1;  
    while(b>0) {  
        if((b&1)==1) {  
            res*=a;  
        }  
        a*=a;  
        b>>=1;  
    }  
    return res;  
}  
double C(double res,int a,int b) {  
    if(b>a-b) {  
        b=a-b;  
    }  
    for(int i=1;i<=b;++i) {  
        res*=(a-i+1.0)/i;  
    }  
    return res;  
}  
void getCoefficient() {//{[e^x-e^(-x)]/2}^m*{[e^x+e^(-x)]/2}^(c-m)展开式中e^kx和e^(-kx)的系数  
    for(int k=0;k<=c;++k) {  
        tp1[k]=tp1_[k]=tp2[k]=tp2_[k]=p[k]=p_[k]=0;  
    }  
    double sign,halfEm=quickPow(0.5,m);  
    int exp;  
    for(int i=0;i<=m;++i) {//计算前半部分表达式展开式的e^exp的系数  
        sign=(i&1)==1?-1:1;  
        exp=m-i-i;  
        if(exp<0) {  
            tp1_[-exp]+=sign*C(halfEm,m,i);  
        }  
        else {  
            tp1[exp]+=sign*C(halfEm,m,i);  
        }  
    }  
    halfEm=quickPow(0.5,c-m);  
    for(int j=0;j<=c-m;++j) {//计算后半部分表达式展开式的e^exp的系数  
        exp=c-m-j-j;  
        if(exp<0) {  
            tp2_[-exp]+=C(halfEm,c-m,j);  
        }  
        else {  
            tp2[exp]+=C(halfEm,c-m,j);  
        }  
    }  
    double fp,sp;//分别表示第一个式子和第二个式子的系数  
    for(int i=-m;i<=m;++i) {//计算整个表达式展开式的e^exp的系数  
        fp=i<0?tp1_[-i]:tp1[i];  
        for(int j=-(c-m);j<=c-m;++j) {  
            sp=j<0?tp2_[-j]:tp2[j];  
            exp=i+j;  
            if(exp<0) {  
                p_[-exp]+=fp*sp;  
            }  
            else {  
                p[exp]+=fp*sp;  
            }  
        }  
    }  
}  
double solve() {  
    getCoefficient();  
    double ans=0,sign=(n&1)==1?-1:1;  
    for(int k=1;k<=c;++k) {  
        ans+=C(quickPow(1.0*k/c,n)*(p[k]+sign*p_[k]),c,m);  
    }  
    return ans;  
}  
int main() {  
    while(scanf("%d",&c),c!=0) {  
        scanf("%d%d",&n,&m);  
        if(m>n||m>c||((n+m)&1)==1) {  
            printf("0.000\n");  
        }  
        else if(n==0&&m==0){  
            printf("1.000\n");  
        }  
        else {  
            printf("%.3lf\n",solve());  
        }  
    }  
    return 0;  
}