首页 > 其他分享 >普通生成函数学习笔记

普通生成函数学习笔记

时间:2024-02-16 17:57:36浏览次数:35  
标签:infty frac 函数 limits sum 笔记 生成 frac1 aligned

普通生成函数是让一个序列(可以是有限序列,可以是无限序列)的第 \(i\) 项 \(a_i(i\ge0)\) 作为 \(x^i\) 的系数。
序列 \([2,3,4,5]\) 用生成函数表达就是 \(2+3x+4x^2+5x^3\)。
序列 \([1,3,5,7,\ldots]\) 用生成函数表达就是 \(\sum\limits_ {i=0}^\infty(2i+1)x^i\)。


由于这样的生成函数是个多项式,不便计算,所以有些生成函数具有封闭形式。
封闭形式可以通过方程,数列知识等来计算,计算时,要认为生成函数中的 \(x\) 是个极小值,并且算出来是收敛的。
如 \(F(x)=\sum\limits_ {i=0}^\infty x^i=\frac 1{1-x}\) 就是用等比数列求和,或者说几何级数得到的。
那要是是 \(\sum\limits_{i=0}^\infty(i+1)x^i\) 甚至是 \(\sum\limits_{i=0}^\infty\binom{n+i-1}ix^i\) 呢?
答案是 \(\sum\limits_{i=0}^\infty\binom{n+i-1}ix^i=\frac1{(1-x)^n}\)。
证明可以使用广义二项式定理:

\[\begin{aligned} \frac1{(1-x)^n}&=(1-x)^{-n}\\ &=\sum_{i=0}^\infty\binom{-n}i(-x)^i1^{-1-i}\\ &=\sum_{i=0}^\infty\binom{-n}i(-x)^i\\ &=\sum_{i=0}^\infty\frac{(-n)^{\underline i}}{i!}(-x)^i\\ &=\sum_{i=0}^\infty(-1)^i\binom{n+i-1}i(-x)^i\\ &=\sum_{i=0}^\infty\binom{n+i-1}ix^i\\ \end{aligned} \]

同理,\(\sum\limits_{i=0}^\infty\binom{n+i-1}it^ix^i=\frac1{(1-tx)^n}\)。
根据二项式定理,\(\sum\limits_{i=0}^n\binom nix^i=(1+x)^n\)。
至于在 \(F(x)\) 展开式前加了 \(t\) 个 \(0\),就相当于乘以了 \(x^t\),所以添加后就是 \(x^tF(x)\)。


生成函数最直接的用法就是求解递推式。
已知 \(a_0=1,a_1=2,a_n-5a_{n-1}+6a_{n-2}=0\),求 \(a_n\) 的通项公式。

\[\begin{aligned} F(x)=\sum\limits_{i=0}^\infty a_ix^i=a_0+a_1x+a_2x^2&+a_3x^3+\ldots\\ -5F(x)=-5x\sum\limits_{i=0}^\infty a_ix^i=-5a_0x-5a_1x^2&-5a_2x^3-5a_3x^4-\ldots\\ 6x^2F(x)=-5x\sum\limits_{i=0}^\infty a_ix^i=6a_0x^2&+6a_1x^3+6a_2x^4+6a_3x^5-\ldots\\ F(x)-5xF(x)+6x^2F(x)=a_0+(a_1-5a_0)x\\ \end{aligned} \]

把 \(a_0=1,a_1=2\) 带入得到 \(F(x)-5xF(x)+6x^2F(x)=1-3x\),即 \(F(x)=\frac{1-3x}{x^2-5x+6}=\frac1{1-2x}\)。

运用广义二项式定理展开 \(\frac1{1-2x}\),得到 \(F(x)=\sum\limits_{i=0}^\infty2^ix^i\),也就是说 \(a_n=2^n\)。


上面是侥幸把封闭式的分子约分成了 \(1\),但往往是做不到的。
比如斐波那契数列 \(f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}\),求 \(f_n\) 的通项公式。

