第三周-初识母函数

1组合数学Combinatorics3似函数，非函数3-1从投掷色子说起清华大学马昱春2母函数母函数是函数吗？母函数的定义定义2-1对于序列c0,c1,c2…,构造一函数G(x)=c0+c1x+c2x2+…,称G(x)为序列c0,c1,c2…的母函数。x2+2x3+3x4+4x5+5x6+6x7+5x8+4x9+3x10+2x11+x12G(x)=组合数学的主要内容是计数，用的最多的计数工具要算母函数。3母函数母函数，是组合数学中尤其是计数方面的一个重要理论和工具，运用这种数学方法往往对程序效率与速度有很大改进。母函数方法不仅在概率论的计算中有重要地位，而且已成为组合数学中一种重要方法。母函数和计数法则•例：两个色子掷出6点，有多少种可能？•解法1：第一位数1-5，且第二位数由第一位来确定•解法2：1+5=5+1；或2+4=4+2；或3+34+=6雅各布·伯努利瑞士数学家1654年－1705年•投掷m粒色子时，加起来点数总和等于n的可能方式的数目？5×1=52+2+1=5且:乘法法则或:加法法则•例：两个色子掷出n点，有多少种可能？指数对应点数)(×()母函数和计数法则5G(x)=(x+x2+…+x6)2=x2+2x3+3x4+4x5+5x6+6x7+5x8+4x9+3x10+2x11+x12x1x2x4x6X且:乘法法则或:加法法则()2×←x2或或或或或(函数中的系数对应计数序列。两个色子掷出n点的可能方法数即为求G(x)=(x+x2+…+x6)2中xn的系数。x4x6:·x5+x2·x４+x3·x3=5x6)或或或或或+xx2x3x4x5x6++++(+xx2x3x4x5x6++++)=n++x4·x2+x5·x１x6的系数为5，表示两个色子掷出6点的可能方法有5种。??????母函数是母亲，计数序列是孩子。6•投掷m粒色子时，加起来点数总和等于n的可能方式的数目？雅各布·伯努利JakobI.Bernoulli瑞士数学家1654年－1705年G(x)=(x+x2+x3+x4+x5+x6)m母函数和计数法则(x+x2+x3+x4+x5+x6)(x+x2+x3+x4+x5+x6)展开式中xn项的系数(x+x2+x3+x4+x5+x6)(x+x2+x3+x4+x5+x6)+x2§1.母函数和计数法则•定义2-1对于计数序列c0,c1,c2…,函数G(x)是序列c0,c1,c2…的母函数。•1812年，法国数学家拉普拉斯在著作《概率的分析理论》的第一卷中系统地研究了母函数方法及与之有关的理论–计数工具–不考虑收敛性–不考虑实际上的数值–形式幂级数(Formalpowerseries)7c0c1c2……x++G(x)=拉普拉斯似函数,非函数,是？？§1.母函数和计数法则8对应关系计算（原像）求解原像p的数值（映像）对数映射将指数运算简化为做加法乘法求得映像lgp的数值反对数81314123p)lg()lg(lg41812331p§1.母函数和计数法则9映射关系徐利治我国著名数学家“数学发展中比比皆是通过映射手段求解的现象。”映射，是两类数学对象或集合之间的某种“对应关系”。------《数学方法论选讲》母函数和计数法则10原像映像aixi×bn-ixn-i=aibn-ixn多项式乘法运算使母函数具备了计数的能力乘法法则:n个计数对象可以划分为i个对象和n-i个对象aibn-i加法法则:n个计数对象所有的划分策略累加多项式乘法母函数映射系数对应？映射关系c0,c1,…,cn=n+(x+x2+x3+x4+x5+x6)(x+x2+x3+x4+x5+x6)=x2+2x3+3x4+4x5+5x6+……?)()(00kkkkkkxbxa=(a0+a1x+a2x2+…)×(b0+b1x+b2x2+…)aixibn-ixn-iniininnbac0210,...,,,xn0()nnnfxax0()nnnGxax函数:11x2+2x3+3x4+4x5+5x6+6x7+5x8+4x9+3x10+2x11+x12G(x)=母函数就是一列用来展示一串数字序列的挂衣架。—赫伯特·维尔夫a0a1a2a3a4a5x0x1x2x3x4x512§3本讲的小结寻找到映射关系就是“数学发现”。寻找映射是数学家重要的思维方式。定义2-1对于序列a0,a1,a2…,构造一函数G(x)=a0+a1x+a2x2+…,称G(x)为序列a0,a1,a2…的母函数。欧拉1764年前伯努利1705年前似函数,非函数,是映射拉普拉斯1812年13组合数学Combinatorics3似函数，非函数3-2母函数的计数问题清华大学马昱春14母函数和计数法则例1：若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有项，即称出5克的方案有2种。52x41325同样，432110243216故称出6克的方案有2个，称出10克的方案有1个10987654324322222211111xxxxxxxxxxxxxx))()()((15问题举例例1：若有1、2、4、8、16、32克的砝码各一枚，问能称出那几种重量？有几种可能方案？)1)(1)(1)(1)(1)(1()(3216842xxxxxxxG3264163281648242111111111111xxxxxxxxxxxx)1()1)(1(2xxxxx1164630632)1(kkxxxx16问题举例从母函数可以得知，用这些砝码可以称出从1克到63克的重量，而且办法都是唯一的。这问题可以推广到证明任一十进制数n，可表示为0,10,20kaankkkk而且是唯一的。17问题举例例:整数n拆分成1，2，3，…，m的和，并允许重复，求其母函数。若整数n拆分成1，2，3，…，m的和，并允许重复，其母函数为：)1()1)(1(1111111)1()1)(1()(2224221mmmmxxxxxxxxxxxxxG.....1)1(21xxx18问题举例如若其中m至少出现一次，其母函数如何？)())(()())(()(mmmmxxxxxxxxxxxG11111224222)1()1)(1(1)1()1)(1(1)(1222mmxxxxxxxG上式的组合意义：即整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。•人民币常用硬币：1角，5角，1元。•人民币硬币的母函数•美元常用硬币：1角，2角5分，5分硬币的组合19102050100100200()(1...)(1...)(1...)Gxxxxxxx10202550()(1...)(1...)Gxxxxx51010202550()(1...)(1...)(1...)Gxxxxxxx20组合数学Combinatorics3似函数，非函数3-3整数拆分清华大学马昱春21整数的拆分所谓自然数(正整数)分拆,就是将一个正整数表达成若干个正整数之和:各部分之间考虑顺序的叫有序分拆(Composition);否则叫无序分拆(Partition).3的有序2-拆分：3=2+1=1+2n的有序r-拆分的个数是C(n-1,r-1)n个球，要分成r份，用r-1个隔板插入到球之间的n-1个空隙，方案数C(n-1,r-1)放球模型：n的一个r-分拆相当于把n个无区别的球放到r个有标志的盒子，盒子不允许空着n个球n-1个空隙r-1个隔板……•无序分拆•3的无序2-拆分：3=2+1•3的所有无序拆分3=3+0+0=2+1+0=1+1+1•x1+x2+…+xr=n的非负整数解个数？C(n+r-1,n)所谓整数拆分(partitionofapositiveintegern)即把整数分解成若干整数的和，相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。1..11..11..11..1n个1x1个1r-1个门框有序拆分的放球模型：n的一个r-分拆相当于把n个无区别的球放到r个有标志的盒子，盒子不允许空着相当于把n个无区别的球放到r个有标志的盒子，盒子允许空着0+3+03+0+0与无序拆分不同§2.母函数的应用：整数拆分数•正整数的无序拆分：将一个正整数n拆分成若干正整数的和，数字之间顺序无关并允许重复，其不同的拆分数即p(n)。–密码学，统计学，生物学……•p(3)=3:3，2+1，1+1+1.231740年诺地在信中问欧拉：整数的拆分方案数？中xn的系数诺地欧拉“1”的母函数“2”的母函数“m”的母函数WeilA．NumberTheory：AnApproachThoughtHistory[M]．Boston：Birkhouser，1984．284G(x)=(1+x+x2+…)(1+x2+x4+…)…(1+xm+x2m+…)…指数对应点数•OEIS:On-lineEncycopediaofIntegerSequences–数论相关权威数据库和算法库–p(n):A000041序列•整数拆分p(n)的母函数§2.母函数的应用：整数拆分数•OEIS:On-lineEncycopediaofIntegerSequences–数论相关权威数据库和算法库–p(n):A000041序列•整数拆分p(n)的母函数G(x)=(1+x+x2+…)(1+x2+x4+…)(1+x3+x6+…)…(1+xm+x2m)…§2.母函数的应用：整数拆分数25欧拉的母函数方法虽然巧妙，但是并不适合计算p(n)。多项式乘法的手工计算拉马奴金，1918年p(200)=3972999029388数学家一度认为整数拆分数的计算很难有大的突破了。欧拉，1740年p(29)=4565“数学史甚至是科学史上最奇怪的人”从未接受过正规数学训练的他具有惊人的数学直觉，独立发现了近3900个数学公式和命题。2012年美国数学家KenOno和同事证明他临终前发现的一个函数可以被用来解释宇宙黑洞的部分奥秘。弦论三大本笔记记录他所预见的数学命题，日后有许多得到了证实。如比利时数学家德利涅（V.Deligne）于1973年证明了拉马努金1916年提出的一个猜想，并因此获得了1978年的菲尔兹奖。美国佛罗里达大学于1997年创办了《拉马努金期刊》，专门发表“受到他影响的数学领域”的研究论文；印度之子，拉玛努金（1887-1920）•OEIS:On-lineEncycopediaofIntegerSequences–数论相关权威数据库和算法库–p(n):A000041序列•整数拆分p(n)的母函数G(x)=(1+x+x2+…)(1+x2+x4+…)(1+x3+x6+…)…(1+xm+x2m)…§2.母函数的应用：整数拆分数27欧拉的母函数方法虽然巧妙，但是并不适合计算p(n)。多项式乘法的手工计算拉马奴金，1918年p(200)=3972999029388OEISp(300)=9253082936723602数学家一度认为整数拆分数的计算很难有大的突破了。欧拉，1740年p(29)=4565(1+x+2x2+2x3+2x4+2x4…)nikgifkgf][][])[*(f[k]g[k]计算机的出现和组合算法的发展计算机64位整型无符号整型unsigned_int64最大表示264-118,446,744,073,709,551,61528§2.母函数的应用：整数拆分数p(416)=17,873,792,969,689,876,004p(417)=18,987,964,267,331,664,557基于整型表示的多项式乘法算法