组合数学5

1组合数学Combinatorics5神奇的序列5-1Catalan数清华大学马昱春计算机界的精灵•一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?1，2，3,41入，2入，2出，1出3入，3出，4入，4出1234计算机界的精灵•一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?第一次为空时进行分步？1234第一次为空时有k个元素出栈，即1出栈的序号;将1~n的序列分成两个序列，其中一个是1~k-1共k-1个元素另外一个是k+1~n，共n-k个元素设f(n)是n个元素的出栈序列数f(n)=f(k-1)*f(n-k)k=1~nf(n)=f(0)*f(n-1)+f(1)*f(n-2)+.......+f(n-2)*f(1)+f(n-1)*f(0)二叉树•n个节点构成的二叉树，共有多少种情形？•根肯定会占用一个结点，设T(i,j)表示根的左子树含i个结点，右子树含j个结点•除了根之外剩余的n-1个结点可以有如下的分配方式，T(0,n-1),T(1,n-2),...T(n-1,0)，。•设问题的解为f(n)，•假设f(0)=1，那么f(1)=1,f(2)=2,f(3)=5。f(n)=f(0)*f(n-1)+f(1)*f(n-2)+.......+f(n-2)*f(1)+f(n-1)*f(0)Catalan数•1751年欧拉在与哥德巴赫的通信中提出一个问题：–正n边形化分为不重叠的三角形有多少种方法？C(n)=C(0)*C(n-1)+C(1)*C(n-2)+.......+C(n-2)*C(1)+C(0)*C(n-2)回顾历史•1758年，JohannSegner给出了欧拉问题的递推关系•1838年，研究热潮–GabrielLame给出完整证明和简洁表达式–EugèneCharlesCatalan在研究汉诺塔时探讨了相关问题,解决了括号表达式的问题.–……–1900EugenNetto在著作中将该数归功于Catalan.历史回顾•1988年以及1999年的文献研究表明实际上最初发现Catalan数的也不是Euler，–1753欧拉在解决凸包划分成三角形问题的时候，推出了Catalan数。–1730年我国清朝时期的明安图（蒙古人）比Catalan更早使用了Catalan数，见《割圜密率捷法》。后来他的学生在1774年将其完成发表。Catalan数•比利时的数学家欧仁·查理·卡塔兰(1814–1894)命名•OEISA000108•1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700,1767263190,6564120420,24466267020,91482563640,343059613650,1289904147324,4861946401452,...C(n)=C(0)*C(n-1)+C(1)*C(n-2)+.......+C(n-2)*C(1)+C(n-1)*C(0)C(n)=C(0)*C(n-1)+C(1)*C(n-2)+.......+C(n-2)*C(1)+C(n-1)*C(0)栈与格路•作业W2-G1：(n,n)y=x(1,-1)x-y=1(0,0)DyckPath限制线要向下或向右移一格，得x－y=1;问题转化为求(0,1)到(n,n)不接触x-y=1的格路数。(0,0)关于x－y=1的对称点为(1,-1).利用上一问的方法所求格路数为Cn==(n,n)y=x(1,-1)x-y=1(0,0)母函数证法•母函数c(x)2=C0C0+(C1C0+C0C1)x+(C2C0+C1C1+C0C2)x2+……C1C2C3C0=1c(x)=C0+C1x+C2x2+……c(x)2=C1+C2x+C3x2+……0111nnRxnnx!))...(()(Cn=问题等价如果失去括号，运算将会怎样•这个经典的括号匹配问题一共有多少种方式呢？•用Cn表示长度2n的Dyckword的个数。•这里Dyckword是一个有n个X和n个Y组成的字串，且所有的从第一个字符开始的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的Dyckwords:•XXXYYYXYXXYYXYXYXYXXYYXYXXYXYYDyck语言•Dyck语言是计算机领域很有意思的一种语言。在计算机科学、数学、语言学的形式化语言理论中，Dyck语言是一个包含了括号[、]的平衡字符串的语言。•对于那些必须要有正确的括号嵌套序列的表达式，它在解析的过程中扮演了很重要的角色，比如算数和代数表达式。•它是在数学家沃尔特·冯·戴克死后被命名的。Handsacrossthetable•有n个人围在圆桌参加晚宴，他们两两直接想通过握手相互认识。但是可能影响别人，所以他们的手不能有交叉，那么一共有多少种握手的方式？•结果是Catalan数。这就是著名的“Handsacrossthetable”问题，还有同名爱情电影呢。Catalan数•20世纪研究的热潮–M.Kuchinski找到31种问题结构都对应Catalan数–到2010年8月21日，R.Stanley找到190种不同问题结构都可以用Catalan数来计数。19组合数学Combinatorics5神奇的序列5-2指数型母函数清华大学马昱春20指数型母函数•二项式定理•C(n,k)的生成函数•其系数表示从n项中选择k项的组合数2(1)(1)(1)(1)12!nknnnnnkxnxxxk(1)(1)(1)(1)(1)......(1)(1)nxxxxxxxx1xx…x1012k-11231221000(,)!(1)(,)(,)!!knkkkkkCnkkxxCnkxxPnkkk𝐶𝑛,𝑘𝑘!=P(n,k)如果要计算排列，而非组合时，应采用如下的通项2{1,,,...,}2!!nxxxn21多重全排列•请问“pingpang”8个字母有多少种不同的排列？–加上下标以区别p1p2n1n2g1g2ia！！！！222811222822多重全排列•3个a1,2个a2,3个a3–组成k个数的组合有多少种？)1)(1)(1()(32232xxxxxxxxxG)1()23321(325432xxxxxxxx8765432369109631xxxxxxxx23•3个a1,2个a2,3个a3取4个进行组合，组合的样子？•从x4的系数可知，这8个元素中取4个组合，其组合数为10。这10个组合可从下面展开式中得到)1)(1)(1(3323322231211xxxxxxxx)()()()1(12221331322132213312322232123213323313323223132232132122122131333231222121321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx8765432369109631xxxxxxxxxG)()1(])()()()(1[33233223122212312212213122212121xxxxxxxxxxxxxxxxxxxx24多重排列3个a1,2个a2,3个a3取4个进行排列有多少种？对应的两个两个的不同排列为例，其不同排列数为2321xx6!2!2!4即六种。同样，1个,3个的不同排列数为,3311aaaa,1331aaaa,3131aaaa,1313aaaa,1133aaaa,3113aaaa1a3a4!3!4即以此类推。,3331aaaa,1333aaaa,3133aaaa,3313aaaa25故可得问题的解，其不同的排列数为)!2!21!1!31!1!2!11!1!1!21!1!31!2!21!2!1!11!2!21!3!11!3!11(!4222133132213221331232223212321332331xxxxxxxxxxxxxxxxxxxxxxx!3!2!2!3!23!33!2!24!4)!23!2!23!34(!47036181626为了便于计算，利用上述特点，形式地引进函数)!3!2!11)(!2!11)(!3!2!11()(32232xxxxxxxxxGe)61211()1211256722(1325432xxxxxxxx))()(()(32232111xxxxxxxxxG!8560!7560!6350!5170!470!328!291!31!)(8765432xxxxxxxxxGe87654327217287235121712353142931xxxxxxxx)!23!2!23!34(!47036181627•母函数•指数型母函数,,,210aaa对于序列构造一函数：,,,,210aaa,)(2210xaxaaxG称函数G(x)是序列的母函数求解组合问题求解排列问题对于序列，函数,,,210aaakkexkaxaxaxaaxG!!3!21!)(332210称为是序列的指数型母函数,,,210aaa2012nnxnxxxexnn.......!!!是{1,1,…,1}的指数型母函数28指数型母函数多重全排列：若元素有个，元素有个，…，元素有个，由此；组成的n个元素的排列，不同的排列总数为1a1n2a2nknka!!!!21knnnn其中knnnn21多重排列：若元素有个，元素有个，…，元素有个，由n个元素中取r个排列，设其不同的排列数为。则序列的指数型母函数为1a1n2a2nknkarpnppp,,10)!!21!1()!!21!1()!!21!1()(2221221knnnenxxxnxxxnxxxxGk29指数型母函数指数型母函数解决有重元素的排列具有优越性。例：由1，2，3，4四个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现；2出现次数不超过1次；3出现次数可达3次，也可以不出现；4出现次数为偶数。求满足上述条件的数的个数。30数1出现次数不超过2次，但不能不出现；2出现次数不超过1次；3出现次数可达3次，也可以不出现；4出现次数为偶数设满足条件的r位数为ar，序列a0,a1,…a10的指数型母函数为)!4!21)(!3!2!11)(1)(!21!()(42322xxxxxxxxxGe10987654322881481288148174843244338325xxxxxxxxxx!!!!!!!!!!101260097650814071785664552154643182511098765432xxxxxxxxxx由此可见满足条件的5位数共215个。)1444881247321)(2123(76543232xxxxxxxxxx31举例例:求1，3，5，7，9五个数字组成的n位数的个数，要求其中3，7出现的次数为偶数，其他1，5，9出现次数不加限制。设满足条件的r位的个数为ar，则序列a1,a2,a3…对应的指数型母函数为332242321421)!!()!!()(xxxxxxGe32由于,!!32132xxxex).(21!4!2142xxeexxxxxxxxeeeeeeexG3223224141)()()(