母函数

一 母函数的定义

1.定义

• 对于序列$C_0,C_1,C_2,\dots$构造一函数
  $G(x)=C_0+C_1x+C_2x^2+\dots$称$G(x)$为序列$C_0,C_1,C_2,\dots$的母函数。

例如：$(1+x)^n$为序列$C_0,C_1,C_2,\dots C_n$的母函数。

• 序列的长度：可能是有限的，也可能是无限的。
• 序列和对应的母函数是一一对应的。

2.理解

• 组合数学的主要内容是计数，用的最多的计数工具为母函数。

例：两个骰子掷出6点，有多少种可能性？

现有：且：乘法法则（分步）或：加法法则（分类）

• 方法一：第一位数1-5，且第二位数由第一位数来确定 $5×1=5$
• 方法二：$1+5=5+1$;或$2+4=4+2$;或$3+3=3+3$

如果：很多骰子的情况，以上方法是不是不再适用？

雅各布·伯努利(Jakob Bernoulli‎）300多年前提出的问题：
投掷m粒骰子时，加起来点数总和等于n的可能方式的数目？

思路：如下图所示

• 先来看两个色子掷出n点的可能，第一个色子掷出的可能性为1或2或3或4或5或6，即$?+?+?+?+?+?$，如果直接点数相加，结果为各个点数的求和，显然不符合要求，那么什么相加呢？
• 我们考虑第一个色子两个点数，分两步贴点，贴第一个点为x，贴第二个点为x，则两个点可以表示为$x^2$，同理，1 3 4 5 6可分别表示为：$x \space x^3\space x^4\space x^5\space x^6$,则：
  1或2或3或4或5或6 可表示为：$x+x^2+x^3+x^4+x^5+x^6$
• 两个色子掷出的点数之和，分布来看，假设第一个色子掷出2点，第二个色子掷出4点，得到6点，即为：$x^2x^4=x^6$
  掷出6点所有的可能性：
  $x^1x^5+x^2x^4+x^3x^3+x^4x^2+x^5x^1$共5种，与
  $(x+x^2+x^3+x^4+x^5+x^6)×(x+x^2+x^3+x^4+x^5+x^6)$中的$x^6$系数相同。
  由此可见，两个色子掷出的点数可由
  $(x+x^2+x^3+x^4+x^5+x^6)^2$函数中的系数表示。

3.总结：函数中的系数对应计数序列。

再来理解母函数的定义：

• 关注每一个计数序列
• 每一个计数序列对应的是$x^k$

这个定义是拉普拉斯在研究概率的时候，研究了母函数的方法和相关定义。（1812年法国数学家拉普拉斯在著作《概率的分析理论》第一卷中系统地研究了母函数的方法和有关理论）

投掷m个色子出现n点的个数？

最后我们来看母函数与函数的区别：

母函数 似函数 非函数

母函数：

• 计数工具
• 不考虑收敛性
• 不考虑实际上的数值
• 形式幂级数(format power series)

通过映射进行问题转化。

结构未发生变化只是视角发生了变化 产生新思维、新想象力

二 母函数的应用一_砝码问题

例一：

• 有1克，2克，3克，4克的砝码，一共能称出多少种重量？
• 对于每一种重量，有多少种不同的解决方案？
  求解：
  1克砝码选或者不选，表示为$1+x$
  2克砝码选或者不选，表示为$1+x^2$
  3克砝码选或者不选，表示为$1+x^3$
  4克砝码选或者不选，表示为$1+x^4$
  所以，分布求解，母函数为：
  $G(x)=(1+x)(1+x^2)(1+x^3)(1+x^4)$ $=1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^{10}$
  所以，一共称出的重量为1-10克。
  每种重量，对应的方案数，即为$x^k ,\space k=1,\dots10$ 前面的系数。

例二：

• 有1，2，4，8，16，32克的砝码，一共能称出多少种重量？
• 对于每一种重量，有多少种不同的解决方案？
  母函数为：
  $G(x)=(1+x)(1+x^2)(1+x^4)(1+x^8)(1+x^{16})(1+x^{32})$怎样将其快速展开？
  因为:$1+x=\frac{1-x^2}{1-x}$
  所以：
  $G(x)=\frac{1-x^2}{1-x}\cdot\frac{1-x^4}{1-x^2}\cdot\frac{1-x^8}{1-x^4}\cdot\frac{1-x^{16}}{1-x^8}\cdot\frac{1-x^{32}}{1-x^{16}}\cdot\frac{1-x^{64}}{1-x^{32}}$即：
  $G(x)=\frac{1-x^{64}}{1-x}=(1+x+x^2+\cdots+x^{63})=\sum_{k=0}^{63}x^k$由此发现，用1、2、4、8、16、32…这样的数做砝码，就可以唯一确定一些重量。

总结：

• 2如果进行累加有一个特殊的性质，任何一个十进制数n都可以表达为$2^k$进行累加。
  $n=\sum_{k\ge0}a_k2^k\space,0\le a_k\le1,k\ge0$
  这也就是为什么二进制数是合理的原因。

三 母函数的应用二

例一：

• 整数$n$拆分成$1,2,3\dots m$的和，并允许其重复，求其母函数。
  母函数为： $G_1(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots(1+x^m+x^{2m}+\cdots)$又因为无穷级数$(1-x)^{-1}=(1+x+x^2+\cdots)$
  所以： $G_1(x)=\frac{1}{1-x}\cdot\frac{1}{1-x^2}\cdots\frac{1}{1-x^m}=\frac{1}{(1-x)(1-x^2)\cdots(1-x^m)}$
• 如若其中$m$至少出现一次，其函数如何？ $G_2(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots(x^m+x^{2m}+\cdots)$
  则： $G_2(x)=\frac{x^m}{(1-x)(1-x^2)\cdots(1-x^m)}$可表示为：
  $G_2(x)=\frac{1}{(1-x)(1-x^2)\cdots(1-x^m)}-\frac{1}{(1-x)(1-x^2)\cdots(1-x^{m-1})}$

上式的组合意义：即整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。
例二：

• 人民币：1角，5角，1元，求其母函数。
  $G(x)=(1+x^{10}+x^{20}+\cdots)(1+x^{50}+x^{100}+\cdots)(1+x^{100}+x^{200}+\cdots)$
• 美元：10美分，25美分
  $G(x)=(1+x^{10}+x^{20}+\cdots)(1+x^{25}+x^{50}+\cdots)$
• 美元：5美分，10美分，25美分。
  $G(x)=(1+x^{5}+x^{10}+\cdots)(1+x^{10}+x^{20}+\cdots)(1+x^{25}+x^{50}+\cdots)$
  画图对比结果：人民币的表现相对于美元更加丰富。
  加入5美分后，美元表现力剧增。

四 整数拆分

1.有序拆分和无序拆分

• 将一个正整数拆分成若干个正整数之和。
• 各部分之间考虑顺序叫做有序拆分(composition)
• 各部分之间不考虑顺序叫做无序拆分(partition)
  例如：
  3的有序拆分：$1+2 ,\space 2+1$
  3的无序拆分：3就等于$1+2$之和。

数字$n$拆分成$r$个自然数之和，有多少种不同的方案数？

• 有序拆分
  如下图：
  $r-1$个隔板形成$r$份，由于每个区域至少要有一个球，所以需要插入$n$个球形成的$n-1$个空隙，所以方案数为$C(n-1,r-1)$

• 无序拆分：
  无序$r$拆分：对应一个数$n$怎么把它划分成$r$个自然数之和。
  3的无序2拆分：3=2+1
  3的所有无序拆分：3=3+0+0=2+1+0=1+1+1

无序拆分： 把一个整数拆分成若干整数的和，相当于把$n$个无区别的球放到$r$个无标志的盒子，盒子允许空着，有多少种方法，就意味着整数拆分数有多少。

2.无序拆分数

概念：

• 经常被用于密码学，统计学，生物学等领域。
• 将一个正整数n拆分成若干正整数之和，数字之间顺序无关并允许重复，其不同的拆分数即$p(n)$.

历史进程：

• 欧拉通过多项式乘法的手工计算，1740年，得出$p(29)=173525$
  欧拉母函数拆分法：
  $G_1(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots(1+x^m+x^{2m}+\cdots)$中$x^n$的系数。
  欧拉的方法确实精妙，但不一定是计算整数拆分数最有效的方法。

• 拉马努金 1918年，得出$p(200)=3972999029388$
  拉马努金推出计算整数拆分方案数的一个"公式"：
  $p(n)\sim\frac{1}{4n\sqrt{3}}exp(\pi\sqrt{\frac{2n}{3}}) \space a\rightarrow\infty$

• OEIS得出p(300)=9253082936723602
  OEIS(The On-Line Encyclopedia of Integer Sequences)
  数论相关权威数据库和算法库
  $p(n):A000041序列$

• 计算机的出现和组合算法的发展使整数拆分数的计算有了极大的突破。
  方法：$G_1(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots(1+x^m+x^{2m}+\cdots)\cdots$将系数放入数组$f(k)$$g(k)$进行卷积运算，进行卷积运算$(f*g)[k]=\sum_{n}f(i)g(k-i)$得出：
  $G_1(x)=(1+x+2x^2+2x^3+2x^4+2x^4+\cdots)(1+x^3+x^6+\cdots)\cdots(1+x^m+x^{2m}+\cdots)\cdots$依次递推，即可利用计算机方法逐步循环得到多项式乘法的解。
  结论：计算机计算整数拆分数只能计算到$p(416)$。
  原因：计算机64位无符号整型最大表示：18,446,744,073,709,551,615。$p(417)$超出其范围，会溢出。
  瓶颈：如何处理大数相乘？
  Birch and Swinnerton-Dyer猜想

3. ferrers图像与整数拆分

ferrers图像

• 将n个数字表示为n个格子

• 非递增性：上一层的格子要比下一层的格子多

性质

• 每一层至少有一个格子。

• 第一行与第一列互换，第二行与第二列互换,…要虚线轴旋转所得的图仍是FERRERS图像。两个FERRERS图像称为一对共轭的FERRERS图像。

整数拆分性质与FERRERS图像

• 整数$n$拆分成最大数为$k$的拆分数，与整数$n$拆分成$k$个数的和的拆分数相等。
  最大数为$k$,对应FERRERS图像行最多的格子数为$k$个。
  $k$个数的和，对应FERRERS图像有$k$层。
  最大数是$k$和变成$k$个数的和，它们的对应FERRERS图像（沿斜对角线翻转的共轭FERRERS图像）是一一对应的。

  

• 整数$n$拆分为最多不超过$m$个数的和的拆分数和$n$拆分成最大不超过$m$的拆分数相等。（FERRERS图像共轭性可证明）

• 整数$n$拆分为互不相同的若干个奇数的和的拆分数，和$n$拆分为自共轭的Ferrers图像的拆分数相等。
  自共轭图像：
  沿斜对角线翻转的共轭FERRERS图像还是本身的FERRERS图像称为自共轭图像。
  自共轭图像对应奇数拆分数的表示方法。
  拆分为奇数:
  设$n=(2n_1+1)(2n_2+1)+\cdots+(2n_k+1)$，其中$n_1>n_2>\cdots>n_k$
  对应Ferrers图像：
  第一行，第一列都是$n_1+1$格，对应于$2n_1+1$。
  第二行，第二列都是$n_2+1$格，对应于$2n_2+1\cdots$
  如下图所示。

  

  举例：$17=9+5+3$对应的Ferrers图像。

  

五 母函数发展历史

1705年前雅各布·伯努利研究骰子
1740年左右欧拉研究整数拆分
1812年拉普拉斯提出母函数的概念

抽出定义：

• 对于序列$C_0,C_1,C_2,\dots$构造一函数
  $G(x)=C_0+C_1x+C_2x^2+\dots$称$G(x)$为序列$C_0,C_1,C_2,\dots$的母函数。母函数 似函数 非函数 是映射