\[\begin{aligned} F(x)=\sum\limits_{i=0}^\infty f_ix^i=f_0+f_1x+f_2x^2&+f_3x^3+\ldots\\ xF(x)=x\sum\limits_{i=0}^\infty f_ix^i=f_0x+f_1x^2&+f_2x^3+f_3x^4+\ldots\\ x^2F(x)=x^2\sum\limits_{i=0}^\infty f_ix^i=f_0x^2&+f_1x^3+f_2x^4+f_3x^5+\ldots\\ F(x)-xF(x)-x^2F(x)=f_0+(f_1-f_0)x\\ F(x)=\frac x{1-x-x^2}\\ \end{aligned} \]

这个时候可以去想待定系数法拆分 \(F(x)\)。

\[\frac x{1-x-x^2}=\frac A{1-ax}+\frac B{1-bx}=\frac{(-aB-Ab)x+A+B}{abx^2-(a+b)x+1} \]

\[\begin{cases} -aB-Ab=1\\ A+B=0\\ ab=-1\\ a+b=1 \end{cases} \]

\(4\) 个方程,\(4\) 个未知数,由于 \(A,B\) 和 \(a,b\) 地位相同,钦定 \(A\ge B\)。

\[\begin{cases} A=\frac1{\sqrt5}\\ B=-\frac1{\sqrt5}\\ a=\frac{1+\sqrt5}2\\ b=\frac{1-\sqrt5}2 \end{cases} \]

\[\begin{aligned} \frac x{1-x-x^2}&=\frac{\frac1{\sqrt5}}{1-\frac{1+\sqrt5}2x}+\frac{-\frac1{\sqrt5}}{1-\frac{1-\sqrt5}2x}\\ &=\frac1{\sqrt5}(\frac1{1-\frac{1+\sqrt5}2x}-\frac1{1-\frac{1-\sqrt5}2x})\\ &=\sum_{i=0}^\infty\frac1{\sqrt5}((\frac{1+\sqrt5}2)^i-(\frac{1-\sqrt5}2)^i)x^i \end{aligned} \]

所以 \(f_i=\frac1{\sqrt5}((\frac{1+\sqrt5}2)^i-(\frac{1-\sqrt5}2)^i)\)。


卡特兰数的递推式 \(H_n=\sum\limits_{i=0}^{n-1}H_iH_{n-i-1}\) 可以通过 dp 简单求出,其中边界 \(H_0=1,H_1=1\)。
卡特兰数的递推是卷积的形式,可以先计算一下 \(H^2(x)\) 再去计算封闭式。

\[\begin{aligned} H^2(x)&=\sum_{i=0}^\infty(\sum_{j=0}^iH_jH_{i-j})x^i\\ &=\sum_{i=0}^\infty(\sum_{j=0}^{(i+1)-1}H_jH_{(i+1)-j-1})x^i\\ &=\sum_{i=0}^\infty H_{i+1}x^i\\ &=\frac1x\sum_{i=0}^\infty H_{i+1}x^{i+1}\\ &=\frac1x\sum_{i=1}^\infty H_ix^i\\ &=\frac1x(H_0x^0+\sum_{i=1}^\infty H_ix^i-1)\\ &=\frac1x(H(x)-1)\\ \end{aligned} \]

\(xH^2(x)-H(x)+1=0\),即 \(H(x)=\frac{1\pm\sqrt{1-4x}}{2x}\),有增根。
当 \(x=0\) 时,\(H(0)\) 的值就是 \(H_0\),后面的 \(H_ix^i\) 都因为 \(x^i=0\) 为 \(0\)。
使用洛必达法则对 \(H(x)\) 进行求导,来获得 \(x=0^+\) 时的极限。

\[\lim_{x\to0^+}\frac{1\pm\sqrt{1-4x}}{2x}=\frac{\mp\frac2{\sqrt{1-4x}}}2=\mp\frac1{\sqrt{1-4x}} \]

为了让 \(H(0)\) 和 \(H_0\) 的值一样,\(H(x)=\frac{1-\sqrt{1-4x}}{2x}\)。
使用广义二项式定理展开 \(\sqrt{1-4x}\)。

\[\begin{aligned} \sqrt{1-4x}&=(1-4x)^\frac12\\ &=\sum_{i=0}^\infty\binom{\frac12}i(-4x)^i1^{\frac12-i}\\ &=\sum_{i=0}^\infty\frac{(\frac12)^{\underline i}}{i!}(-4x)^i\\ &=1+\sum_{i=1}^\infty\frac{(\frac12)^{\underline i}}{i!}(-4x)^i\\ \end{aligned} \]

