浅谈生成函数与组合计数,多项式全家桶(干货满满)

引言

​ 组合计数问题是信息学竞赛中常见的一类问题,而生成函数往往是解决这类问题的重要工具。

​ 上面这句话出自2015年金策的论文,这篇论文写的非常系统,推荐阅读。

​ 本文则是偏向于推导和总结,分成组合数学部分和多项式全家桶 一点都不全 部分,分别讲解生成函数在解决组合计数问题的方法及技巧。

组合数学

基础概念

生成函数

​ 生成函数就是一列用来展示一串数字的挂衣架。(赫伯特·维尔夫)

​ 在数学中,某个序列 \({\displaystyle (a_{n})_{n\in \mathbb {N} }}\) 的母函数(又称生成函数,英语:Generating function)是一种形式幂级数,其每一项系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。(*)

​ 看完上面的解释,相信初次接触生成函数的读者也对它有了一定的了解 (扯吧 。生成函数按实现功能可以分成两类:普通型生成函数、指数型生成函数。

普通型生成函数(OGF)

​ 对于一个给定的数列 \(\{a_n\}\) ,定义它的普通型生成函数 \(G(x)\) 为

\[ G(x)=\sum_{n=0}^{+\infty}a_nx^n \]

​ 如果这个数列是不是无穷数列,那么比最后一项高的项都为 \(0\) 。

指数型生成函数(EGF)

​ 对于一个给定的数列 \(\{a_n\}\) ,定义它的指数型生成函数 \(G(x)\) 为

\[ G(x)=\sum_{n=0}^{+\infty}{a_n\over n!}x^n \]

​ 如果这个数列是不是无穷数列,那么比最后一项高的项都为 \(0\) 。

​ 生成函数说白了就是把一个数列摆在一个形式幂级数上,而形式幂级数就是上面那个写成函数样子的 \(G(x)\) ,注意,它真的就只是一个形式,那个变量 \(x\) 不可能真的带一个数进去算。如果拿挂衣架做比喻的话,那 \(x\) 的不同幂次就相当于挂衣架上的一个一个钩子,数列 \(\{a_n\}\) 就是一件一件的衣服。钩子把一件一件衣服挂在挂衣架上,就是生成函数。

​ 我们不妨用几道烂大街的数学题来看一下生成函数这个东西的作用。

例子
  • (例题 1-1-1)有 \(1g\) 砝码 \(2\) 枚,\(2g\) 砝码 \(3\) 枚,\(3g\) 砝码一枚,相同质量砝码之间没有区别,问称出每种质量的方案数。

    解:

​ 考虑生成函数,设 \(x\) 的指数为砝码的质量,可以写出普通型生成函数如下

\[ \begin{align*} F(x)&=(1 + x + x^2)(1 + x^2 + x^4 + x^6)(1+x^3)\\ &= 1 + x + 2 x^2 + 2 x^3 + 3 x^4 + 3 x^5 + 3 x^6 + 3 x^7 + 2 x^8 + 2 x^9 + x^{10} + x^{11} \end{align*} \]
​ 其中每一个括号里的内容代表每一种质量的砝码,以第一个括号为例,\(1\)(即 \(x^0\) )代表不取 \(1g\)
砝码,\(x\) 代表取 \(1\) 个 \(1g\) 砝码,\(x^2\) 代表取 \(2\) 个 \(1g\) 砝码,其他同理。

  • (例题 1-1-2)你有数字 \(1\) 两个,数字 \(2\) 三个, 数字 \(3\) 一个,问选出一个、两个、三个……数字的方案数。

    解:

​ 考虑生成函数,设 \(x\) 的指数为数字的个数,可以写出普通型生成函数如下
\[ \begin{align*} F(x)&=(1+x+x^2)(1+x+x^2+x^3)(1+x)\\ &= 1 + 3x + 5x^2 + 6 x^3 + 5x^4 + 3x^5 + x^6 \end{align*} \]

​ 本题的题面和上道题有点像,但是要求的东西不同,上道题要求的是每种质量和的方案数(即数字总和),而这道题是数字个数,定义状态不同,故生成函数不同。

​ 这道题其实是为了引出下面这道指数型生成函数的例题。

  • (例题 1-1-3)你有数字 \(1\) 两个,数字 \(2\) 三个, 数字 \(3\) 一个,问组成一位数、两位数、三位数……的方案数。

    解:

​ 考虑生成函数,设 \(x\) 的指数为数字的个数,可以写出指数型生成函数如下
\[ \begin{align*} F(x)&=({1\over 0!}+{1\over 1!}x+{1\over 2!}x^2)({1\over 0!}+{1\over 1!}x+{1\over 2!}x^2+{1\over 3!}x^3)({1\over 0!}+{1\over 1!}x)\\ &={1 \over 0!} + {3 \over 1!} x + {8 \over 2!} x^2 + {19 \over 3!} x^3 + {38 \over 4!} x^4 + {60 \over 5!} x^5 + {60 \over 6!} x^6 \end{align*} \]

​ 指数型生成函数可能刚开始有点难以理解,初学者可能会发出这样的疑问:这个东西不就是 \(x^n\) 下面加了一个 \(n!\) 吗?是的,形式上就是这样的,在编程中,运算时也要把它转成普通型运算,再转成指数型展示。但是,与上面的问题对比一下,就不难发现一个规律:

普通型生成函数解决的是组合问题(无标号),指数型生成函数解决的是排列问题(有标号)。

​ 好吧,这里面也没什么大道理,让我们观察其中一项的计算过程,以 \(x^3\) 为例,我们看一下那个 \(19\) 是怎么来的。
\[ \begin{align*} {19\over 3!}&={1\over 2!\cdot 1!\cdot 0!}+{1\over 2!\cdot 0!\cdot 1!}+{1\over 1!\cdot 2!\cdot 0!}+{1\over 1!\cdot 1!\cdot 1!}+{1\over 0!\cdot 3!\cdot 0!}+{1\over 0!\cdot 2!\cdot 1!}\\ 19&={3!\over 2!\cdot 1!\cdot 0!}+{3!\over 2!\cdot 0!\cdot 1!}+{3!\over 1!\cdot 2!\cdot 0!}+{3!\over 1!\cdot 1!\cdot 1!}+{3!\over 0!\cdot 3!\cdot 0!}+{3!\over 0!\cdot 2!\cdot 1!}\\ 19&={3\choose 2\quad 1\quad 0}+{3\choose 2\quad 0\quad 1}+{3\choose 1\quad 2\quad 0}+{3\choose 1\quad 1\quad 1}+{3\choose 0\quad 3\quad 0}+{3\choose 0\quad 2\quad 1} \end{align*} \]
​ 式子变一变,就变成了一个多重元素全排列的形式,例题 1-1-2 是对一样的数列构造一个普通型生成函数,\([x^3]=6\) ,(\([x^n]\) 表示取多项式中次数为 \(n\) 的项的系数)而 \(\displaystyle {19\over 3!}\) 展开也有 \(6\) 项,只是每一项多乘了排列数罢了。

​ 更形式的说,设原题三个括号中的生成函数分别为 \(A(x),B(x),C(x)\),有
\[ F(x)={\displaystyle\large\sum_{n=0}^{+\infty}}\sum_{i=0}^{+\infty}\sum_{j=0}^{+\infty}\sum_{k=0}^{+\infty}[n=i+j+k]{n\choose i\quad j \quad k}a_ib_jc_kx^n \]
​ 对于有标号的组合对象,我们在转移时还要考虑不同的标号排列,于是我们在分母上填了阶乘,这样就可以帮助我们转移了。接下来,我们来看一下这个叫组合对象的基础概念。

组合对象

​ 组合计数问题一般定义了一类组合对象 \(A\) ,它可能是满足某一类性质的树、图、串等对象的集合;其中每个对象 \(a \in A\) 都被赋予了一个大小 \({\rm size}(a) \in\mathbb N\),它可能代表节点数,序列长度等。对于某个固定的 \(n\),满足 \({\rm size}(a)=n\) 的对象是有限的,记作 \(A_n\) 。我们的任务通常为求出 \(A_n\) 的数值。

​ 根据不同问题的要求,组合对象可以分为有标号和无标号两类。

(论文)

​ 比较概念性的东西,为了加深对组合意义的理解。

​ 在例题1-1-1中,不同砝码组合构成的集合就是我们要研究的组合对象,每一种砝码组合就是一个对象,对象 \(a\) 的 \(\rm size\) 定义为这个砝码组合的质量和,\(A_n\) 表示质量和为 \(n\) 的砝码组合的方案数,该组合对象属于无标号组合对象;

​ 在例题1-1-3中,不同 \(n\) 位数( \(n\) 个数字的排列)构成的集合就是我们的组合对象,一个 \(n\) 位数就是一个对象,对象 \(a\) 的 \(\rm size\) 定义为数的位数,\(A_n\) 表示构成 \(n\) 位数的方案数,该组合对象属于有标号组合对象。

​ 稍微理解一下“组合对象”这个名词就好。

基础公式

​ 仅仅只是表示成几个式子的乘积只是生成函数最基本的部分,利用形式幂级数的变形进行推导才是比较有研究价值的地方,接下来,我们来展示一些基础而重要的公式并给出其应用。

公式

  • 公式 \(\rm I\)

\[ \displaystyle (1-x)^{-1} = \sum_{n=0}^{+\infty}x^n\\ \]

​ 也被称作无穷递缩等比数列求和公式,由于收敛性,\(x\in(0,1)\) 时式子成立,但由于本文讲的是生成函数,写出来的但式子是形式幂级数,所以 \(x\) 不能代具体的数。

​ 把左边的分母乘到右边去就可以得证,或者直接套用等比数列求和公式证明。

  • 公式 \(\rm II\)

\[ \quad\displaystyle (1-x)^{-k} = \sum_{n=0}^\infty{n+k-1\choose k-1}x^n = \sum_{n=0}^\infty{n+k-1\choose n}x^n \]

​ 可以由公式 \({\rm I}\) 两边同求 \(k-1\) 次导,再同除以 \((k-1)!\) 得到。 也可以把式子转化为 \({\big(}(1-x)^{-1}{\big)}^k\) ,用隔板法证明。

  • 公式 \(\rm{III}\) (广义二项式定理)

\[ (x + y)^\alpha = \sum_{i=0}^{+\infty}{\alpha \choose i}x^iy^{\alpha -i} \]
​ 其中 \(\displaystyle{\alpha \choose k}={\alpha(\alpha - 1)\cdots(\alpha - k + 1)\over k!}={\alpha^{{\underline k}}\over k!}\)

​ 可以利用广义二项式定理推导公式 \(\rm{I}\) 和公式 \(\rm{II}\) 。

  • 公式 \(\rm{IV}\) (泰勒展开)

\[ f(x)=\sum_{n=0}^\infty {f^{(n)}(a)\over n!}(x-a)^n \]

​ 表示 \(f(x)\) 在 \(x=a\) 处的泰勒展开,其中 \(f^{(n)}\) 表示 \(f\) 的 \(n\) 阶导函数,其中 \(a=0\) 的情况被称作麦克劳林展开,形式如下:
\[ f(x)=\sum_{n=0}^\infty {f^{(n)}(0)\over n!}x^n \]

  • 公式 \(\rm V\)

\[ \displaystyle e^x = \sum_{n=0}^{+\infty}{1\over n!}x^n\\ \]

​ 直接套用麦克劳林展开公式就可以得到,注意 \(e^x\) 的导数是它本身。

上一篇:数字反转 NOIp普及组2011


下一篇:中国剩余定理 $CRT$