母函数

数学

---

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

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

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

---

定义

给定数列$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)$$

---

先举个例子吧

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

---

解：

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

称出物重	0	1	2	3	4	5	6	7	8	9
方法数	1	1	1	1	1	2	2	2	2	1

称出物重	10	11	12	13	14	15	16	17	18
方法数	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=1}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+g_0)+(f_1+g_1)x+(f_2+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<0,\cdots ,0,g_0,g_1,g_2,\cdots>$$

4.求导

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

---

5.卷积规则：

$$H(x)=G(x)\dot 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}+a^3C^{m-1}{m+2}+\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}{x!}+\dfrac{x^3}{3!})(1+x+\dfrac{x^2}{x!})(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+x+\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：

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

---

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}$$

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

---

①：

1.题目UVA674
2.题目：http://acm.hdu.edu.cn/showproblem.php?pid=1398

代码：http://www.wutianqi.com/?p=590

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