接下来去化简 \((\frac12)^{\underline i}\)。

\[\begin{aligned} (\frac12)^{\underline i}&=\frac12\frac{-1}2\frac{-3}2\ldots\frac{-i-3}2\\ &=\frac{(-1)^{i-1}1\times3\times5\times\ldots\times(2i-3)}{2^i}\\ &=\frac{(-1)^{i-1}(2i-2)!}{2^i(i-1)!2^{i-1}}\\ &=\frac{(-1)^{i-1}(2i-2)!}{2^{2i-1}(i-1)!}\\ \end{aligned} \]

\[\begin{aligned} \sqrt{1-4x}&=1+\sum_{i=1}^\infty\frac{(\frac12)^{\underline i}}{i!}(-4x)^i\\ &=1+\sum_{i=1}^\infty\frac{\frac{(-1)^{i-1}(2i-2)!}{2^{2i-1}(i-1)!}}{i!}(-4x)^i\\ &=1-\sum_{i=1}^\infty\frac{(2i-2)!2^{2i}x^i}{2^{2i-1}(i-1)!i!}\\ &=1-\sum_{i=1}^\infty\frac{(2i-2)!}{(i-1)!i!}2x^i\\ &=1-\sum_{i=1}^\infty\frac{(2i-1)!}{(i-1)!i!}\frac1{2i-1}2x^i\\ &=1-\sum_{i=1}^\infty\binom{2i-1}i\frac1{2i-1}2x^i\\ \end{aligned}\\ \]

\[\begin{aligned} H(x)&=\frac{1-\sqrt{1-4x}}{2x}\\ &=\frac{1-(1-\sum\limits_{i=1}^\infty\binom{2i-1}i\frac1{2i-1}2x^i)}{2x}\\ &=\sum\limits_{i=1}^\infty\binom{2i-1}i\frac1{2i-1}x^{i-1}\\ &=\sum\limits_{i=0}^\infty\binom{2i+1}{i+1}\frac1{2i+1}x^i\\ &=\sum\limits_{i=0}^\infty\binom{2i}{i}\frac1{i+1}x^i \end{aligned} \]

最终得到 \(H_n=\binom{2n}n\frac1{n+1}\)。


生成函数的展开式是多项式,生成函数的乘积就是多项式的卷积。我们知道,背包是多项式的加法卷积,所以可以使用生成函数来计算背包问题。

LGP2000 拯救世界

  • 第一种金神石的块数必须是 \(6\) 的倍数,即 \(\sum\limits_{i=0}^\infty x^{6i}=\frac1{1-x^6}\)。
  • 第一种木神石最多用 \(9\) 块,即 \(\sum\limits_{i=0}^9x^i=\frac{1-x^{10}}{1-x}\)。

别的所有石头全部同理,把 \(10\) 种石头的封闭式乘起来,得到 \(\frac1{(1-x)^5}\)。
运用广义二项式定理展开,得到 \(\sum\limits_{i=0}^\infty\binom{i+4}ix^i\)。
那么第 \(n\) 项系数就是 \(\binom{n+4}n\),不过这题要写高精度,所以我写 Python。

import decimal
decimal.getcontext().prec=400000
n=decimal.Decimal(input())
print((n+1)*(n+2)*(n+3)*(n+4)/24)

LGP3726 [AH2017/HNOI2017] 抛硬币
甲抛硬币 \(a\) 次,乙抛硬币 \(b\) 次,问有多少种情况使得甲的正面次数大于乙。
\(a,b\le10^{15}\),\(b\le a\le b+10^4\)

如果甲抛出了正面就把计数器加一,如果乙抛出了正面就把计数器减一。
构造生成函数 \(F(x)=(1+x)^a(1+\frac1x)^b\),那么甲正面的情况就是 \(F(x)\) 的所有正指数系数和 \(\sum\limits_{i=1}^a[x^i]F(x)\),\([x^i]F(x)\) 表示生成函数 \(F(x)\) 的 \(i\) 项系数。

