中英文对照网站怎么做,定制礼品,建立网站有哪几种方式,2023年第三波新冠9月1. 简介
在数学中#xff0c;某个序列的母函数(Generating function#xff0c;又称生成函数)是一种形式幂级数#xff0c;其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。
母函数可分为很多种#xff0c;包括普通母函数、指数母函…1. 简介
在数学中某个序列的母函数(Generating function又称生成函数)是一种形式幂级数其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。
母函数可分为很多种包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题因此选用何种母函数视乎序列本身的特性和问题的类型。
这里先给出两句话不懂的可以等看完这篇文章再回过头来看 1.“把组合问题的加法法则和幂级数的乘幂对应起来” 2.“母函数的思想很简单 — 就是把离散数列和幂级数一 一对应起来把离散数列间的相互结合关系对应成为幂级数间的运算关系最后由幂级数形式来确定离散数列的构造. “ 我们首先来看下这个多项式乘法
2. 母函数的定义 3. 例子
这里先给出2个例子等会再结合题目分析
第一种
有1克、2克、3克、4克的砝码各一枚能称出哪几种重量每种重量各有几种可能方案
考虑用母函数来解决这个问题
我们假设x表示砝码x的指数表示砝码的重量这样 1个1克的砝码可以用函数11∗x111*x^111∗x1表示 1个2克的砝码可以用函数11∗x211*x^211∗x2表示 1个3克的砝码可以用函数11∗x311*x^311∗x3表示 1个4克的砝码可以用函数11∗x411*x^411∗x4表示 上面这四个式子懂吗
我们拿1x21x^21x2来说前面已经说过x表示砝码x的指数表示砝码的重量初始状态时这里就是一个质量为2的砝码。
那么前面的1表示什么按照上面的理解1其实应该写为1∗x01*x^01∗x0,即1代表重量为2的砝码数量为0个。
所以这里11x21x01x211x^2 1x^0 1x^211x21x01x2即表示2克的砝码有两种状态不取或取不取则为1x01x^01x0取则为1∗x21*x^21∗x2
不知道大家理解没我们这里结合前面那句话
“把组合问题的加法法则和幂级数的乘幂对应起来“
接着讨论上面的1x21x^21x2这里x前面的系数有什么意义
这里的系数表示状态数(方案数)
1x21x^21x2也就是1x01x21x^0 1x^21x01x2也就是上面说的不取2克砝码此时有1种状态或者取2克砝码此时也有1种状态。(分析)
所以前面说的那句话的意义大家可以理解了吧
几种砝码的组合可以称重的情况可以用以上几个函数的乘积表示
(1x)(1x2)(1x3)(1x4)(1x)(1x^2)(1x^3)(1x^4)(1x)(1x2)(1x3)(1x4)
(1xx2x4)(1x34x7)(1xx^2x^4)(1x^3^4x^7)(1xx2x4)(1x34x7)
1xx22x32x42x52x62∗x7x8x9x101 x x^2 2x^3 2x^4 2x^5 2x^6 2*x^7 x^8 x^9 x^{10}1xx22x32x42x52x62∗x7x8x9x10
从上面的函数知道可称出从1克到10克系数便是方案数。经典
例如右端有2x52 x^52x5 项即称出5克的方案有2种53241同样612342101234。故称出6克的方案数有2种称出10克的方案数有1种 。
第二种
接着上面接下来是第二种情况
求用1分、2分、3分的邮票贴出不同数值的方案数
大家把这种情况和第一种比较有何区别第一种每种是一个而这里每种是无限的。 母函数图(4)
以展开后的x4x^4x4为例其系数为4即4拆分成1、2、3之和的拆分方案数为4
即 411111121322411111121322411111121322
这里再引出两个概念整数拆分和拆分数
所谓整数拆分即把整数分解成若干整数的和相当于把n个无区别的球放到n个无标志的盒子盒子允许空也允许放多于一个球。
整数拆分成若干整数的和办法不一不同拆分法的总数叫做拆分数。
现在以上面的第二种情况每种种类个数无限为例给出模板
#include
using namespace std;
// Author: Tanky Woo
// www.wutianqi.com
const int _max 10001;
// c1是保存各项质量砝码可以组合的数目
// c2是中间量保存没一次的情况
int c1[_max], c2[_max];
int main()
{ //int n,i,j,k;int nNum; // int i, j, k;while(cin nNum){for(i0; inNum; i) // ---- ①{c1[i] 1;c2[i] 0;}for(i2; inNum; i) // ----- ②{for(j0; jnNum; j) // ----- ③for(k0; kjnNum; ki) // ---- ④{c2[jk] c1[j];}for(j0; jnNum; j) // ---- ⑤{c1[j] c2[j];c2[j] 0;}}cout c1[nNum] endl;}return 0;
}我们来解释下上面标志的各个地方(重点) ① 、首先对c1初始化由第一个表达式(1xx2..xn)(1xx^2..x^n)(1xx2..xn)初始化把质量从0到n的所有砝码都初始化为1. ② 、 i从2到n遍历这里i就是指第i个表达式上面给出的第二种母函数关系式里每一个括号括起来的就是一个表达式。 ③、j 从0到n遍历这里j就是(前面i個表达式累乘的表达式)里第j个变量。如(1x)(1x2)(1x3)(1x)(1x^2)(1x^3)(1x)(1x2)(1x3)j先指示的是1和x的系数i2执行完之后变为 (1xx2x3(1x3)(1xx^2x^3(1x^3)(1xx2x3(1x3)这时候j应该指示的是合并后的第一个括号的四个变量的系数。 ④ 、 k表示的是第j个指数所以k每次增i因为第i个表达式的增量是i。 ⑤ 、把c2的值赋给c1,而把c2初始化为0因为c2每次是从一个表达式中开始的。 咱们赶快趁热打铁来几道题目 相应题目解析均在相应的代码里分析 题目http://acm.hdu.edu.cn/showproblem.php?pid1028 代码http://www.wutianqi.com/?p587 这题大家看看简单不把上面的模板理解了这题就是小Case! 看看这题 题目http://acm.hdu.edu.cn/showproblem.php?pid1398 代码http://www.wutianqi.com/?p590 要说和前一题的区别就只需要改2个地方。 在i遍历表达式时可以参考我的资料—《母函数详解》把inNum改成了iinNum,其次在k遍历指数时把ki变成了kii; Ok,说来说去还是套模板~~~ 题目http://acm.hdu.edu.cn/showproblem.php?pid1085 代码http://www.wutianqi.com/?p592 这题终于变化了一点但是万变不离其中。 大家好好分析下结合代码就会懂了。 题目http://acm.hdu.edu.cn/showproblem.php?pid1171 代码http://www.wutianqi.com/?p594 还有一些题目大家有时间自己做做 HDOJ17091028、1709、1085、1171、1398、2069、2152 原创文章欢迎各位转载但是请不要任意删除文章中链接请自觉尊重文章版权违法必究谢谢合作。Tanky Woo原创, www.WuTianQi.com 附 1.在维基百科里讲到了普通母函數、指數母函數、L級數、貝爾級數和狄利克雷級數 http://zh.wikipedia.org/zh-tw/%E6%AF%8D%E5%87%BD%E6%95%B0 2Matrix67大牛那有篇文章什么是生成函数 http://www.matrix67.com/blog/archives/120 3.大家可以看看杭电的ACM课件的母函数那篇我这里的图片以及一些内容都引至那。 如果大家有问题或者资料里的内容有错误可以留言给出博客:http://www.wutianqi.com/ Tanky Woo原创文章转载请注明出处http://www.wutianqi.com/?p596。 对于任何转载本博客文章且不保留原文链接或任意删改文中链接的行为本人将一定周旋到底 老版下载地址 母函数Generating function详解点击下载 (仅作保留所用里面有错误建议看我的最新版本关注本博客http://www.wutianqi.com/?p539) 4. 矩母函数Moment Generating Function
“我们需要更多的特征来描述分布例如峰度偏度除了常用的平均值方差这些特征统一称为矩那么有没有一个函数能够计算所有矩呢当然有矩母函数你就可以通过微分来计算各种矩而不是从定义的积分算你肯定知道微分比积分容易吧” https://blog.csdn.net/Anne033/article/details/109304935
4.1 概率统计中的“矩”是什么
对比物理的力矩你会发现概率论中的“矩”真的是很有启发性的一个词。
4.1.1 力矩
大家应该都知道物理中的力矩我这里也不展开说细节了用一幅图来帮助大家回忆一下
4.1.2 概率论中的“矩”
在概率论中有一杆无处不在的“秤”。因为这把“秤”的存在所以我们有了“矩”。
4.1.2.1 彩票的问题
福利彩票每一注两元钱真是中国的良心啊猪肉、房价都涨了多少了 每一注的中奖几率如下胡诌的 称量实际上是
4.1.3 “矩” %%%
比方说我们感兴趣的是随机变量X。 矩是X的期望值例如EXEX²EX³等。 第一矩是EX 第二矩是EX² 第三矩是EX³ … 第n个矩是EX ^ n。
当然我们非常熟悉前两个矩均值μ EX和方差EX²−μ²。它们是X的重要特征。 平均值是 平均值方差是分布的分布程度。但是必须有其他的特征来定义分布。例如第三矩是分布的不对称性。第四关是尾巴有多沉、多厚。 这些矩告诉您有关分布的信息。
4.2 什么是矩产生函数MGF
关于产生/母函数https://blog.csdn.net/Anne033/article/details/109652192
顾名思义MGF实际上是生成矩的函数 EXEX²EX³…EX ^ n。也就是”矩“的母亲够通俗吧。 这就是您从MGF那里获取时光的方式。 4.3 证明为什么第n个矩是MGF的第n个导数
我们将使用泰勒级数证明这一点。 如果对③取另一种导数因此取两次则将得到EX²。 如果您采用另一个三阶导数则将得到EX³依此类推…… 当我第一次看到矩生成函数时我无法理解t在函数中的作用因为t似乎是我不感兴趣的任意变量。但是如您所见t是辅助变量。我们引入t是为了能够使用演算导数并使我们不感兴趣的项为零。 等等… 但是我们可以直接了当使用期望值的定义来计算。为什么我们还需要MGF 4.4 为什么我们需要MGF
为了方便当然是我们希望MGF可以轻松计算矩。 但是为什么MGF比定义期望值更容易 在我的数学教科书中他们总是问我“请找出计算二项式n, p泊松λ指数λ正态0, 1等的函数的矩。” 但是他们从未真正向我展示过为什么MGF会如此有用以至于它们激发喜悦。
我认为以下示例会给您带来喜悦最简单的示例显示MGF更容易指数分布的MGF。 我们将从PDF开始。 指数分布的PDF 导出指数的MGF。
对于存在的MGF应该存在期望值 E(etx)E(e ^ tx)E(etx)。 这就是为什么“ t-λ0”是要满足的重要条件的原因因为不满足积分将不会收敛。这称为散度检验这是在尝试确定积分是收敛还是发散时首先要检查的内容。 一旦有了MGFλ/(λ−t)λ/(λ-t)λ/(λ−t)计算矩就变成了求导数的问题这比积分更容易直接计算期望值。
使用MGF可以通过求导数而不是积分来查找矩
4.5 常见分布的MGF 4.6 MGF的属性 5. 注意事项
对于任何有效的MGFM0 1每当您计算MGF时插入t 0并查看是否得到1。 矩提供了一种指定分布的方法。例如您可以在前两个矩均值和方差完全指定正态分布。当您知道分布的多个不同矩时您将了解有关该分布的更多信息。如果有一个您没有认识的人并且您知道他们的身高体重肤色喜爱的爱好等您仍然不一定完全了解他们但是正在获得关于他们的越来越多的信息。 MGF的优点在于一旦有了MGF一旦存在期望值您就可以得到第n个矩。MGF将随机变量的所有矩编码为一个函数以后可以再次从中提取它们。 概率分布由其MGF唯一确定。如果两个随机变量具有相同的MGF则它们必须具有相同的分布。 对于那些对术语“矩”感到好奇的人像我一样为什么一个矩称为矩 分布的重要特征之一是它的尾巴有多沉重尤其是对于金融风险管理而言。如果您还记得2009年的金融危机那实际上就是无法解决罕见事件发生的可能性。风险管理人员低估了基金交易头寸中的许多金融证券的峰度峰度在希腊语中是指“凸起”。有时假设的风险曲线平滑的随机分布可能会在其中隐藏凸起。而且我们可以检测到使用MGF的人员
6. MGF and Laplace 6.1 Laplace变换的前世今生
依然是答强哥问感兴趣的同学可以先看看上一篇博客。
特意上了趟Wikipedia感兴趣的同学请戳这里然后就惊呆了又根据果壳网的小伙伴的提问与回答按图索骥找到了MIT的网易公开课彻底吓尿了我一直以为将Fourier变换与Laplace变换解释到基底这个层面对很多工科生来说就是人神共愤的事情了没想到这仅仅是个开始。
Wikipedia中原文阐述是The Laplace transform is related to the Fourier transform, but whereas the Fourier transform expresses a function or signal as a series of vibration(frequency), the Laplace Transform resolves a function into its moments.
我抄下这段英文的原因是有个词不大好翻译原文的意思是Laplace变换与Fourier变换有关但前者是将一个函数信号表达成一系列振动模式就是不同频率的正弦函数信号而Laplace变换则是将函数分解成它的moment。问题在于这个moment怎么翻译。
Laplace的起源与它后来的应用几乎没有一点关系而是涉及到概率论这也让我对Fourier变换的起源产生的质疑它早先到底是不是为了解决类似将一个复杂的函数或者信号拆成一系列的不同频率的简单函数或信号之和的问题而出现的有兴趣的同学可以去查查。这个moment不是常见的时刻的意思而是和一个统计量形象一点就是和物理量有关的一个量。先看看moment generating function 中文译名叫矩母函数这是我第一次在应用随机过程中听到的高大上的一个词后来因为这老师上课的水平实在不能苟同加上这门课内容又不是我这种弱智青年所能理解于是我再也没听这门课了即使这样因能听到这个词实在已是我家祖坟冒青烟的才能享受到的待遇了。 很像到这里先提一下很牛逼的矩母函数的来源吧然后再解释下Wikipedia里关于Laplace变换的那句话的含义感受什么才是西方式的逻辑思维绝壁不是从天而降的定义、介绍性质、知识花边和所谓应用的中国式教育下的逻辑。
数学家们也不是闲的没事研究Laplace变换这么个玩意儿起初没有人会知道会诞生出这么个经天纬地的变换出来他们只不过求解概率学一个小小的问题——矩母函数矩母函数无论是从中文名还是英文名都能看出来矩母意思就是矩的母亲。卧槽大家是不是觉得很狗血。矩母函数就是为了求矩而构造出来的函数因此是现有矩再有矩母函数的。正如古代先有的曹丕称魏文帝才后有的曹孟德被称为魏武帝的帝位也是可以有儿子传给老子的。
所以还是看看矩是怎么回事吧。力矩,转动惯量平均数方差skewness三次方差这些乱七八糟的东西将要一个个粉墨登场啦。 再次强调一下这个矩母函数就是Laplace变换的雏形而证明过程中我们看到矩母函数被展开成一个个系数为矩的泰勒级数展开的形式这就是为什么Wikipedia中提到Laplace变换是将函数分解成多个矩。
至此,Laplace变换的前生都讲完了。
不过下面这个解释我也挺喜欢的。
MIT微分方程公开课中提到Laplace变换是从幂级数中诞生出来的。
幂级数形式如下 一切看起来就是Laplace变换的样子了。
我宁愿选择倒过来看因为这样就可以把Laplace变换看成是幂级数求和得到的。 这个函数大概就是这帮天才想解决一个概率论上的问题就是这个矩的问题为了更好的求解这个矩问题丧心病狂地构造了矩母函数有了Laplace变换的雏形矩母函数的幂级数展开的形式展开的各项前的系数就是各种矩了。所以Wikipedia中才说Laplace变换是将一个函数拆成很多个矩的形式 最后只剩下一个问题概率论里这种矩到底是干什么用的具体什么高深的用途我不知道。当时我再也没听课了停留的记忆是求平均数方差三次差等很方便超简单往往就是求个矩母函数就能求出各阶矩有个很方便的通用的公式就能求出来。
PS接下来就应该看看Laplace变换用基底怎么解释才能高大上了
原文链接 https://zhuanlan.zhihu.com/p/148408669 https://en.wikipedia.org/wiki/Moment-generating_function http://www.wutianqi.com/blog/596.html https://zhuanlan.zhihu.com/p/148408669 https://zhuanlan.zhihu.com/p/147749867 https://blog.csdn.net/simplelove17/article/details/26604817
