精华内容
下载资源
问答
  • 一些常见数列的生成函数推导

    千次阅读 2016-11-14 23:07:07
    曾经有人问过我:“斐波那契数列的生成函数长啥样?” 。。。所以这东西我还是写一发吧 它有什么用?它没啥用。。。1.齐次线性递推数列定义:给定常数k,a1,a2,...,ak,h0,h1,...,hk−1k,a_1,a_2,...,a_k,h_0,h_1,.....

    曾经有人问过我:“斐波那契数列的生成函数长啥样?”
    。。。所以这东西我还是写一发吧
    它有什么用?它没啥用。。。

    1.齐次线性递推数列

    定义:给定常数k,a1,a2,...,ak,h0,h1,...,hk1,构造如下数列:
    hn={hna1hn1+a2hn2+...+akhnkn<knk
    称作齐次线性递推数列。
    多项式
    F(x)=h0+h1x+h2x2+...
    被称作这个数列的一般生成函数。

    说到齐次线性递推数列,最经典的就是斐波那契数列。
    定义不用给了吧……

    斐波那契数列的生成函数是这个样子的:
    F(x)=1+x+2x2+3x3+5x4+8x5+...

    如何用一些有限项的多项式来表示这个级数?

    我们构造这样一个函数:
    A(x)=1xx2
    易验证:
    F(x)A(x)=1
    即:
    F(x)=11xx2

    这是为什么呢?
    原因很简单,对于n2
    [n](F(x)A(x))=[n]F(x)[n1]F(x)[n2]F(x)=0
    其中[n]F(x)代表F(x)n次项系数

    这个结论有一些很好玩的结果,比如代入x=0.01,有:
    10.9899=1.010203050813213455...
    我们还可以知道,如果把斐波那契数列写成这样:
    1
    11
    112
    1113
    11115
    111118
    1111113
    11111121

    然后把每一位从上到下加起来,将会出现长度为89的循环节,因为10.89是个有理数……

    我们可以把这个推广到一般形式:

    对于递推式
    hn=a1hn1+a2hn2+...+akhnk
    的生成函数
    F(x)=h0+h1x+h2x2+...

    构造函数:
    H(x)=h0+h1x+h2x2+...+hk1xk1
    A(x)=1a1xa2x2...akxk
    则:
    F(x)A(x)=H(x)A(x) mod xk
    F(x)=H(x)A(x) mod xkA(x)

    可以看出这个形式十分的优雅,不过我并不知道这个优雅的形式与数列本质有什么关联……

    这东西有啥用?
    给出一个k阶线性递推方程,求第n项,n,k105
    暴力O(nk),矩乘k3logk,全挂了……
    FFT可以O(nlogn)
    叫我毒瘤。

    2.非齐次线性递推数列

    定义:给定常数k,a1,a2,...,ak,h0,h1,...,hk1,构造如下数列:
    hn={hna1hn1+a2hn2+...+akhnk+g(n)n<knk
    称作非齐次线性递推数列。
    其中g(n)是关于n的函数,可以是常函数

    要求用一些有限项多项式来表示级数:
    F(x)=h0+h1x+h2x2+...

    和之前一样,构造多项式:
    H(x)=h0+h1x+h2x2+...+hk1xk1
    A(x)=1a1xa2x2...akxk
    G(x)=g(0)+g(1)x+g(2)x2+...
    则:
    F(x)A(x)=H(x)A(x) mod xk+(G(x)G(x) mod xk)
    F(x)=[H(x)A(x)G(x)] mod xk+G(x)A(x)

    所以如果G(x)能被有限项多项式表示的话就做完了。。。
    g(n)=1,则G(x)=1+x+x2+...=11x
    g(n)=n,则G(x)=x+2x2+3x3...=x(1x)2
    g(n)=n2,则G(x)=x+4x2+9x3...=x(x+1)(1x)3
    以此类推,如果g函数是个多项式的话还是可以表示出来的

    3.卡特兰数列

    定义:
    hn={1h0hn1+h1hn2+...+hn1h0n=0n1

    F(x)=h0+h1x+h2x2+...

    容易发现这个递推式本身就是一个卷积,所以我们直接把这个多项式自乘一下
    F2(x)=h1+h2x+h3x2+...=F(x)1x
    解得
    F(x)=114x2x
    即为卡特兰数列的生成函数。

    4.。。。我并不知道这数列叫啥名字,暂且称作广义卡特兰数列吧。。。
    我们都知道卡特兰数列的第n项代表n个元素的入栈出栈序列数,即从原点走到(n,n)不跨越y=x的方案数
    那么,定义广义卡特兰数列hk(n)表示n+k个元素入栈出栈后栈中剩余k个元素的入栈出栈序列数,即从原点走到(n+k,n)不跨越y=x的方案数
    求生成函数:
    Fk(x)=hk(0)+hk(1)x+hk(2)x2+...

    考虑栈中剩余的这k个元素,第i个元素放进去之后就不动了,然后经历了一些入栈弹栈,然后塞入第i+1个元素
    换句话说我们可以把第i个元素看做栈底,然后进行了一堆入栈出栈操作,然后栈空了,然后塞进第i+1个元素……
    如果中间这些走了个过场的元素数量为s,那么方案数是多少?
    h0(s),即卡特兰数列第s
    于是问题就简单了,我们把n个元素的序列分成k+1段,如果一段有s个元素,方案数是h0(s),求方案数

    会生成函数的看到这里已经懂了吧。

    构造函数H(x)=h0(0)+h0(1)x+h0(2)x2+...=114x2x
    Fk(x)=Hk+1(x)=(114x2x)k+1

    展开全文
  • 证明基本都是用TaylorTaylorTaylor公式(见2009毛杰明集训队论文) &amp;lt;1,1,1,1,1....&amp;gt;⇒ez&amp;lt;1,p,p2,p3,p4....&amp;gt;⇒epz&amp;lt;1,−1,1,−1,1....&...1,0,−1,0,...

    证明基本都是用TaylorTaylor公式(见2009毛杰明集训队论文)
    &lt;1,1,1,1,1....&gt;ez&lt;1,p,p2,p3,p4....&gt;epz&lt;1,1,1,1,1....&gt;ez&lt;1,0,1,0,1....&gt;ez+ez2&lt;1,0,1,0,1,0.1....&gt;eiz+eiz2 &lt;1,1,1,1,1....&gt;\Rightarrow e^z\\ &lt;1,p,p^2,p^3,p^4....&gt;\Rightarrow e^{pz}\\ &lt;1,-1,1,-1,1....&gt;\Rightarrow e^{-z}\\ &lt;1,0,1,0,1....&gt;\Rightarrow \frac{e^z+e^{-z}}{2}\\ &lt;1,0,-1,0,1,0.-1....&gt;\Rightarrow \frac{e^{iz}+e^{-iz}}{2}

    展开全文
  • 生成函数详解

    2019-09-25 14:58:08
    目录 生成函数(母函数)详解 预备知识 广义二项式定理 形式幂级数 普通生成函数(OGF) 定义 常见的OGF 运用OGF推导数列通项 生成...

    生成函数(母函数)详解

    预备知识

    广义二项式定理

    广义二项式定理是把一般的二项式定理从整数域推广到了实数域

    定义:

    \[C_{\alpha}^{k}=\begin{cases} \frac{\alpha(\alpha-1)(\alpha-2) \dots (\alpha-k+1)}{k!},k>1 \\ 1,k=0 \\ 0,k<0 \end{cases}(k \in \mathbb{Z},\alpha \in \mathbb{R})\]

    那么有

    \[(x+y)^{\alpha}=\sum_{k=0}^{\infin} C_{\alpha}^{k} x^{\alpha-k}y^k (\alpha \in \mathbb{R})\]

    推论:

    (1) \[(x+y)^n=\sum_{k=0}^{n} C_{n}^{k} x^{n-k}y^k (n \in \mathbb{N^+})\]

    容易看出,这就是一般的二项式定理。

    ​ 证明:拆成两部分

    \[ \begin{aligned} (x+y)^n &=\sum_{k=0}^{\infin} C_{n}^{k} x^{n-k}y^k \\ &=\sum_{k=0}^{n} C_{n}^{k} x^{n-k}y^k+ \sum_{k=n+1}^{\infin} C_{n}^{k} x^{n-k}y^k\end{aligned}\]

    注意到当\(n,k \in \mathbb N\),且\(n<k\)时,\(\frac{n(n-1)(n-2) \dots (n-k+1)}{k!}\)的分子中一定有一项是0,所以\(C_n^k=0\)

    那么\((x+y)^n=\sum_{k=0}^{n} C_{n}^{k} x^{n-k}y^k (n \in \mathbb{N^+})\)

    (2) \[(x+y)^{-n}=\sum_{k=0}^{\infin} (-1)^k C_{n+k-1}^{n-1} x^{n-k}y^k (n \in \mathbb{N^+})\]

    证明:

    \[\begin{aligned} C_{-n}^{k} &=\frac{(-n)(-n-1)(-n-2) \dots (-n-k+1)}{k!} \\ &= (-1)^k \frac{n(n+1)(n+2) \dots (n+k-1)}{k!} \\ &=(-1)^k C_{n+k-1}^{k}=(-1)^k C_{n+k-1}^{n-1}\end{aligned}\]

    代入广义二项式定理的表达式,

    \[(x+y)^{-n}=\sum_{k=0}^{\infin}(-1)^k C_{n+k-1}^{n-1} x^{n-k}y^k (n \in \mathbb{N^+})\]

    形式幂级数

    定义\[A(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n+\dots=\sum_{i=0}^{\infty} a_ix^i\]为以x为未定元的一个形式幂级数。在形式幂级数中,我们不关心x的取值和级数是否收敛,把x作为形式,只关心系数。

    再介绍一下形式幂级数的基本运算,下面会用到。

    加法就是把对应项的系数相加

    \[A(x)+B(x)=\sum_{n=0}^{\infty} (a_n+b_n)x^n\]

    乘法和多项式乘法类似

    \[A(x) \cdot B(x)=\sum_{n=0}^{\infty} \sum_{k=0}^n a_kb_{n-k}\]

    普通生成函数(OGF)

    定义

    对于一个序列\(a\),我们定义\(f(x)=\sum_{n=0}^{\infty} a_nx^n\)\(a\)的生成函数(又叫母函数).\(f(x)\)是一个形式幂级数。至于是有限项还是无限项在做题中影响不大,只要按照题目意义做就可以了。

    比如序列\(1,2,3\)的生成函数就是\(1+2 \times x^2+3 \times x^3\)

    生成函数可以帮我们解决一些计数问题。

    有1克、2克、3克、4克的砝码各一枚,能称出哪几种重量?每种重量各有几种可能方案(选的砝码种类不同,或个数不同看成不同方案)?

    每个砝码可以选或不选,不选看成1,选看成\(x^i\)

    那么生成函数就是

    \[\begin{aligned} f(x) &=(1+x^1)(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} \end{aligned}\]

    发现指数表示重量,系数表示方案数。比如\(2x^6\)表示凑出重量6有两种方案,分别是\(x^1x^2x^3\)\(x^2x^4\),即1g,2g,3g砝码或2g,4g砝码。因此,在用生成函数解决计数问题时,指数往往表示某种条件,而系数表示该条件下的方案数

    求用1分、2分、3分的邮票贴出不同数值的方案数

    这个问题的生成函数就是无限项的。

    \(g(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+x^9+...)\)

    我们要求贴出数值4的方案数,那就要求出\(x^4\)的系数

    常见的OGF

    等比数列形式

    \(a={1,1,1,1,1 \dots}, \ f(x)=1+x+x^2+x^3+\dots=\frac{1}{1-x}\)

    证明:

    这是一个公比为\(x\)的等比数列求和的形式,那么\(f(x)=\frac{1-x^n}{1-x}\),当\(n \to + \infin\)时,\(x^n \to 0,f(x ) \to \frac{1}{1-x}\).因此我们可以写成\(f(x)=\frac{1}{1-x}\),因为式子中x的取值无意义。

    同理有\(f(x)=1+x^2+x^4+x^6+\dots=\frac{1}{1-x^2}\)

    \(f(x)=\sum_{n=0}^{\infty}x^{kn}=\frac{1}{1-x^{k}}\)

    组合数形式

    \(a=1,2,3,4,5 \dots , \ f(x)=1+x+2x^2+3x^3+\dots=\frac{1}{(1-x)^2}\)

    证明:

    根据上面提到的多项式乘法的性质

    \(\begin{aligned} 1+x+2x^2+3x^3+\dots&=(1+x+x^2+x^3+\dots)(1+x+x^2+x^3+\dots) \\&=\frac{1}{1-x}\cdot \frac{1}{1-x}=\frac{1}{(1-x)^2} \end{aligned}\)

    容易发现\(1 + 3x + 6x^2 + 10x^3 + 15x^4...=\frac{1}{(1-x)^3}\)。实际上,我们有:

    \[\frac{1}{(1-x)^n}=\sum_{i=0}^{\infty} C_{i+n-1}^{n-1} x^i (n \in \mathbb{N}^+)\]

    证法一(组合意义):

    我们发现第i项系数就是从k个\((1+x+x^2+x^3+\dots)\)中每个选出一项,乘起来恰为\(x^i\)的方案数。那么问题就变成了\(i=x_1+x_2+ \dots x_k\)的解的组个数。这是组合数学里插板法的经典问题。即把i个相同物品分到k个不同的盒子里面,允许盒子为空。答案是\(C_{i+k-1}^{k-1}\)

    证法二(广义二项式定理):

    根据我们已经证明的推论(2),

    \[(x+y)^{-n}=\sum_{k=0}^{\infin}(-1)^k C_{n+k-1}^{n-1} x^{n-k}y^k (n \in \mathbb{N^+})\]

    \[\begin{aligned}\frac{1}{(1-x)^n}&=(1-x)^{-n} \\ &=\sum_{k=0}^{\infin}(-1)^k C_{n+k-1}^{n-1}(-x)^k \\ &=\sum_{k=0}^{\infin}(-1)^k C_{n+k-1}^{n-1}x^k(-1)^k \\ &=\sum_{k=0}^{\infin}(-1)^{2k} C_{n+k-1}^{n-1}x^k\end{aligned}\]

    显然\((-1)^{2k}=1\)

    \[\therefore \frac{1}{(1-x)^n}=\sum_{i=0}^{\infty} C_{i+n-1}^{n-1} x^i \]

    运用OGF推导数列通项

    斐波那契数列

    斐波那契数列\(F\)满足\(F_n=F_{n-1}+F_{n-2} (n \geq 3),F_1=F_2=1\).

    那么它的生成函数\(f(x)=x+x^2+2x^3+3x^4+5x^5 \dots\)

    常见套路,类似推导等比数列求和公式,错位相减

    \(xf(x)=x^2+x^3+2x^4+3x^5+\dots\)

    \(f(x)-xf(x)=x+x^3+x^4+2x^5+3x^6=x+x^2f(x)\)

    移项,得\((x^2-x+1)f(x)=x\),对\(x^2-x+1\)在实数范围内因式分解,那么

    \[f(x)=\frac{x}{x^2-x+1}=\frac{x}{(1-\frac{1-\sqrt{5}}{2}x)(1-\frac{1+\sqrt{5}}{2}x)}\]

    注意到\[ \frac{1}{(1-\frac{1+\sqrt{5}}{2}x)}-\frac{1}{(1-\frac{1-\sqrt{5}}{2}x)}=\frac{\sqrt{5}x}{(1-\frac{1-\sqrt{5}}{2}x)(1-\frac{1+\sqrt{5}}{2}x)}\]

    \[ \begin{aligned}\therefore f(x)&= \frac{1}{\sqrt{5}} [ \frac{1}{(1-\frac{1+\sqrt{5}}{2}x)}-\frac{1}{(1-\frac{1-\sqrt{5}}{2}x)}] \\ &= -\frac{1}{\sqrt5}\frac{1}{(1-\frac{1-\sqrt5}{2}x)} + \frac{1}{\sqrt5}\frac{1}{(1-\frac{1+\sqrt5}{2}x)}\end{aligned}\]

    注意到\((1-\frac{1-\sqrt5}{2}x)\)很像我们刚刚提到的等比数列形式中,\(f(x)=\frac{1-x^n}{1-x}=\frac{1}{1-x}\)的形式,那么生成函数中的公比就是\(\frac{1-\sqrt5}{2}x\).

    写回数列形式:

    \[F_n= -\frac{1}{\sqrt5}(\frac{1-\sqrt5}{2})^n + \frac{1}{\sqrt5}(\frac{1+\sqrt5}{2})^n\]

    卡特兰数

    定义\(c_n=\sum_{i=0}^{n-1} c_ic_{n-i-1},c_0=c_1=1\),生成函数\(g(x)=c_0+c_1x+c_2x^2+ c_3x^3 +\dots\)

    \[\begin{aligned} g(x)\cdot g(x)&=c_0^2+(c_0c_1+c_1c_0)x+(c_0c_2+c_1c_1+c_2c_0)x^2+\dots\\ &=c_1+c_2x+c_3x^2+\dots \\ &=\frac{g(x)-c_0}{x} \\ &= \frac{g(x)-1}{x}\end{aligned}\]

    \(\therefore x[g(x)]^2-g(x)+1=0\)

    \(g(x)\)看作未知数,由求根公式得

    \(g(x)=\frac{1\pm \sqrt{1-4x}}{2x}\)

    代入检验,发现只有\(g(x)=\frac{1-\sqrt{1-4x}}{2x}\)满足条件。

    \(\therefore g(x)=\frac{1}{2x}[1-(1-4x)^{\frac{1}{2}}]\)

    根据广义二项式定理

    \[\begin{aligned}(1-4x)^{\frac{1}{2}} &= \sum_{k=0}^{\infty} C_{\frac{1}{2}}^k (-4x)^k \\ &=\sum_{k=0}^{\infty} C_{\frac{1}{2}}^k (-1)^k2^{2k}x^k\end{aligned}\]

    注意我们讨论组合数的时候最好分\(k=0\)\(k>0\)两种情况讨论,否则中间过程中可能会出现负数

    \(k=0\)\(C_{\frac{1}{2}}^k (-1)^k2^{2k}x^k=1\ \ (\forall x \in \mathbb{R},C_{x}^0=1)\)

    \[\begin{aligned} C_{\frac{1}{2}}^{k}&= \frac{\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2) \dots (\frac{1}{2}-k+1)}{k!}\\ &=(-1)^{k-1} \frac{\frac{1}{2}\times \frac{1}{2} \times \frac{3}{2} \times \frac{5}{2} \cdots \frac{2k-3}{2}}{k!} \\ &=(-1)^{k-1} \frac{1 \times 1 \times 3 \times 5 \times \dots (2k-3)}{2^kk!} \\ &=(-1)^{k-1} \frac{\frac{1 \times 2 \times 3 \times 4 \times 5 \times \dots (2k-2)}{2 \times 4 \times 8 \times \dots (2k-2)}}{2^kk!} \\ &= (-1)^{k-1}\frac{\frac{(2k-2)!}{2^{k-1}(k-1)!}}{2^kk!} \\ &=\frac{(-1)^{k-1}}{2^{2k-1}} \cdot \frac{(2k-2)!}{k!(k-1)!} \\ &=\frac{(-1)^{k-1}}{2^{2k-1}} \cdot \frac{1}{k} \cdot \frac{(2k-2)}{(k-1)!(k-1)!} \\ &=\frac{(-1)^{k-1}}{2^{2k-1}} \cdot \frac{1}{k}\cdot C_{2k-2}^{k-1} \end{aligned}\]

    回代,得

    \[\begin{aligned}(1-4x)^{\frac{1}{2}} &= 1+\sum_{k=1}^{\infty} C_{\frac{1}{2}}^{k} (-1)^k 2^{2k} x^k\\ &=1+\sum_{k=1}^{\infty} \frac{(-1)^{k-1}}{2^{2k-1}} \cdot \frac{1}{k}\cdot C_{2k-2}^{k-1} \cdot (-1)^k 2^{2k} x^k \\ &=1+\sum_{k=1}^{\infty}(-1) \times 2 \times \frac{1}{k} C_{2k-2}^{k-1}x^k \\ &= 1-2\sum_{k=1}^{\infty} \frac{1}{k} C_{2k-2}^{k-1}x^k\end{aligned}\]

    \[\begin{aligned} g(x) &=\frac{1}{2x}[1-(1-4x)^{\frac{1}{2}}] \\ &= \frac{1}{2x} (2\sum_{k=1}^{\infty} \frac{1}{k} C_{2k-2}^{k-1}x^k) \\ &= \sum_{k=1}^{\infty} \frac{1}{k} C_{2k-2}^{k-1} x^{k-1}\end{aligned}\]

    注意到\(x^{k-1}\)的系数是\(\frac{1}{k} C_{2k-2}^{k-1} x^{k-1}\),那么\(x^k\)的系数就是\(\frac{1}{k+1} C_{2k}^{k} x^k\)

    因此第\(n\)项的系数为\(\frac{C_{2n}^n}{n+1}\)

    卡特兰数的通项公式为:

    \[c_n=\frac{C_{2n}^{n}}{n+1}\]

    转载于:https://www.cnblogs.com/birchtree/p/11575252.html

    展开全文
  • 生成函数学习笔记

    2021-01-04 10:38:00
    文章目录生成函数学习笔记前置知识导数理解简单函数复杂函数四则运算复合函数反函数积分泰勒展开常用函数泰勒展开式莱布尼茨公式广义二项式定理普通生成函数(ogf)数列 转 ogf形式幂级数常见ogf指数生成函数(egf...

    生成函数学习笔记

    前置知识

    导数

    理解

    对函数进行拟合

    简单函数

    f(x)f(x) f(x)f'(x)
    cc 00
    axnax^n anxn1anx^{n-1}
    axa^x axlnaa^x\ln a
    exe^x exe^x
    logaxlog_ax 1xlna\frac{1}{x\ln a}
    lnx\ln x 1x\frac{1}{x}
    sinx\sin x cosx\cos x
    cosx\cos x sinx-\sin x

    复杂函数

    四则运算

    (x+y)=x+y(xy)=xy(xy)=xy+xy(xy)=xyxyy2 (x+y)'=x'+y'\\ (x-y)'=x'-y'\\ (xy)'=x'y+xy'\\ (\frac{x}{y})'=\frac{x'y-xy'}{y^2}

    复合函数

    f(g(x))=f(g(x))g(x) f(g(x))'=f'(g(x))g'(x)

    eg:
    (ex2) (e^{x^2})'\\
    f(x)=ex,g(x)=x2f(x)=e^x,g(x)=x^2
    原式为 f(g(x))f(g(x))'
    f(x)=ex,g(x)=2x f'(x)=e^x,g'(x)=2x
    于是
    f(g(x))=2xex2 f(g(x))'\\ =2xe^{x^2}

    反函数

    如果 f(x)f(x) 的反函数是 g(x)g(x),则 f(x)=1g(x)f'(x)=\frac{1}{g'(x)}

    反函数:交换 x,yx,y 所得函数

    eg:
    y=exx=lny y=e^x\\ x=\ln y
    互为反函数

    y=ex=1x=yx=1y=1y=1ex y'=e^x=\frac{1}{x'}=y\\ x'=\frac{1}{y}=\frac{1}{y'}=\frac{1}{e^x}

    积分

    似乎只能查表背诵?
    好像还能拼凑

    泰勒展开

    f(x)=i=0f(i)(x0)i!(xx0)i f(x)=\sum^{\infty}_{i=0}\frac{f^{(i)}(x_0)}{i!}(x-x_0)^i
    x0x_0 处拟合函数
    x0=0x_0=0 时,可以将封闭形式展开

    eg:
    f(x)=11xf(i)(x)=i!(1x)if(i)(x0)=f(i)(0)=1f(x)=1+x+x2+...+xn=i=0xi f(x)=\frac{1}{1-x}\\ f^{(i)}(x)=\frac{i!}{(1-x)^i}\\ f^{(i)}(x_0)=f^{(i)}(0)=1\\ f(x)=1+x+x^2+...+x^n\\ =\sum_{i=0}^{\infty}x^i

    常用函数的泰勒展开式

    封闭形式 展开式
    11x\frac{1}{1-x} i=0xi\sum_{i=0}^{\infty}x^i
    exe^x i=0xii!\sum_{i=0}^{\infty}\frac{x^i}{i!}
    sinx\sin x i=0(1)i1(2i+1)!x2i+1\sum_{i=0}^{\infty}(-1)^i\frac{1}{(2i+1)!}x^{2i+1}
    cosx\cos x i=0(1)i1(2i)!x2i\sum_{i=0}^{\infty}(-1)^i\frac{1}{(2i)!}x^{2i}
    ln(1+x)\ln (1+x) i=0(1)ixii\sum_{i=0}^{\infty}(-1)^i\frac{x^i}{i}
    (1+x)a(1+x)^a i=0aii!xi\sum_{i=0}^{\infty}\frac{a^{\overline i}}{i!}x^i

    莱布尼茨公式

    (xy)(n)=i=0n(ni)x(i)y(ni) (xy)^{(n)}=\sum_{i=0}^n\tbinom{n}{i}x^{(i)}y^{(n-i)}

    证明:
    假设 n1n-1 时成立
    (xy)(n)=((xy)(n1))=(i=0n1(n1i)x(i)y(ni1))=i=0n1(n1i)(x(i+1)y(ni1)+x(i)y(ni)) (xy)^{(n)}\\ =((xy)^{(n-1)})'\\ =(\sum_{i=0}^{n-1}\tbinom{n-1}{i}x^{(i)}y^{(n-i-1)})'\\ =\sum_{i=0}^{n-1}\tbinom{n-1}{i}(x^{(i+1)}y^{(n-i-1)}+x^{(i)}y^{(n-i)})
    考虑对于 x(i)y(ni)x^{(i)}y^{(n-i)} 的系数只会有两项有贡献
    (n1i)+(n1i1)=(ni) \tbinom{n-1}{i}+\tbinom{n-1}{i-1}=\tbinom{n}{i}
    所以
    (xy)(n)=i=0n(ni)x(i)y(ni) (xy)^{(n)}=\sum_{i=0}^n\tbinom{n}{i}x^{(i)}y^{(n-i)}
    数学归纳法,n=1n=1 时原式成立,得证

    广义二项式定理

    定义
    (nm)=i=1m(ni+1)m! \tbinom{n}{m}=\frac{\prod_{i=1}^m(n-i+1)}{m!}

    (x+y)n=i=0(ni)xiyni (x+y)^n=\sum_{i=0}^{\infty}\tbinom{n}{i}x^iy^{n-i}
    将二项式定理拓展到负数域

    普通生成函数(ogf)

    数列 转 ogf

    数列 ogf
    cfncf_n cF(x)cF(x)
    afn+bgnaf_n+bg_n aF(x)+bG(x)aF(x)+bG(x)
    fn>>mf_n >> m xmF(x)x^mF(x)
    fn<<mf_n << m F(x)xm\frac{F(x)}{x^m}
    cnfnc^nf_n F(cx)F(cx)
    nfnnf_n xF(x)xF'(x)
    fnn\frac{f_n}{n} F(x)x\int \frac{F(x)}{x}
    i=0nfi\sum_{i=0}^nf_i F(x)xi=F(x)11xF(x)\sum x^i\\=F(x)\frac{1}{1-x}

    形式幂级数

    不对函数的发散收敛感兴趣,只对系数感兴趣
    因此 xx 的值可以任意,使得函数收敛

    eg:
    i=0+xi=1xn+11x \sum_{i=0}^{+\infty}x^i\\ =\frac{1-x^{n+1}}{1-x}
    此时为保证函数收敛,令 1<x<1-1<x<1
    =11x =\frac{1}{1-x}
    所以
    i=0+xi=11x \sum_{i=0}^{+\infty}x^i=\frac{1}{1-x}

    常见ogf

    指数生成函数(egf)

    题目

    BZOJ3028 食物

    Description

    有若干种物品,每种物品选取的限制如下:
    A :偶数个
    B :小等于 1 个
    C :小等于 2 个
    D :奇数个
    E :4 的倍数个
    F:小等于 3 个
    G:小等于 1 个
    H:3 的倍数个
    求从中选择 n 个物品的方案数,对 10007 取模。
    n10500n ≤ 10^{500}

    Solution

    A(x)=x2i=11x2 A(x) =\sum x^{2i} =\frac{1}{1-x^2}
    B(x)=1+x B(x)=1+x
    C(x)=1+x+x2=1x31x C(x)=1+x+x^2=\frac{1-x^3}{1-x}
    D(x)=x2i+1=x1x2D(x)=xA(x)=x1x2 D(x) =\sum x^{2i+1} =\frac{x}{1-x^2}\\ 或\\ D(x)=xA(x)=\frac{x}{1-x^2}
    E(x)=x4i=11x4 E(x)=\sum x^{4i}=\frac{1}{1-x^4}
    F(x)=1+x+x2+x3=1x41x F(x)=1+x+x^2+x^3=\frac{1-x^4}{1-x}
    G(x)=1+x G(x)=1+x
    H(x)=x3i=11x3 H(x)=\sum x^{3i}=\frac{1}{1-x^3}

    总方案数
    Sum(x)=x(1x)4 Sum(x)=\frac{x}{(1-x)^4}

    然后两种方法

    • 再次变形
      Sum(x)=x(xi)4=x(i+33)xi Sum(x)=x(\sum x^i)^4=x\sum \tbinom{i+3}{3}x^i
      [xn]Sum(x)=(n+23) [x^n]Sum(x)=\tbinom{n+2}{3}

    • 公式暴力展开
      Sum(n)(x)=i=0n(ni)x(i)((1x)4)(ni) Sum^{(n)}(x)\\ =\sum_{i=0}^n\tbinom{n}{i}x^{(i)}((1-x)^{-4})^{(n-i)}
      发现当 i>1i>1x(i)=0x^{(i)}=0,当 i=0i=0x(i)=x=x0=0x^{(i)}=x=x_0=0
      所以
      Sum(n)(x)=n((1x)4)(n1)=ni=4n+2i(1x)n3 Sum^{(n)}(x)\\ =n((1-x)^{-4})^{(n-1)}\\ =\frac{n\prod_{i=4}^{n+2}i}{(1-x)^{-n-3}}
      Sum(n)(x0)=ni=4n+2i Sum^{(n)}(x_0)=n\prod_{i=4}^{n+2}i
      [xn]Sum(x)=Sum(n)(x0)n!=n(n+1)(n+2)6 [x^n]Sum(x)=\frac{Sum^{(n)}(x_0)}{n!}=\frac{n(n+1)(n+2)}{6}

    边读入边取模,计算即可

    Code

    #include <bits/stdc++.h>
    using namespace std;
    
    const int mod = 10007;
    int a;
    
    inline int power(int s, int c) {
      int ans = 1;
      for (; c; c >>= 1, s = s * s % mod)
        if (c & 1) ans = ans * s % mod;
      return ans;
    }
    
    signed main() {
      char x = getchar();
      for (; x >= '0' && x <= '9'; x = getchar()) a = ((a * 10) + (x & 15)) % mod;
      printf("%d\n", a * (a + 1) % mod * (a + 2) % mod * power(6, mod - 2) % mod);
      return 0;
    }
    
    展开全文
  • 您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ? 我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。 如何生成斐波那契數列 斐波那契...
  • 4.linspace(a,b,n)线性等分,a、b为等差数列的初值和终值,n是节点数 5.logspace(as,bf,n)等比数列 6.size(a)查验矩阵维数 7.length(a)查验向量的维数 8.sqrt(x)根号x 9.real(x)x的实部 10....
  • 您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ? 我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。 如何生成斐波那契數列 斐波那契(Fibonacci)數...
  • 文章目录题目描述什么是斐波那契数列请写出生成斐波那契数列的函数实现方法1:递归 O(2^n)实现方法2:从底层开始循环计算 O(n)实现方法3:动态规划 O(n)其他实现方法 斐波那契数列是一道非常经典的面试题,因为它...
  • 从最常见的裴波那切数列说起 斐波那契(Fibonacci)數列是一个非常简单递归数列,除第一个和第二个数外,任意一个数都可由前两个数相加得到。用计算机程序输出斐波那契數列前 N 个数是一个非常简单问题,许多...
  • 您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ? 我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。 如何生成斐波那契數列 斐波那契...
  • Python 3 生成

    2021-01-19 22:25:56
    生成器 在 Python 中,使用了 yield 的函数被称为生成器(generator)。 跟普通函数不同是,生成器是一个返回迭代器的函数,只能用于...下面是一个所有语言都常见的例子,斐波那契数列: import sys from builtins
  • 第九节 函数2

    2021-01-30 16:43:48
    常见的递归:阶乘、斐波那契数列(Fibonacci sequence) 内置函数中常用函数 range(start,stop,step) 数组序列生成器,左闭右开,可设定步长。默认初始值为0,步长为1。 zip() zip本意指拉链,即将几组序列数据...
  • 您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ?我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。如何生成斐波那契數列斐波那契(Fibonacci)數列是...
  • python 函数学习 yield

    2014-09-28 17:09:41
    您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ?我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。如何生成斐波那契數列斐波那契(Fibonacci)數列是...
  • Python yield生成器详解

    2021-01-03 16:19:14
    您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ? 我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。 如何生成斐波那契數列 斐波那契(Fibonacci)數...
  • 您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ?我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。如何生成斐波那契數列斐波那契(Fibonacci)數列是...
  • python-yield 生成

    2017-10-12 20:58:41
    您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ? 我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。 yield 讲解 如何生成斐波那契數列 斐波那契...
  • 您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ? 我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。 如何生成斐波那契數列 斐波那契(Fibonacci...
  • Python ----生成器 yield

    2019-02-22 15:18:55
    您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ? 我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。 如何生成斐波那契數列 斐波那契(Fibonacci)...
  • 您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ? 我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。 如何生成斐波那契數列 斐波那契(Fibonacci)...
  • matlab之linspace与logspace函数

    千次阅读 2020-03-06 20:30:42
    意思是生成一个行向量,共n个元素,第一个数为x1,最后一个数为x2,每个数之间间隔为 (x2-x1)/(n-1),即是一个等差数列,例如: >> y = linspace(0,10,5) >y= > 0 2.5000 5.0000 7.5000 10.0000 %可见...
  • 带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ?我们先抛开 generator,以一个常见的编程题目来展示 yield 概念。如何生成斐波那契數列斐波那契(Fibonacci)數列是一个非常简单...
  • Python常见面试题

    千次阅读 2020-08-31 11:30:40
    1.如何用一行代码生成[1,3,5,7,9,11...使用random模块可以轻松搞定,不得不说这个random库其实很有用,里面有很多重要的函数值得大家熟练掌握 6.如何删除list里面重复元素并保证顺序并不变化 很多人第一时间会想到
  • Matlab空数组与子数组两个常见的特殊数组生成其相应子数组生成数组方式的函数(1)linspace :以等差数列生成数组(2)logspace:以等比数列生成数组其他:reshape 函数 两个常见的特殊数组 nullmatrix = [ ] ...
  • python中numpy常见运算

    千次阅读 2018-03-05 16:00:55
    1.矩阵创建 1)list方法生成矩阵 2)数组函数arange 生成矩阵 arange(start,end,step) arange(end) .reshape(行,列) 默认从1开始 3)创建0/1矩阵 np.zeros((行,列)) np.ones((行,列)) 4)等差数列 np....
  • 原文地址: ... 斐波拉契数列用列表生成式写不出来,但是,用函数把它打印出来却很容易: def fib(max):
  • 3.了解数据生成函数。 二、实验内容 1.调用pyplot查看数据分布图像 2.调用numpy.arange生成等差数列 3.调用scipy.stats生成常见分布数量数据 4.调用numpy.random.poisson生成泊松分布数量数据 三、实验要求 以...
  • 详解Python中yield

    2020-03-23 11:13:19
    您可能听说过,带有 yield 的函数在 Python 中被称之为 generator(生成器),何谓 generator ? 我们先抛开 generator,以一个常见的编程题目来展示 yield 的概念...用计算机程序输出斐波那契数列的前 N 个数是一...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 187
精华内容 74
关键字:

常见数列的生成函数