\[\begin{aligned} \sum_{i=1}^a[x^i]F(x)&=\sum_{i=1}^a[x^i](1+x)^a(1+\frac1x)^b\\ &=\sum_{i=1}^a[x^i]x^a(1+\frac1x)^a(1+\frac1x)^b\\ &=\sum_{i=1}^a[x^i]x^a(1+\frac1x)^{a+b}\\ \end{aligned} \]

\[\begin{aligned} x^a(1+\frac1x)^{a+b}&=x^a\sum_{i=0}^{a+b}\binom{a+b}i(\frac1x)^i1^{a+b-i}\\ &=\sum_{i=0}^{a+b}\binom{a+b}ix^{a-i} \end{aligned} \]

要使 \(a-i\ge1\),也就是要做到 \(i\le a-1\),即 \(\sum\limits_{i=0}^{a-1}\binom{a+b}ix^{a-i}=\sum\limits_{i=1}^a\binom{a+b}{a-i}x^i\)。
最后得到 \(\sum\limits_{i=1}^a[x^i]F(x)=\sum\limits_{i=1}^a\binom{a+b}{a-i}=\sum\limits_{i=0}^{a-1}\binom{a+b}{i}\)。
因为 \(a+b\) 很大,\(|a-b|\) 很小,原式就是杨辉三角上的半行减去 \(a\) 到中间那一段。
由于模数非质数,需要 exLucas 计算组合数。


\(n\ge3\),集合 \(A\subseteq[1,2,\ldots,n]\),若 \(\sum\limits_{i\in A}i\) 为奇数,那么称 \(A\) 为奇集合。集合 \(S\) 为所有奇集合组成的集合。求 \(|S|\),以及 \(\sum\limits_{A\in S}\sum\limits_{i\in A}i=\sum\limits_{A\in S}\operatorname{sum}(A)\)。

答案可以乱做,猜一个奇集合数量是全集子集数量的一半 \(2^{n-1}\),每个集合平均有 \(\frac n2\) 个元素,每个元素平均大小 \(\frac{n+1}2\),所以和是 \(2^{n-1}\times\frac n2\times\frac{n+1}2=n(n+1)2^{n-3}\)。猜得很准,这就是答案。

构造生成函数 \(F(x)=\prod\limits_{i=1}^n(1+x^i)\)。
\(F(x)=\prod\limits_{i=1}^n(1+x^i)=\sum\limits_{A\subseteq[1,2,\ldots,n]}x^{\operatorname{sum}(A)}\)
当 \(x=-1\) 时,等式左边为 \(0\),是收敛的,所以不妨把 \(x=-1\) 带入。
当 \(x=-1\) 时,每个奇集合会对等式右边作出 \(+1\) 贡献,否则会作出 \(-1\) 贡献,得到奇集合和非奇集合的数量是相等的,即 \(|S|=\frac12\times2^n=2^{n-1}\)。

\[\begin{aligned} \prod\limits_{i=1}^n(1+x^i)&=\sum\limits_{A\subseteq[1,2,\ldots,n]}x^{\operatorname{sum}(A)}\\ (\prod\limits_{i=1}^n(1+x^i))'&=(\sum\limits_{A\subseteq[1,2,\ldots,n]}x^{\operatorname{sum}(A)})'\\ \sum_{i=1}^n{ix^{i-1}\prod_{j\ne i}{\left( 1+x^j \right)}}&=\sum\limits_{A\subseteq[1,2,\ldots,n]}\operatorname{sum}(A)x^{\operatorname{sum}(A)-1} \end{aligned} \]

带入 \(x=-1\),得到 \(\sum\limits_{A\in S}\operatorname{sum}(A)=\sum\limits_{A\not\in S}\operatorname{sum}(A)\)。
带入 \(x=1\),得到 \(\sum\limits_{A\in S}\operatorname{sum}(A)+\sum\limits_{A\not\in S}\operatorname{sum}(A)=n(n+1)2^{n-2}\)。
最后得到 \(\sum\limits_{A\in S}\operatorname{sum}(A)=\frac12\times n(n+1)2^{n-2}=n(n+1)2^{n-3}\)。

