【学习笔记】母函数Part1

大概是好久之前的学习笔记?

边复习边发吧。其实MO再不做题的时候,拿来磨磨脑子也挺有意思的。

这一部分大概是从「基础组合计数」到「一般型母函数」,再到「线性循环数列」。

二项式定理

一点瞎扯

考虑二项式定理 $(x+y)^n=\sum\binom{n}{i}x^iy^{n-i}$,由于展开成了二元多项式的形式,所以存在卷积性质。利用此或可证明一些东西。

一点有趣的证明题

A

证明:

考虑一个式子:$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$。那么对于原式的右边就可以化成

B

证明

考虑 $(1+x)^{n+1}$ 的两种展开方式:

比较两个多项式中 $i+1$ 项的系数,可知证毕。

形式幂级数

关于 $\frac{1}{1-x}$

设该商为 $\sum c_nx^n$。那么有

可知 $c_0=1,c_i=c_{i-1}$ 。所以每一项的系数都为 $1$ 。故有形式幂级数基本定理:

一系列求母函数例子

部分分式

这一章的作用在于把一个复杂的计数问题转化为许多个简单的 $\rm OGF$ 的形式。

预备定理

设 $\frac{P(x)}{Q(x)}$ 是一个真分式,$a$ 是 $Q(x)$ 的一个 $k$ 重根,那么存在一个数列 $A_{1\sim k}$ 使得

其中 $\frac{P’(x)}{Q’(x)}$ 依旧是真分式。

懒得证了。感性理解。

部分分式定理

设 $\frac{P(x)}{Q(x)}$ 是一个真分式,如果 $a_1,a_2,\cdots a_m$ 分别是多项式 $Q(x)$ 的 $k_1,k_2,\cdots k_m$ 重根。那么存在一张数表 $\mathbf A$ ,使得

由预备定理可知显然。

例题

(1)

分解 $\frac{1}{x^3-x^2-x+1}$ 为部分分式。

首先因式分解可以知道 $1$ 是他的二重根,$-1$ 是他的一重根。那么可以根据部分分式定理得到

两边通分后发现是个恒等式,于是就可以对 $x$ 用特殊值法得到

然后就没有然后了。

(2)

将分解 $\frac{6x^2+22x+18}{x^3+6x^2+11x+6}$ 为部分分式

继续考虑将分母因式分解。即

那么之后就变成sb题了,分解为 $\frac{1}{x+1}+\frac{2}{x+2}+\frac{3}{x+3}$。

简单组合问题

一般组合问题

设有 $n$ 种不同的物体,分别只能取 $a_1,a_2,a_3\cdots a_n$ 个,如果要取 $r$ 个,有多少种方案。

形式幂级数大概就是

这样。或者考虑一个更特殊的问题,从 $n$ 个不同物品里可以重复地取出 $r$ 个的方案数:

由上面的形式幂级数展开可以知道,这个东西的第 $r$ 项是 $\binom{n-1+r}{n-1}=\binom{n+r-1}{r}$,是个常见的结论。

砝码模型

设有 $n$ 种砝码,质量分别为 $c_1,c_2\cdots c_n$,分别有 $b_1,b_2\cdots b_n$ 枚,求一共可以称出多少种不同质量的物品。

这个东西的形式幂级数大概是

不定方程相关

的非负整数解个数。

很显然是

这里继续把 $1$ 当作一个物品,每个变量只能拿 $p_i$ 的倍数个就很好理解了。

那么这东西的母函数显然是

有关分拆数的拓展

在正整数 $r$ 的所有分拆中, 不超过 $n$ 的有几种?

发现本质上是在求这样一个不定方程

的非负整数解个数。

那么显然就是 $\frac{1}{(1-x)(1-x^2)\cdots(1-x)^n}$

又一个拓展(OI中的应用)

给定 $n$ 和 $c_i(1\leq c_i\leq \rm m)$,求 $0\leq x_i\leq c_i$ 时,$\sum x_i=s$ 的解的数量。

对于前 $30\%$ 的数据,有 $n\leq 16,0\leq m,s\leq 10^9$ 。

对于前 $70\%$ 的数据,有 $n\leq 35,0\leq m,s\leq 10^9$ 。

对于另外 $30\%$ 的数据,有 $1\leq n\leq 5\cdot 10^5,0\leq m,s\leq 100$。

发现大概 $30\%$ 的可以直接大力容斥,最后 $30\%$ 的可以生成函数,中间 $40\%$ 的就需要神秘的 $\rm Meet~in~Middle$ 了。想了想大概就是分成两部分,枚举第二部分的时候顺便乘法原理一下第一部分的结果就完了。

线性循环数列

斐波那契数列通项

考虑斐波那契数列 $\{a_n\}$ 的母函数可以这么得到:

考虑 ① + ② + ③ 得到:

可知

那么考虑如何展开这个东西。令 $r_1,r_2$ 为方程 $1-x-x^2$ 的两个根。那么有

变一下形:

然后有一步很神仙的转化。由

得到

可知

继而可以得到

一般线性循环数列

由上例可知,对于一个给定的 $k$ 阶线性循环数列,求母函数只需要构造出除了前 $k$ 项之外系数都为 $0$ 的幂级数即可。

比如给定数列 $\{a_n\}$ 满足:

那么考虑构造如下四个:

还是 ① + ② + ③ + ④:

就完了。

嗯,剩下的内容就留给下一篇了。