精华内容
下载资源
问答
  • 常生成函数
    2020-02-27 22:48:38

    这是一篇关于生成函数题目的汇总

    简单,即博主能做出来的

    中等

    困难

    CF1010F

    更多相关内容
  • 生成函数知识总结

    千次阅读 2020-06-16 22:04:28
    生成函数基础知识OJ练习Fruit HDU - 2152(普通生成函数)排列组合 HDU - 1521(指数生成函数)Ignatius and the Princess III HDU - 1028(普通生成函数)Holding Bin-Laden Captive! HDU - 1085(普通生成函数)...

    基础知识

    (1)普通生成函数: k k k 种元素的多重集合的 r r r 组合数(有限和无限多重集都可以)

    • 数列:1,1, 1, 1, 1的生成函数,也可以表示一个因子的限制
      g ( x ) = 1 + x + x 2 + ⋯ + x n + ⋯ = ∑ n = 0 ∞ x n = 1 1 − x g(x)=1+x+x^2+\dots+x^n+\dots=\sum_{n=0}^{\infty} x^n =\frac 1{1-x} g(x)=1+x+x2++xn+=n=0xn=1x1
    • e 1 + e 2 + ⋯ + e k = n e_1+e_2+\dots+e_k=n e1+e2++ek=n 的正整数解为: C n + k − 1 n C_{n+k-1}^n Cn+k1n。其生成函数如下
      g ( x ) = ∑ n = 0 ∞ C n + k − 1 n x n = 1 ( 1 − x ) k g(x)=\sum_{n=0}^{\infty}C_{n+k-1}^n x^n=\frac {1}{(1-x)^k} g(x)=n=0Cn+k1nxn=(1x)k1

    (2)指数生成函数: k k k 种元素的多重集合的 r r r 排列数(有限和无限多重集都可以)

    (3)生成函数次数表示选择物品的次数

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    解题方法

    对于直接可计算公式的题目
    生成函数为: g ( x ) = ( 1 + x + x 2 + …   ) ( 1 + x 2 + x 4 + …   ) ( 1 + x 3 + x 6 + …   ) … g(x)=(1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)\dots g(x)=(1+x+x2+)(1+x2+x4+)(1+x3+x6+) 请你计算 x m x^m xm 的系数

    解题步骤

    1、列出式子:有 n 项,每项代表一个种类的限制(一个括号代表一项)
    2、初始化C1和C2的系数为 0,拿第一项初始化C1
    3、然后,第一维从 2 到 n 枚举每一项,第二维从 0 到 m 枚举每一个系数( x j x^j xj),第三维枚举每一项中的每一个因子( x k x^k xk),将 x j x^j xj x k x^k xk 的系数相乘,并累加到C2上
    4、第二维结束之后,将C2的系数更新到C1,全部结束后,返回 x m x^m xm的系数C1[m]

    练习题

    HDU - 2152 Fruit (普通生成函数)

    链接:http://acm.hdu.edu.cn/showproblem.php?pid=2152

    题意:有 n 种水果,每种水果出现的次数在 [ a i , b i ] [a_i,b_i] [ai,bi] 之间,问一共买 m 个水果有多少种购买方案?

    思路 ( x a 1 + ⋯ + x b 1 ) ( x a 2 + ⋯ + x b 2 ) … ( x a n + ⋯ + x b n ) (x^{a_1}+\dots+x^{b_1})(x^{a_2}+\dots+x^{b_2})\dots(x^{a_n}+\dots+x^{b_n}) (xa1++xb1)(xa2++xb2)(xan++xbn) 对这个生成函数求 x m x^m xm 的系数

    #include <bits/stdc++.h>
    using namespace std;
    int n,m;
    int a[110],b[110],C1[110],C2[110];
    int solve()
    {
        for(int i=0;i<=m;++i) C1[i]=C2[i]=0;
        for(int i=a[1];i<=b[1];++i) C1[i]=1;
        for(int i=2;i<=n;++i)
        {
            for(int j=0;j<=m;++j)
                for(int k=a[i];k<=b[i];++k)
                    C2[j+k]+=C1[j];
            for(int j=0;j<=m;++j)
                C1[j]=C2[j],C2[j]=0;
        }
        return C1[m];
    }
    int main()
    {
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=1;i<=n;++i)
                scanf("%d%d",&a[i],&b[i]);
            printf("%d\n",solve());
        }
        return 0;
    }
    

    HDU - 1521 排列组合 (指数生成函数)

    链接:http://acm.hdu.edu.cn/showproblem.php?pid=1521

    题意:有 n 种物品,每种物品的数量为 a i a_i ai ,问取 m 个物品的排列数

    思路 ( 1 + x + x 2 2 ! + ⋯ + x a 1 a 1 ! ) ( 1 + x + x 2 2 ! + ⋯ + x a 2 a 2 ! ) … ( 1 + x + x 2 2 ! + ⋯ + x a n a n ! ) (1+x+\frac {x^2}{2!}+\dots+\frac {x^{a_1}}{a_1!})(1+x+\frac {x^2}{2!}+\dots+\frac {x^{a_2}}{a_2!})\dots(1+x+\frac {x^2}{2!}+\dots+\frac {x^{a_n}}{a_n!}) (1+x+2!x2++a1!xa1)(1+x+2!x2++a2!xa2)(1+x+2!x2++an!xan) 对这个式子求 x m m ! \frac {x^m}{m!} m!xm 的系数

    #include <bits/stdc++.h>
    using namespace std;
    int n,m;
    int a[110],b[110];
    double fac[110];
    double C1[110],C2[110];
    void init()
    {
        fac[0]=fac[1]=1;
        for(int i=2;i<=100;++i)
            fac[i]=fac[i-1]*i;
    }
    double solve()
    {
        for(int i=0;i<=m;++i) C1[i]=C2[i]=0;
        for(int i=0;i<=a[1];++i) C1[i]=1.0/fac[i];
    
        for(int i=2;i<=n;++i)
        {
            for(int j=0;j<=m;++j)
                for(int k=0;k<=a[i];++k)
                    C2[j+k]+=C1[j]*1.0/fac[k];
            for(int j=0;j<=m;++j)
                C1[j]=C2[j],C2[j]=0;
        }
        return C1[m]*fac[m];
    }
    int main()
    {
        init();
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=1;i<=n;++i)
                scanf("%d",&a[i]);
            printf("%.0lf\n",solve());
        }
        return 0;
    }
    

    HDU - 1028 Ignatius and the Princess III (普通生成函数)

    链接:http://acm.hdu.edu.cn/showproblem.php?pid=1028

    题意:将整数 n n n 拆分成正整数相加的形式,问有几种组合

    思路:每一个小于 n n n 的正整数都有可能组成。共有 n n n个因子,可以得到生成函数
    g ( x ) = ( 1 + x + x 2 + …   ) ( 1 + x 2 + x 4 + …   ) ( 1 + x 3 + x 6 + …   ) … g(x)=(1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^3+x^6+\dots)\dots g(x)=(1+x+x2+)(1+x2+x4+)(1+x3+x6+)

    x n x^n xn的系数就是所求的组合方式

    #include <bits/stdc++.h>
    using namespace std;
    int n,c1[130],c2[130];
    int solve(int m)
    {
        for(int i=0; i<=m; ++i) c1[i]=c2[i]=0;
        for(int i=0; i<=m; ++i) c1[i]=1;
        for(int i=2; i<=m; ++i)
        {
            for(int j=0; j<=m; ++j)
                for(int k=0; k<=m&&j+k<=m; k+=i)
                    c2[j+k]+=c1[j];
            for(int j=0; j<=m; ++j)
                c1[j]=c2[j],c2[j]=0;
        }
        return c1[m];
    }
    int main()
    {
        while(~scanf("%d",&n))
            printf("%d\n",solve(n));
        return 0;
    }
    

    HDU - 1085 Holding Bin-Laden Captive! (普通生成函数)

    链接:http://acm.hdu.edu.cn/showproblem.php?pid=1085

    题意:由面值为1、2、5的硬币不能组成的最小面值是多少。

    思路:可以得到生成函数
    g ( x ) = ( 1 + x + x 2 + …   ) ( 1 + x 2 + x 4 + …   ) ( 1 + x 5 + x 10 ) g(x)=(1+x+x^2+\dots)(1+x^2+x^4+\dots)(1+x^5+x^{10}) g(x)=(1+x+x2+)(1+x2+x4+)(1+x5+x10)
    从小到大遍历系数,为 0 的那一项就是不能组成的

    #include <bits/stdc++.h>
    using namespace std;
    int n,a[4],b[4],c1[8005],c2[8005];
    void solve(int m)
    {
        for(int i=0; i<=m; ++i) c1[i]=c2[i]=0;
        for(int i=0; i<=a[1]; ++i) c1[i]=1;
        for(int i=2; i<=3; ++i)
        {
            for(int j=0; j<=m; ++j)
                for(int k=0; k<=a[i]*b[i]&&j+k<=m; k+=b[i])
                    c2[j+k]+=c1[j];
            for(int j=0; j<=m; ++j)
                c1[j]=c2[j],c2[j]=0;
        }
    }
    int main()
    {
        while(scanf("%d%d%d",&a[1],&a[2],&a[3])&&(a[1]||a[2]||a[3]))
        {
            b[2]=2,b[3]=5;
            int m=a[1]*1+a[2]*2+a[3]*5;
            solve(m);
            int x=1;
            while(x<=m&&c1[x]) x++;
            printf("%d\n",x);
        }
        return 0;
    }
    

    HDU - 2189 悼念512汶川大地震遇难同胞——来生一起走 (普通生成函数)

    链接:http://acm.hdu.edu.cn/showproblem.php?pid=2189

    题意:把n个人分成几个小组。每个小组的人数必须是素数

    思路:用素数组成n,但是不知道用具体多少个素数。每一个小于等于 n 的素数都是一个因子。
    可以得到生成函数:
    g ( x ) = ( 1 + x 2 + x 4 + x 6 + …   ) ( 1 + x 3 + x 6 + …   ) ( 1 + x 5 + x 10 + …   ) g(x)=(1+x^2+x^4+x^6+\dots)(1+x^3+x^{6}+\dots)(1+x^5+x^{10}+\dots) g(x)=(1+x2+x4+x6+)(1+x3+x6+)(1+x5+x10+)
    x n x^n xn的系数就是这个组合数的答案

    BZOJ3028: 食物(普通生成函数 + 推导 + 欧拉降幂)

    Description
    明明这次又要出去旅游了,和上次不同的是,他这次要去宇宙探险!
    我们暂且不讨论他有多么NC,他又幻想了他应该带一些什么东西。理所当然的,你当然要帮他计算携带N件物品的方案数。
    他这次又准备带一些受欢迎的食物,如:蜜桃多啦,鸡块啦,承德汉堡等等
    当然,他又有一些稀奇古怪的限制:
    每种食物的限制如下:
    (1)承德汉堡:偶数个
    (2)可乐:0个或1个
    (3)鸡腿:0个,1个或2个
    (4)蜜桃多:奇数个
    (5)鸡块:4的倍数个
    (6)包子:0个,1个,2个或3个
    (7)土豆片炒肉:不超过一个。
    (8)面包:3的倍数个

    注意,这里我们懒得考虑明明对于带的食物该怎么搭配着吃,也认为每种食物都是以‘个’为单位(反正是幻想嘛),只要总数加起来是N就算一种方案。因此,对于给出的N,你需要计算出方案数,并对10007取模

    思路:很明显示生成函数的题,并且考虑的是组合数
    可以得到生成函数:
    g ( x ) = ( 1 + x 2 + …   ) ( 1 + x ) ( 1 + x + x 2 ) ( x + x 3 + …   ) ( 1 + x 4 + x 8 + …   ) ( 1 + x + x 2 + x 3 ) ( 1 + x ) ( 1 + x 3 + x 6 + …   ) g(x)=(1+x^2+\dots )(1+x)(1+x+x^2)(x+x^3+\dots)(1+x^4+x^8+\dots)(1+x+x^2+x^3)(1+x)(1+x^3+x^6+\dots) g(x)=(1+x2+)(1+x)(1+x+x2)(x+x3+)(1+x4+x8+)(1+x+x2+x3)(1+x)(1+x3+x6+)

    g ( x ) = 1 1 − x 2 ( 1 + x ) 1 − x 3 1 − x x 1 1 − x 2 1 1 − x 4 ( 1 − x 4 1 − x ) ( 1 + x ) 1 1 − x 3 g(x)=\frac 1{1-x^2}(1+x)\frac {1-x^3}{1-x}x\frac 1{1-x^2}{\frac {1}{1-x^4}}(\frac {1-x^4}{1-x})(1+x)\frac 1{1-x^3} g(x)=1x21(1+x)1x1x3x1x211x41(1x1x4)(1+x)1x31

    g ( x ) = x ( 1 − x ) 4 = ∑ n = 0 ∞ C n + 4 − 1 3 x n + 1 = ∑ n = 0 ∞ C n + 2 3 x n g(x)=\frac x{(1-x)^4}=\sum_{n=0}^{\infty}C_{n+4-1}^3x^{n+1}=\sum_{n=0}^{\infty}C_{n+2}^3x^n g(x)=(1x)4x=n=0Cn+413xn+1=n=0Cn+23xn
    因此,答案就是 a n = C n + 2 3 a_n=C_{n+2}^3 an=Cn+23
    在这里插入图片描述

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int Maxn=510;
    const int mod=10007;
    char s[Maxn];
    
    ll QuickPower(ll base,ll n)
    {
    	ll ret=1;
    	while(n)
    	{
    		if(n&1)
    			ret=(ret*base)%mod;
    		n>>=1;
    		base=(base*base)%mod;
    	} 
    	return ret;
    }
    int main()
    {
    	scanf("%s",s+1);
    	int n=0,len=strlen(s+1);
    	for(int i=1;i<=len;i++)
    		n=(n*10%mod+s[i]-'0')%mod;
    	ll ans=n*(n+1)%mod*(n+2)%mod*QuickPower(6,mod-2)%mod;
    	printf("%lld\n",ans);
    }
    

    2019 ICPC上海网络赛 E. Counting Sequences II (指数生成函数 + 推导)

    链接:https://nanti.jisuanke.com/t/41413

    题意:给定n个位置,对于每一个数 a i a_i ai,都满足 1 ≤ a i ≤ m 1\le a_i \le m 1aim,并且如果 a i a_i ai是偶数的话, a i a_i ai出现的次数是偶数次,求排列的个数

    思路:求的是排列,所以是指数型生成函数。在[1,m]的范围内,相当于有m个因子,每个因子分别代表对 1 、 2 、 3 、 4 、 … 、 m 1、2、3、4、\dots、m 1234m各自的限制。其中偶数有 f l o o r ( m 2 ) floor(\frac m2) floor(2m)个,奇数有 m − f l o o r ( m 2 ) m-floor(\frac m2) mfloor(2m),设 t = f l o o r ( m 2 ) t=floor(\frac m2) t=floor(2m),可以得到指数型生成函数
    g ( x ) = ( 1 + x + x 2 2 ! + x 3 3 ! + …   ) m − t ( 1 + x 2 2 ! + x 4 4 ! + …   ) t g(x)=(1+x+\frac {x^2}{2!}+\frac {x^3}{3!}+\dots)^{m-t}(1+\frac {x^2}{2!}+\frac {x^4}{4!}+\dots)^{t} g(x)=(1+x+2!x2+3!x3+)mt(1+2!x2+4!x4+)t
    化简可得:
    g ( x ) = e x ( m − t ) ( e x + e − x 2 ) t = e x ( m − t ) ∑ i = 0 t C t i e x ( t − i ) e − x i 2 t g(x)=e^{x(m-t)}(\frac {e^x+e^{-x}}2)^t=\frac{e^{x(m-t)}\sum_{i=0}^tC_t^ie^{x(t-i)}e^{-xi}}{2^t} g(x)=ex(mt)(2ex+ex)t=2tex(mt)i=0tCtiex(ti)exi
    g ( x ) = ∑ i = 0 t C t i e ( m − 2 i ) x 2 t = ∑ n = 0 ∑ i = 0 t C t i ( m − 2 i ) n 2 t x n n ! g(x)=\frac {\sum_{i=0}^tC_t^ie^{(m-2i)x}}{2^t}=\sum_{n=0}\frac{\sum_{i=0}^tC_t^i{(m-2i)^n}}{2^t}\frac {x^n}{n!} g(x)=2ti=0tCtie(m2i)x=n=02ti=0tCti(m2i)nn!xn
    因此可以得到 a n = ∑ i = 0 t C t i ( m − 2 i ) n 2 t a_n=\frac{\sum_{i=0}^tC_t^i{(m-2i)^n}}{2^t} an=2ti=0tCti(m2i)n a n a_n an就是答案

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int mod=1e9+7;
    int t,m;
    ll n;
    int qpow(int b,int n,int mod)
    {
        int res=1;
        while(n)
        {
            if(n&1) res=1ll*res*b%mod;
            n>>=1;
            b=1ll*b*b%mod;
        }
        return res;
    }
    const int N=2e5;
    int fac[N+10],finv[N+10];
    void init()
    {
        fac[0]=fac[1]=1;
        for(int i=2; i<=N; ++i) fac[i]=1ll*fac[i-1]*i%mod;
        finv[N]=qpow(fac[N],mod-2,mod);
        for(int i=N-1; i>=0; --i)
            finv[i]=1ll*finv[i+1]*(i+1)%mod;
    }
    
    int C(int n,int m)
    {
        return 1ll*fac[n]*finv[m]%mod*finv[n-m]%mod;
    }
    int main()
    {
        init();
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld%d",&n,&m);
            n%=mod-1;
            int ans=0;
            int t=m/2;
            for(int i=0; i<=t; ++i)
                ans=(ans+1ll*C(t,i)*qpow(m-2*i,n,mod)%mod)%mod;
            ll res=qpow(2,t,mod);
            ans=1ll*ans*qpow(res,mod-2,mod)%mod;
            printf("%d\n",ans);
        }
        return 0;
    }
    
    展开全文
  • 生成函数(母函数) 什么是生成函数:wiki上的介绍 在数学中,某个序列(an)n∈N\large {\displaystyle (a_{n})_{n\in \mathbb {N} }}(an​)n∈N​ 的母函数(又称生成函数,英语:Generating function)是一种形式幂...

    生成函数(母函数)

    什么是生成函数:wiki上的介绍

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

    母函数可分为很多种,包括普通母函数指数母函数L级数贝尔级数狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题,因此选用何种母函数视乎序列本身的特性和问题的类型。

    母函数,又称生成函数,是ACM竞赛中经常使用的一种解题算法,常用来解决组合方面的题目。

    生成函数的定义:g(x)=a0+a1x+a2x2+a3x3+...\large g(x)=a_0+a_1x+a_2x^2+a_3x^3+...g(x)=a0+a1x+a2x2+a3x3+...g(x)\large g(x)g(x)是序列a0,a1,a2,...a_0,a_1,a_2,...a0,a1,a2,...的生成函数。

    小题


    一、

    有1克、2克、3克、4克的砝码各一枚,能称出哪几种重量?每种重量各有几种可能方案?
    

    我们用母函数来解决这个问题

    1个1克砝码可以看成1+x^1,1表示不取,x^1表示取一个,以下同理
    1个2克砝码可以看成1+x^2
    1个3克砝码可以看成1+x^3
    1个4克砝码可以看成1+x^4
    

    那么生成函数就是

    g(x)=(1+x1)(1+x2)(1+x3)(1+x4)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10\large g(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}g(x)=(1+x1)(1+x2)(1+x3)(1+x4)=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10

    这个函数中可以看出重量为3克的方案有两种,重量为7的方案有两种,重量为10的有1种。

    不难发现指数表示重量,系数表示方案数。


    二、

    求用1分、2分、3分的邮票贴出不同数值的方案数:
    大家把这种情况和第一种比较有何区别?第一种每种是一个,而这里每种是无限的。
    

    那么生成函数就是g(x)=(1+x+x2+x3+...)(1+x2+x4+x6+...)(1+x3+x6+x9+...)\large g(x)=(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+x^9+...)g(x)=(1+x+x2+x3+...)(1+x2+x4+x6+...)(1+x3+x6+x9+...)

    以展开后的x^4为例,其系数为4,即4拆分成1、2、3之和的拆分方案数为4;

    即 :4=1+1+1+1=1+1+2=1+3=2+2


    三、

    设有n个标志为1,2,…,n的网袋,第i个(i=1,2,…n)网袋里放有ni个球。不同网袋里的球是不同的,而同一网袋里的球则是没有差别的,认为是相同的。询问从中取r个球的方案数。
    

    设生成函数g(x)=(1+x1+x2+...+xn1)(1+x1+x2+...+xn2)...\large g(x)=(1+x^1+x^2+...+x^{n1})(1+x^1+x^2+...+x^{n2})...g(x)=(1+x1+x2+...+xn1)(1+x1+x2+...+xn2)...

    最后指数为r的那一项的系数就是方案数。


    总结一下,生成函数大多用来解决有限或无限物体的组合方案。

    给出通用模板,其实就是暴力拆这个函数罢了。

    #include<cstdio>
    using namespace std;
    int N,g[2][125];
    int main(){
    	while(~scanf("%d",&N)){
    		for(int i=0;i<=N;++i) g[1][i]=1,g[0][i]=0;
    		for(int i=2;i<=N;++i){
    			for(int j=0;j<=N;++j)
    			for(int k=0;k<=N-j;k+=i) g[i&1][j+k]+=g[1-(i&1)][j];
    			for(int j=0;j<=N;++j) g[1-(i&1)][j]=0;
    		}
    		printf("%d\n",g[N&1][N]);
    	}
    	return 0;
    }
    

    以上是一些基础,接下来给一道难题(反正我一点也不会,逃):BZOJ4001

    不会也没有关系,我们慢慢来。


    特殊情况

    a={1,1,1,1,...}a=\{1,1,1,1,...\}a={1,1,1,1,...}f(x)=1+x+x2+x3+...=11−x\large f(x)=1+x+x^2+x^3+...=\frac{1}{1-x}f(x)=1+x+x2+x3+...=1x1

    这又是为什么呢?

    我们发现f(x)\large f(x)f(x)是一个等比数列

    又因为x∈(−1,1)x∈(-1,1)x(1,1)

    所以当n→∞n \to \inftyn时,1−xn1−x\frac{1-x^n}{1-x}1x1xn中,xn→0x^n \to 0xn0,所以f(x)=1+x+x2+x3+...=11−x\large f(x)=1+x+x^2+x^3+...=\frac{1}{1-x}f(x)=1+x+x2+x3+...=1x1

    同理f‘(x)=1+2x+3x2+4x3+...=1(1−x)2=(11−x)2=f2(x)\large f`(x)=1+2x+3x^2+4x^3+...=\frac{1}{(1-x)^2}=(\frac{1}{1-x})^2=f^2(x)f(x)=1+2x+3x2+4x3+...=(1x)21=(1x1)2=f2(x)

    f‘‘(x)=1+3x+6x2+10x3+15x4...=1(1−x)3=f3(x)\large f``(x)=1+3x+6x^2+10x^3+15x^4...=\frac{1}{(1-x)^3}=f^3(x)f(x)=1+3x+6x2+10x3+15x4...=(1x)31=f3(x)

    推广1(1−x)k=∑i∞Ci+k−1k−1xi=fk(x)\large \frac{1}{(1-x)^k}=\sum_{i}^{\infty} C_{i+k-1}^{k-1}x^i=f^k(x)(1x)k1=iCi+k1k1xi=fk(x)

    用组合数学中的所谓“隔板法”求一下,第iii项的系数就是Ci+k−1k−1C_{i+k-1}^{k-1}Ci+k1k1


    斐波那契通项公式

    下面我们用生成函数求斐波那契数列的通项公式:

    首先f(x)=x+x2+2x3+3x4+5x5+...\large f(x)=x+x^2+2x^3+3x^4+5x^5+...f(x)=x+x2+2x3+3x4+5x5+...

    f(x)f(x)f(x)乘上个xxx,然后相减

    f(x)−x∗f(x)=(x+x2+2x3+3x4+...)−(x2+x3+2x4+3x5+...)=x+x3+x4+2x5+3x6=x+x2f(x)\large f(x)-x*f(x)=(x+x^2+2x^3+3x^4+...)-(x^2+x^3+2x^4+3x^5+...)=x+x^3+x^4+2x^5+3x^6=x+x^2f(x)f(x)xf(x)=(x+x2+2x3+3x4+...)(x2+x3+2x4+3x5+...)=x+x3+x4+2x5+3x6=x+x2f(x)

    f(x)f(x)f(x)f(x)=x1−x−x2f(x)=\frac{x}{1-x-x^2}f(x)=1xx2x

    然后如何还原成序列呢?

    先因式分解

    x1−x−x2=x(1−1−52x)(1−1+52x)\large \frac{x}{1-x-x^2}=\frac{x}{(1-\frac{1-\sqrt{5}}{2}x)(1-\frac{1+\sqrt{5}}{2}x)}1xx2x=(1215x)(121+5x)x

    用裂项法1n(n+k)=1k(1n−1n+k)\frac{1}{n(n+k)}=\frac{1}{k}(\frac{1}{n}-\frac{1}{n+k})n(n+k)1=k1(n1n+k1)

    x(1−1−52x)(1−1+52x)=1(1−1−52x)((1−1−52x+(−5x))x=1−5(11−1−52x−11−1+52x)=−1511−1−52x+1511−1+52x\large \frac{x}{(1-\frac{1-\sqrt{5}}{2}x)(1-\frac{1+\sqrt{5}}{2}x)}\\ \large=\frac{1}{(1-\frac{1-\sqrt{5}}{2}x)((1-\frac{1-\sqrt{5}}{2}x+(-\sqrt{5}x))}x\\ \large=\frac{1}{-\sqrt{5}}(\frac{1}{1-\frac{1-\sqrt{5}}{2}x}-\frac{1}{1-\frac{1+\sqrt{5}}{2}x})\\ \large=-\frac{1}{\sqrt{5}}\frac{1}{1-\frac{1-\sqrt{5}}{2}x}+\frac{1}{\sqrt{5}}\frac{1}{1-\frac{1+\sqrt{5}}{2}x}(1215x)(121+5x)x=(1215x)((1215x+(5x))1x=51(1215x1121+5x1)=511215x1+51121+5x1

    把他分裂成等比数列的形式。

    an=−15(1−52)n+15(1+52)n\large a_n=-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n+\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^nan=51(215)n+51(21+5)n

    这就是斐波那契数列通项公式。


    终于写完了,接下来就是多刷例题训练了。

    HDU1028

    HDU1085

    洛谷P2000

    BZOJ3028

    转载于:https://www.cnblogs.com/XSamsara/p/10547940.html

    展开全文
  • 生成函数

    千次阅读 2019-04-01 21:59:18
    转载请注明 目录 转载请注明 1.前言 2.必要知识 2.1形式幂级数 2.1.1概念 ...3.生成函数 3.1普通型母函数 3.1.1定义 3.1.2常见普通型母函数 3.1.3定理一 3.1.4例子 3.2指数型母函数 ...

    转载请注明

    目录

    转载请注明

    1.前言

    2.必要知识

    2.1形式幂级数

    2.1.1概念

    2.1.2特点

    2.1.3运算

    2.1.4关于形式幂级数的(群的)逆元和单位元

    2.2齐次方程与非齐次方程

    2.2.1概念

    2.2.2举例

    3.生成函数

    3.1普通型母函数

    3.1.1定义

    3.1.2常见普通型母函数

    3.1.3定理一

    3.1.4例子

    3.2指数型母函数

    3.2.1定义

    3.2.2常见指数型母函数

    3.2.3定理二

    3.2.4例子

    4.由递推关系求通项公式的几个方法

    4.1递推关系的定义

    4.2求解方法

    4.2.1迭代法

    4.2.2母函数法

    4.2.3特征根法

    5.参考文献


    1.前言

    本文主要讨论两类生成函数(普通型母函数和指数型母函数),除此之外,还研究了通过数列递推式导出数列通项公式的方法。

     

    2.必要知识

     

    2.1形式幂级数

    2.1.1概念

    设一个数列(序列)  为  f(n),

    则 f(n)   的形式幂级数是 A(x) = \sum_{n=0}^{\infty} f(n) \cdot x^n  

     

    2.1.2特点

    形式幂级数有以下两个特点:

    2.1.2.1特点一

    形式幂级数不关心 x 的值

    2.1.2.2特点二

    形式幂级数不关心收敛和发散,即对 A(x) 的收敛和发散不做要求

     

    2.1.3运算

    形式幂级数的运算是在把  A(x)   在 n \rightarrow \infty  时看作收敛的情况的基础上进行的的。

    形式幂级数的运算主要有以下三种,在此之前,我们先使用一些初始设定:

    设  a(n),b(n)  是两个关于n 的数列(序列),

    a(n) 的形式幂级数是  A(x) = \sum_{n=0}^{\infty} a(n) \cdot x^n

    设 b(n)  的形式幂级数是  B(x) = \sum_{n=0}^{\infty} b(n) \cdot x^n

     

    2.1.3.1相等运算

    若  \forall x>0, \ a(n) = b(n)  , 那么  A(x) =B(x)

     

    2.1.3.2相加运算

    A(x)+B(x) = \sum_{n=0}^{\infty} (a(n)+b(n)) \cdot x^n

    除此之外,还满足交换律和结合律

     

    2.1.3.3相乘运算

    A(x) \cdot B(x) = \sum_{n=0}^{\infty}c(n)\cdot x^n

    其中,c(n)=\sum_{k=0}^{n}a_k \cdot b_{n-k}(对加法也满足分配律)

    c(n) 是序列  a(n)  和  b(n)  的柯西乘积

     

    2.1.4关于形式幂级数的(群的)逆元和单位元

     

    2.1.4.1单位元

    形式幂级数的单位元是1(数字)

     

    2.1.4.2逆元

    一、概念

    设 A(x) = \sum_{n=0}^{\infty}a(n)\cdot x^n

    若存在 B(x) = \sum_{n=0}^{\infty}b(n)\cdot x^n,满足A(x) \cdot B(x),

    则 B(x)  是 A(x)  关于 1 的逆元

    二、逆元的充要条件

    A(x)  有逆元的充要条件是 a(0) \neq 0

    三、逆元的唯一性

    若  A(x)  有逆元,则逆元唯一,即 B(x) 是唯一的

     

    2.2齐次方程与非齐次方程

    2.2.1概念

    设方程 a_1x_1^{k_1}+a_2x_2^{k_2}+...+a_nx_n^{k_n}=f(n)   (1)

    则 (1) 为齐次方程的充要条件是:

    条件一:k_1=k_2=...=k_n

    条件二:f(n)=0

    2.2.2举例

    对某个 n 元一次常系数方程:a_1x_1+a_2x_2+...+a_nx_n=f(n)     (*)

    一、齐次方程

    若 (*) 中 f(n)=0 ,那么 (*) 是齐次方程

    二、非齐次方程

    若 (*) 中 f(n) \neq 0, 那么 (*) 是非齐次方程

     

     

    3.生成函数

    生成函数也叫做母函数,它是一个数列(序列)的一种形式幂级数。其中,每一项的系数分别代表着组合方法数(针对这一项的次数)。母函数主要分为两类:普通型母函数和指数型母函数。

     

    3.1普通型母函数

    普通型母函数是针对组合问题而言的 

    3.1.1定义

    有两种类型的普通型母函数:

    一、单下标序列的母函数

    对序列 a(n) ,有普通型母函数 A(x)= \sum_{n=0}^{\infty} a(n) \cdot x^n 。

    二、双下标序列的母函数(可以引申至更多)

    对序列 a(n,m) ,有普通型母函数 A(x_1,x_2)= \sum_{n=0}^{\infty} a(n,m) \cdot x_1^{n} \cdot x_2^{m}

    3.1.2常见普通型母函数

    3.1.2.1 对序列 a(n,m) = \binom{n}{m},m \in [0,n]( n 固定),

    有普通型母函数 A(x)= \sum_{k=0}^{n} \binom{n}{k} \cdot x^k = (1+x)^n

     

    3.1.2.2 对序列 F(n) = \frac{1}{\sqrt 5} \cdot ((\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n),   即斐波那契数列,

    有普通型母函数  A(x) = \sum_{n=0}^{\infty}F(n) \cdot x^n = \frac{1}{1-x-x^2}

     

    3.1.2.3 对序列 a(n)=1 

    有普通型母函数  A(x)= \sum_{n=0}^{\infty} a(n) \cdot x^n = \frac{1}{1-x}

     

    3.1.2.4 对序列 a(n)=n,

    有普通型母函数  A(x)= \sum_{n=0}^{\infty} a(n) \cdot x^n = \frac{1}{(1-x)^2}

     

    3.1.2.5 对序列  a(n,m)=\begin{cases} 1 & \text{ if } n=1 \\ \frac{m \cdot (m+1)\cdot (m+2)\cdot ... \cdot (n-2)}{(n-1)!} & \text{ if } n>1 \end{cases}  (m 固定)

    有普通型母函数 A(x) = \sum_{n=0}^{\infty} a(n,m) \cdot x^n = \frac{1}{(1-x)^m}

    3.1.3定理一

    设从 n 元集合 S ={a_1,a_2...a_n} 中取 k 个元素的组合叫做 b_k, 限定元素 a_i 出现的次数是 M_i (1\leqslant i\leqslant n)

    那么 b_k 的组合数序列的普通型母函数是     \prod_{i=1}^{n}(\sum_{m \in M_i} x_m)

    3.1.4例子

    有重量为1,3,5(克)的砝码个两个,问:

    (1)可以称出多少种不同重量的物品?

    (2)若要称出重量为7克的物品,所使用的法码有多少种本质不同的情况?

    解:

    第一问:

    根据定理一,设(普通型)生成函数 G(x)=(1+x+x^2)(1+x^3+x^6)(1+x^5+x^{10})      (2)

    其中,1 表示不用重量为 1 克的砝码, x 表示使用 1 个重量为 1 克的砝码,x^2 表示使用两个重量为 1 克的砝码....以此类推

    (2)  展开为  G(x)=1+x+x^2+x^3+x^4+2x^5+2x^6+2x^7+...+x^{18} ,

    因此,可以称出 19 种不同重量的物品

    第二问:

    由第一问的展开式可知答案为 2

     

    3.2指数型母函数

    指数型母函数是针对多重元素的排列问题而言的

    3.2.1定义

    对序列 a(n),有指数型母函数 A(x)=\sum_{n=0}^{\infty} a(n) \cdot \frac{x^n}{n!}

    对于多下标同理

    3.2.2常见指数型母函数

    3.2.2.1 对序列 a(n)=1

    有指数型母函数 A(x)=\sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x

     

    3.2.2.2 对序列 a(n)=p^n

    有指数型母函数 A(x) = \sum_{n=0}^{\infty}p^n\cdot\frac{x^n}{n!}=e^{px}


     3.2.2.3 对序列  a(n)=\begin{cases} 1 & \text{ if } x=0,2,4.. \\ 0 & \text{ if } x=1,3,5.. \end{cases}

    有指数型母函数 A(x)=\sum_{n=0}^{\infty}\frac{x^n}{n!}[n\%2=0]=1+\frac{x^2}{2!}+\frac{x^4}{4!}+...=\frac{e^x+e^{-x}}{2}

     

    3.2.2.4 对序列  a(n)=\begin{cases} 1 & \text{ if } x=1,3,5.. \\ 0 & \text{ if } x=0,2,4.. \end{cases}

    有指数型母函数 A(x)=\sum_{n=0}^{\infty}\frac{x^n}{n!}[n\%2=1]=1+\frac{x^3}{3!}+\frac{x^5}{5!}+...=\frac{e^x-e^{-x}}{2}

    3.2.3定理二

    从多重集合 M=\{ \infty \cdot a_1,\infty \cdot a_2,...\infty \cdot a_n\} 中选择 k 个元素的排列中,若限定元素 a_i 的出现次数集合为 M_i (1\leqslant i\leqslant n), 在该组合数的指数型母函数是     \prod_{i=1}^{n}(\sum_{m \in M_i}\frac{x^m}{m!}) 

    3.2.4例子

    由  1,2,3,4  这四个数字能构成多少个五位数?并且要求五位数中 1 出现两次或三次, 2 最多出现一次,4 出现偶数次。

    解:

    1 出现两次或三次,对应的母函数是: \frac{x^2}{2!} + \frac{x^3}{3!}

    2 最多出现一次,对应的母函数是:1+\frac{x}{1!}

    3 出现的次数不做要求,对应的母函数是:1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}+...=e^x

    4 出现偶数次,对应的母函数是:1+\frac{x^2}{2!}+\frac{x^4}{4!}+...=\frac{e^x+e^{-x}}{2}

    设五位数的组合数的指数型母函数是 G(x)

    则 G(x) = (\frac{x^2}{2!}+\frac{x^3}{3!})(1+\frac{x}{1!})(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^5}{5!}+...)(1+\frac{x^2}{2!}+\frac{x^4}{4!}+..)

    \Rightarrow \frac{1}{2}(\frac{1}{6}x^2(3+4x+x^2))\cdot e^x\cdot (e^x+e^{-x})

    \Rightarrow \frac{1}{12} \cdot 5! \cdot (3 \cdot \frac{2^3}{3!}+4\cdot \frac{2^2}{2!}+1\cdot \frac{2^1}{1!})

    \Rightarrow 140

     

    4.由递推关系求通项公式的几个方法

    4.1递推关系的定义

    递推关系由递推方程和初始条件构成

    其中,递推方程是形如 a(n)=a(n-1)+a(n-2) ,即由数列的相邻项或者间隔项构成的方程

    初始条件是形如:a_0=0,a_1=1..

    4.2求解方法

    4.2.1迭代法

    \begin{cases} a_n=2a_{n-1}+1 \\ a_1=1 \end{cases},求 a_n ?

    a_n=2_{n-1}+1=2(a_{n-2}+1)+1=2(...)+1=2^n-1

     

    4.2.2母函数法

    \begin{cases} a_n=2a_{n-1}+1 \\ a_1=1 \end{cases},求 a_n ?

    \because a_1=2(a_0+1)

    \therefore a_0=0

    设 f(x)=\sum_{n=0}^{\infty}a_nx^n

    f(x)=\sum_{n=1}^{\infty}(2a_{n-1}+1)x^n=2\sum_{n=1}^{\infty}a_{n-1}x^n+\sum_{n=1}^{\infty}x^n

    \Rightarrow 2x\sum_{n=0}^{\infty}a_nx^n+\sum_{n=1}^{\infty}x^n

    \Rightarrow 2xf(x)+\frac{x}{1-x} 

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

    \Rightarrow f(x)=\sum_{n=0}^{\infty}(2^n-1)x^n

    \therefore a(n)=2^n-1

     

    4.2.3特征根法

    一、介绍一些概念

    概念一:若 \{ a_n \} 满足 a_n+b_1a_{n-1}+b_2a_{n-2}+...+b_ka_{n-k}=f(n)  (*)

    \{b_n \} 为常数,且 b_k \neq 0f(n) 为已知函数

    则 \{ a_n \} 为 k 阶常系数线性递推关系

     

    概念二:若 f(n)=0 , 则 \{ a_n \} 为 k 阶常系数齐次递推关系

     

    概念三(*) 的特征方程是:x^k+b1x^{k-1}+b2x^{k-2}+...+b_{k-1}x+b_k=0

     

    二、分具体情况的不同解法

    1.齐次常系数线性递推关系解法

    情况一:

    (*) 有 k 个相异实根,设这 k 个实根的集合为 solution=\{x_1,x_2..x_k \}

    则递推关系的通解(通项公式)为:a_n=c_1x_1^n+c_2x_2^n+...+c_kx_k^n

    其中,\{c_n \} 为常数集

    若给出了 k 个初始条件,则 \{c_n \} 唯一,进而得到 a_n 的唯一表达式

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    例子:

    \begin{cases} F_n=F_{n-1}+F_{n-2} & \\ F_1=1,F_0=1 & \end{cases}

    解:

    特征方程是 x^2 -x-1=0,得到 两个相异实根:x_1=\frac{1+\sqrt5}{2},x_2=\frac{1-\sqrt5}{2}

    \therefore F_n=c1(\frac{1+\sqrt5}{2})^n+c2(\frac{1-\sqrt5}{2})^n

    将初始条件带入,得到:c_1=\frac{1}{\sqrt 5},c_2=-\frac{1}{\sqrt 5}

    \therefore F_n=\frac{1}{\sqrt 5}(\frac{1+\sqrt 5}{2})^n-\frac{1}{\sqrt 5}(\frac{1-\sqrt 5}{2})^n

     

    情况二:

    (*) 出现一对共轭复根:x_1=a+bi,x_2=a-bi

    则通解为(通项公式)为:a_n=c1 \cdot \rho^n \cdot cos\ n\theta+c_2 \cdot \rho ^n\cdot sin \ n \theta+c_3x_3^n+..+c_kx_k^n

    其中,\rho = \sqrt{ a^2+b^2}\theta = arctan \ \frac{b}{a}   (复数的模长和角),\{c_n \} 为常数集

    若给出一组 k 个初始解,那么 \{c_n \} 唯一,进而得到 a_n 的唯一表达式

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    例子:

    d_n=\begin{bmatrix} 1 & 1 & 0 &0 .& .& . &. & . & 0 & \\ 1& 1& 1& & & & & & 0& \\ 0& 1 & 1& 1& & & & & 0& \\ .& & 1& 1 & 1 & & & & .& \\ .& & & & & .& & & . & \\ .& & & & & & 1 & 1 & 1 & \\ 0& & . & .& & & & 1 & 1 & \end{bmatrix}

    d_n 是一个 n \times n 的矩阵,求 d_n 

    解:

    将 d_n 按照第一行展开,显然可以得到 d_n=d_{n-1}-d_{n-2},并且 d_1=1,d_2=0

    所以其特征方程为:x^2-x+1=0

    解出两个共轭复根:x_1=\frac{1}{2}+\frac{\sqrt 3}{2} i,x_2=\frac{1}{2}-\frac{\sqrt 3}{2} i

    算出 \rho = \sqrt{a^2+b^2}=1,\theta=arctan \ \frac{b}{a}=\frac{\pi}{3}

    \therefore 其通解为 d_n=c_1 \cdot cos \ \frac{n\pi}{3} +c_2\cdot sin \ \frac{n \pi}{3}

    \because d_1=1,d_2=0

    \therefore c_1=1,c_2=\frac{1}{\sqrt 3}

    \therefore d_n=cos \ \frac{n\pi}{3}+\frac{sin \ n\pi}{3\sqrt3}

     

    情况三:

    (*) 出现 k 重根,在这里我们先设 a_1 是重根(可以扩展到多个重根)

    则有通解(通项公式)为:a_n=(c_1+c_2n+c_3n^2...+c_kn^{k-1})\cdot a_1^n

    \{c_n \} 为常数集

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    例子:

    d_n=\begin{bmatrix} 2 & 1 & 0 &0 .& .& . &. & . & 0 & \\ 1& 2& 1& & & & & & 0& \\ 0& 1 & 2& 1& & & & & 0& \\ .& & 1& 2 & 1 & & & & .& \\ .& & & & & .& & & . & \\ .& & & & & & 1 & 2& 1 & \\ 0& & . & .& & & & 1 & 1 & \end{bmatrix}

    d_n 是一个 n \times n 的矩阵,求 d_n 

    解:

    将 d_n 按照第一行展开,显然可以得到 d_n=2d_{n-1}-d_{n-2},并且 d_1=2,d_2=3

    所以其特征方程为:x^2-2x+1=0

    解出 2 个重根:x_1=x_2=1

    \therefore 通解(通项公式)为:d_n=(c_1+c_2n)\cdot 1^n=c_1+c_2n

    \because d_1=2,d_2=3

    \therefore c_1=1,c_2=1

    \therefore d_n=1+n

     

    2.非齐次常系数线性递推关系解法

    (*) 的通项公式如下:a_n=\bar{a_n}+a_n(*),

    其中,a_n(*) 是将递推关系看作齐次线性递推关系得到的通解,而 \bar{a_n} 是根据以下情况得到的特解

    情况一:

    (*) 右边 f(n) 是 n 的 t 次多项式,并且 1 是 (*) 的特征方程的 m 重根

    那么,有特解为:\bar{a_n}=(c_1n^t+c_2n^{t-1}+...+c_tn+c_{t+1})\cdot n^m 

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    例子:

    给定 k ,求 \sum_{k=1}^{n}k^3

    解:

    设 a_n = \sum_{k=1}^{n}k^3

    那么有 \begin{cases} a_n-a_{n-1}=n^3 & \\ a_1=1 & \end{cases}

    第一步:将递推关系看成是齐次求解通项公式

    得到齐次递推关系:a_n-a_{n-1}=0

    那么有特征方程:x-1=0

    得到解:x=1

    \therefore 其通解(通项公式)为:a_n(*)=c_1 \cdot 1^n=c_1

    第二步:求出特解

    因为 1 是递推关系的 1 重根,

    因此有:\bar{a_n}=(c_1n^3+c_2n^2+c_3n+c_4) \cdot n^1

    代入非齐次递推关系式得到特解: \bar{a_n}=\frac{1}{4}n^4+\frac{1}{2}n^3+\frac{1}{4}n^2

    \therefore a_n =\frac{1}{4}n^4+\frac{1}{2}n^3+\frac{1}{4}n^2+c_1

     由初始值得到:c_1=0

    \therefore a_n =\frac{1}{4}n^4+\frac{1}{2}n^3+\frac{1}{4}n^2=\frac{1}{4}n^2(n+1)^2

     

    情况二:

    (*) 右边 f(n) 是 n 的 t 次多项式,并且 1 不是 (*) 的特征方程的根

    那么,有特解为:\bar{a_n}=c_1n^t+c_2n^{t-1}+...+c_tn+c_{t+1}

     

    情况三:

    (*) 右边 f(n) 是 c \cdot \beta^n 的形式(c,\beta是常数)

    \beta 不是 (*) 的特征方程的根,那么由特解:\bar{a_n}=k \cdot \beta^n(k 为常数)

     

    情况四:

    (*) 右边 f(n) 是 c \cdot \beta^n 的形式(c,\beta是常数)

    \beta 是 (*) 的特征方程的 m 根,那么由特解:\bar{a_n}=k \cdot n^m \cdot \beta^n(k 为常数)

    -------------------------------------------------------------------------------------------------------------------------------------------------------------------------

    例子:

    \begin{cases} a_n=5a_{n-1}-6a_{n-2}+3\cdot2^n & \\ a_0=0,a_1=1 & \end{cases}

    求 a_n

    解:

    第一步:将递推关系看成是齐次求解通项公式

    得到齐次递推关系:a_n-5a_{n-1}+6a_{n-2}=0

    那么有特征方程:x^2-5x+6=0

    得到解:x_1=2,x_2=3

    因此,得到通解为:a_n(*)=c_1\cdot2^n+c_2\cdot3^n

    \because 2 是非齐次递推关系的 1 重根

    \therefore 由特解:\bar{a_n}=k \cdot n\cdot 2^n

    代入非齐次递推关系式得到特解:\bar{a_n}=-6n2^n

    \therefore a_n=c_1 \cdot 2^n+c_2 \cdot 3^n-6n2^n

    由初始值,得到:c_1=-13,c_2=13

    \therefore a_n=-13 \cdot 2^n +13 \cdot 3^n -6n2^n

     

    5.参考文献

    1.https://wenku.baidu.com/view/f4799f98370cba1aa8114431b90d6c85ec3a8807?pcf=2

    2.中文wiki母函数

    3.信息学奥赛-数学一本通

     

    展开全文
  • 生成函数(母函数)、递归方程求解 生成函数(母函数) 我认为生成函数就是把问题转换成处理二项式问题的方法 经典问题 用1元、5元、10元三种纸币能拼出多少种100元的方案? 这其实是一个组合问题,用三...
  • 一些常见数列的生成函数推导

    千次阅读 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,.....
  • 另外,对于生成器的特殊语法支持使得编写一个生成器比自定义一个常规的迭代器要简单不少,所以生成器也是最用到的特性之一。 从Python 2.5开始,[PEP 342:通过增强生成器实现协同程序]的实现为生成器加入了更多的...
  • 另外,对于生成器的特殊语法支持使得编写一个生成器比自定义一个常规的迭代器要简单不少,所以生成器也是最用到的特性之一。 从Python 2.5开始,[PEP 342:通过增强生成器实现协同程序]的实现为生成
  • MATLAB学习笔记(一)函数与跳变函数的绘制 1.函数 比如,我们要绘 f(x)=5,x∈(0,10)f(x) = 5,x\in\left(0,10\right)f(x)=5,x∈(0,10) 的函数图,我们知道他是一条平行于x轴的直线,一般人想的代码可能是:...
  • 函数产生三角波,用于电源电子设备作为 PWM 单元的载波信号
  • 简要:对于一个空类,C++编译器默认生成四个成员函数:默认构造函数、析构函数、拷贝(复制)构造函数、赋值函数 目录 一、默认构造函数 二、析构函数 三、拷贝(复制)构造函数 四、赋值函数 一、默认构造...
  • 类默认生成的成员函数

    千次阅读 2016-07-19 17:18:12
    类默认生成的六个成员函数 一、构造函数  我们知道,类的数据成员是不能在声明类的时候初始化的,因为类并不是一个实体,而是一种抽象的数据类型,并不占据存储空间。为了解决这个问题,C++提供了构造函数来...
  • Linux下随机数生成函数与常见方法

    万次阅读 2018-01-30 22:39:15
    rand函数:  头文件  #include  定义函数  int rand(void)  函数说明  rand()会返回一随机数值,范围在0至RAND_MAX 间。在调用此函数产生随机数前,必须先利用srand()设好随机数种子,如果未设随机数...
  • MATLAB图像生成函数Plot()总结

    千次阅读 2015-05-05 21:59:36
    生成的图形是以序号为横坐标、数组y的数值为纵坐标画出的折线。   (2)>> x=linspace(0,2*pi,30); % 生成一组线性等距的数值 >> y=sin(x); >> plot(x,y) 生成的图形是上30个点连成的光滑的正弦曲线。 二、...
  • C++类默认生成的四个函数

    千次阅读 2014-12-04 11:19:47
    序:对于一个空类,编译器默认生成四个成员函数:默认构造函数、析构函数、拷贝构造函数、赋值函数 一,默认构造函数  默认构造函数(defaultconstructor)就是在没有显式提供初始化式时调用的构造函数。它由不带...
  • 使用模型生成代码的方式常用在应用层软件开发中,需要调用到底层的函数或者其它接口函数获取模型的相关变量值,因此模型需要调用外部函数接口。 10.1 调用外部C代码的方法 (1)要调用外部C代码,首先得要在...
  • MATLAB随机数生成函数有两种形式,一种是形如***rnd,比如(unifrnd,binornd,exprnd)等,一种就是用一个统一的函数random(‘name’,...),利用不同的 name生成不同的分布的随机数 在matlab中,有两个工具箱...
  • Fix MSVC2017 compilation with enabled relaxed constexpr on 32-bit target qt 的bug ,按照下列地址修改源码 ...
  • 首先给出MCMC方法状态数的选取范围,其次在该范围内以生成序列与原始序列的自相关函数的误差平方和最小为原则确定优选状态数,然后利用各状态对应功率范围内的累积分布函数抽样生成随机风电功率,提高优选状态数下...
  • 软件主要提供一些 用DELPHI函数功能的查询,软件可以帮你快速生成各类对话框和注解代码的DELPHI源代码,你可以直接复制使用,可以查询ASC字母代码,当你忘记了你自已的ACCEESS数据库密码时软件还可以帮你找回密码
  • 友元函数 一个常规的成员函数声明描述了三件在逻辑上相互不同的事情 1. 该函数能访问类声明的私用部分 2. 该函数位于类的作用域之中 3. 该函数必须经由一个对象去激活(有一个this指针)   通过将函数声明为...
  • 拒绝编译器自动生成函数 参考
  • Jmeter时间函数

    千次阅读 2022-03-11 12:27:59
    目录 1、前言 2、函数助手 3、time函数 ...Jmeter 的函数助手提供了三种时间函数,分别是:time、timeShift、RandomDate 2、函数助手 1、打开 Jmeter,例如:测试计划里,依次创建线程组、用户参
  • Python 内置函数详解

    万次阅读 多人点赞 2019-11-13 17:21:35
    Python 的内置函数数量众多,功能强大,如果能够灵活运用,必将极大地提高编程效率。...比如,我们说的类型转换函数 int()、str()、float() 等,都是类,而 print()、sorted() 等才是真正地函数
  • MySQL 创建函数, MySQL定义函数实现汉字转拼音 MySQL汉字转拼音 一、MySQL创建函数 1、语法 CREATE FUNCTION fun_name([paramName type , paramName type]) RETURNS type BEGIN -- do something RETURN ...
  • 解决VS2019编译Qt报错:C3615,“qCountLeadingZeroBits”不能生成常量表达式
  • 系统:Win10 环境:VS2019+QT5.9.3 +vs2015编译器 Qt App项目,在使用Qwt时什么都没做,默认项目...2 检查项目参数,由于项目是vs自动生成,因此项目参数使用的是Win10SDK,和vs2019的编译器,于是修改后解决. 出错前:...
  • 我这里并不是要讲“伪随机”、“真随机”这样的问题,而是关于如何生成服从某个概率分布的随机数(或者说 sample)的问题。比如,你想要从一个服从正态分布的随机变量得到 100 个样本,那么肯定抽到接近其均值的样本...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 195,654
精华内容 78,261
关键字:

常生成函数