标签:infty,frac,函数,limits,sum,笔记,生成,frac1,aligned
From: https://www.cnblogs.com/bxjz/p/18017329/OGF-learn

相关文章

  • HttprunnerManager部署笔记
    组策略开放协议端口TCP8000httprunnerTCP80nginxTCP15672rabbitMQ2TCP5672rabbitMQTCP3306mysqlTCP22SSH镜像源-ihttps://mirrors.aliyun.com/pypi/simple-ihttps://pypi.tuna.tsinghua.edu.cn/simple-ihttp://pypi.douban.com/simple/修改镜像源(先安......
  • 【学习笔记】扫描线
    bilibili:BV1Mm411D7kr讲了一下。模板代码:面积并:#include<cstring>#include<iostream>#include<algorithm>#defineintlonglongusingnamespacestd;namespaceIO{template<typenameT>Tread(Tx){Tsum=0,opt=1......
  • 【模板】多项式全家桶(多项式初等函数(部分))
    【模板】多项式初等函数同时作为https://github.com/caijianhong/template-poly的document。杂项数域为\(\mathbbF_{998244353}\),所以定义了mint为modint<998244353>。poly是多项式的类型,从std::vector<mint>继承而来。poly的构造函数如下:poly();explicitpoly(......
  • 生成函数从入门到进门
    引入先看下面这个例子:\[(1+a_1x)\times(1+a_2x)\times\cdots\times(1+a_nx)\]拆括号得:\[1+(a_1+a_2+\cdots+a_n)x+(a_1a_2+a_1a_3+\cdots+a_{n-1}a_n)x^2+\cdots+(a_1a_2\cdotsa_n)x^n\]其中\(x^2\)的系数包含了从\(n\)个元素\(\{a_1,a_2,\cdots,a_n\}\)中选取两个的......
  • 读十堂极简人工智能课笔记03_遗传算法与进化
    1. 寻找正确答案1.1. 卡尔·西姆斯1.1.1. 计算机图形艺术家和研究者1.1.2. 演示过数字进化之创造性和新颖性的先驱1.1.3. 1994年1.1.3.1. 创造一批能游泳、走路、跳跃,甚至互相竞争的虚拟动物震惊了整个科学界1.1.3.2. 它们的人工大脑却是个极其复杂的网络,信息经由传......
  • Arduino学习笔记
    教程ArduinoUno单片机零基础入门学用Arduino@B站.太极创客ArduinoNano单片机2023年ArduinoNano教程@B站.唐老思Arduino核心板ArduinoNanoArduino第三方库ArduinoLibraryList......
  • [学习笔记]换根 DP 的常用处理方式
    [学习笔记]换根DP的常用处理方式换根DP,又称作二次扫描法,通常用于“对每个根求出树形DP的答案”。以每个点作为根节点进行一次树形DP的代价通常无法承受,因此我们会使用两次DFS:第一次DFS指定一个点为根节点,运行一次常规的树形DP。第二遍DFS进行换根DP,得到将根转移......
  • Python笔记09——Set(集合)
    九、集合9.1基础集合(set)是一个无序的不重复元素序列,可进行交、集、差等常见的集合操作。与序列的区别:无序,每次输出顺序随机;元素不重复;创建格式:parame={value01,value02,...}或者set(value)(创建空集合只能用set())创建集合示例set1={1,2,3,4}#直接使用......
  • 性能测试-性能压测脚本的生成以及完善和增强
    1.通过JMeter代理服务器录制脚本为什么用JMeter做性能测试时要 设置客户端的代理JMeter在进行性能测试时,设置客户端代理的主要目的是为了监听和记录浏览器在相应端口的操作。通过设置代理,JMeter可以捕获和记录用户的网络请求和响应,从而模拟用户在真实场景中的行为,对系统进行性......
  • gnuradio笔记[3]-播放音频并观测幅度谱
    摘要使用GNURadio观测音频文件的幅度谱并播放音频,将数据保存到wav文件.关键信息GNURadioCompanion:3.10.8.0(Python3.10.13)实现音频文件参数名称参数值音频组成信标信号+音乐文件信标波形正弦波信标频率800Hz信标幅度(Vpp)1000mV信标持续......