组合数学机械化通用程序库软件V10用户手册

11《组合数学机械化通用程序库软件V1.0》用户手册一、引言本系统的名称为“组合数学机械化通用程序库软件V1.0”，是由南开大学研发的。本软件的首批用户是南开大学组合数学中心的老师和研究生。本用户手册是关于组合数学机械化通用程序库软件的帮助性文件，目的在于描述软件的安装和使用，重点在于阐述程序库中主要函数的理论背景、调用格式及输出结果。预期参考人员包括用户、测试人员、开发人员、项目管理者和其他质量管理人员。本用户手册中涉及到如下专用术语和外文单词缩写形式：a)组合恒等式机器证明：Zeilberger在Gosper算法的基础上提出了一套证明组合恒等式的系统方法，后来又提出了WZ-对的方法，不仅能证明许多已有的恒等式，还能发现一些新的恒等式。其主要思想是证明组合恒等式的两边满足相同的递推关系，然后验证等式两边在初值情况下相等。b)对称函数理论：对称函数理论是代数组合学中的一个重要研究领域，它主要研究对称群和对称多项式的代数性质和组合性质，在数学的其他分支和数学物理中有广阔的应用，是一个受到广泛关注的研究方向。c)组合双射理论：组合双射是指在同样数量的两个对象之间的对应。该理论是组合计数理论的一个重要研究方向，有助于理解各种组合对象之间的密切联系。d)q-级数：主要内容为超几何级数的q-模拟。利用组合对应、算子理论、基本变换、反演、自动证明等方法研究q-恒等式和q-级数的性质。e)APCI：AutoproofofCombinatoricalIdentitiesf)SYMF：SymmetricFunctionsg)EPPT：EnuemratingPaths,PermutationsandTreesh)CPQS：ComputationPackageforq-Seriesi)EVST：ExtremalValueofSetTheoryj)PAPM：PackageforApplicationsinProbabilityMethod相关参考资料包括：a)组合数学机械化通用程序库软件V1.0技术总结报告b)组合数学机械化通用程序库软件V1.0概要设计说明书c)组合数学机械化通用程序库软件V1.0详细设计说明书22d)软件设计文档国家标准GB8567-88二、功能介绍本软件共完成了六个通用程序库，重点实现了机器证明、q-级数、对称函数和组合计数等四个领域的常用函数包。这些程序库包括了机器证明、q-级数、对称函数、排列和路及树、集合论和概率方法等领域中常用的基本函数和过程。在组合恒等式机器证明方面，我们实现了SisterCeline算法求正则超几何项递归关系、算子消元法、q-Zeilberger算法、Gosper算法、素性判别的随机算法、正交多项式的关联系数求解、求多项式解的多项式算法等内容。其中Gosper算法和q-Zeilberger算法的算法实现尤为重要。在q-级数方面，我们重点实现了有关q-级数等式方面的组合双射算法。主要包括Sylvester映射、特定分拆生成、Corteel-Lovejoy映射、Euler定理的组合证明、Bressoud映射、Franklin对合、Durfee方块和共轭分拆。这些组合双射算法是该领域的基本算法，为进一步构造双射提供了强大的工具。在对称函数方面，我们实现了该领域常用的一些函数和过程，包括置换的（轮换）分解、格排列生成、分拆与杨表表示、分拆与斜分拆的秩、寻找最长递增子序列、RSK算法、排列的Growthdiagram生成、犹豫杨表和集合划分之间的对应、匹配和Oscillatingtableaux之间的对应等基本组合对象生成算法和基本组合算法。其中，RSK算法是对称函数的核心算法，具有广泛的应用，它的软件实现将大大有助于我们研究对称函数。在组合计数方面，我们重点研究了有关路、排列和树的程序实现。排列中的基本函数包括PermInsertion、PermPosition、PermList、PermSubseqN、IsPermutation等生成和判断函数。有禁模式的排列是计算机科学中重要的组合结构。在这方面我们编写了PermSamepatternt、PermNbpattern、PermNbpatterns、PermNbpatternT、PermNbpatternsT、PermDistpattern、PermDistpatterns、PermAvoidP、PermAvoidPs等模式排列生成函数。此外我们编写了排列的基本统计量等生成函数。在路的算法实现方面，我们编写了Dyck路、自由Dyck路、有2k个缺陷的n-Dyck路的生成函数。匹配在生物信息学中有很多应用，我们实现了MatchingList、MatchingNbpattern、MatchingAvoidP、RNASSN和RNA二级结构等生成算法。在标号树方面，我们给出了标号树的序列表示和函数表示。在集合论方面，我们实现了具有特定性质的集合的生成函数，包括列出包含某特定集合的子集的函数shade、列出包含于某特定子集的函数shadow、匹配布尔代数元素的函数matchtofirst、布尔代数对称链分解函数schd和寻找特定对称链函数symchain和寻找与集系有特殊性质的特定子集的函数Bondy。组合中的概率方法是通过设定概率空间，将某个存在性稳定转化为概率非零事件问题。在开发的程序库中，我们重点实现了离散随机变量和连续随机变量的期望和方差函数，快速排序算法和超图的二染色算法。这是概率方法中最经典的例子和最基本的算法。33三、运行环境硬件环境：IntelPentiumIII650MHz、128MRAM、2G硬盘空间或更高操作系统：Windows2000或WindowsXP支持软件：Maple10四、安装方法本系统共有三个安装文件combmech.lib、combmech.hdb和combmech.ind，假设它们位于E盘根目录下，安装步骤如下：（1）打开数学软件Maple10。（2）在Maple命令行内输入如下命令设定程序库路径[libname:=libname,E:\\;（3）将程序库combmech.lib读入当前程序库路径[readlib(E:\\combmech.lib);（4）输入如下命令[with(APCI);若显示结果如下[Gosper2,Gosper3,Polysolve,Primetest,Rrop,Tran,cancel_operator,cceline,celine,celine1,re,sequence_to_tree,tree_to_sequence]则表示已正确安装软件。五、数学符号显示说明在Maple中数学的符号显示与实际表达方式不同，如输入“m[2]”显示为下标m2；输入“matrix([[1,1,1,1],[1,1,0,0],[1,0,0,0]])”，则显示为111111001000.六、软件使用本系统共包括六个程序库，下面将分别说明每个程序库主要函数如何使用。（1）APCI——自动证明程序库（1．1）调用软件包[with(APCI);显示结果如下[Gosper2,Gosper3,Polysolve,Primetest,Rrop,Tran,cancel_operator,cceline,celine,celine1,re,sequence_to_tree,tree_to_sequence]（1．2）Gosper2和Gosper3函数Gosper算法给出了如下问题的解答：给定一个超几何项tn（相邻两项之比tn+1/tn为有关于n的有理函数），求超几何项zn使得zn+1-zn=tn。其算法可以分为三步：1、求tn相邻两项之比r(n)，2、求r(n)的GP表示，3、求44Gosper方程的多项式解。函数Gosper2实现了算法的前两步，Gosper3实现了算法的第三步。Gosper2函数的理论背景如下：满足上述条件的多项式a(n),b(n),c(n)被称为有理函数r(n)的GP表示。给定超几何项tn，求tn+1/tn的GP表示这一功能由函数Gosper2给出。例如取tn为如下超几何项[t:=binomial(2*n-3,n)/4^n;显示结果如下调用函数Gosper2[Gosper2(t,n);显示结果如下给定多项式a(n),b(n),c(n)，关于多项式x(n)的如下方程被称为Gosper方程函数Gosper3实现了求解Gosper方程的功能。以方程nx(n+1)-(n-1)x(n)=1为例，调用如下：[Gosper3([n,n+2,1],n);显示结果如下thesolveofx(n)is:K1Cm1n（1．3）函数celine和cceline理论背景如下：55下面以函数f(n,k)=kn!/(k!(n-k)!)为例进行说明如何调用函数celine和cceline.调用格式[celine((n,k)-k*n!/(k!*(n-k)!),1,2);显示结果如下(n2Kn)F(nK2,kK1)C(2n2K3n)F(nK1,kK1)C(n2Kn)F(nK2,k)C(n2Kn)F(nK1,k)C(K2n2C5nK3)F(n,k)=0调用格式[cceline((n,k)-k*n!/(k!*(n-k)!));显示结果如下(KnC1)F(n,k)CF(nK1,k)nCF(nK1,kK1)n=0（1．4）函数re理论算法说明：使用该函数时需要使用软件包qsum9.mpl[read:=E:\\qsum9.mpl;函数调用格式[re(qhyperterm([0],[],q,z,k),[z]);显示结果如下Therecurrencerelationsatisfies:s(zq)C(zK1)s(z)=0（1．5）函数Tran功能说明：此函数也需要软件包qsum9.mpl的支持，函数调用格式66[Tran(qhyperterm([a,b],[c],q,z,k),[z]);显示结果如下TheconditionthattheTransformationFormulasshouldcomplywithis:|c/q|1.Therecurrencerelationsatisfies:f(z)=K(KzaqCqCcKzbq)f(zq)q(zK1)K(zabqKc)f(q2z)q(zK1)（1．6）函数Rrop理论背景函数调用格式[Rrop(pochhammer(x,n));显示结果如下wecanget[a,b,c,y][1,Kn,0,y]（1．7）函数Polysolve理论背景函数调用格式[Polysolve(N-1,n);显示结果如下thesolveofy(n)is:77a0K12nC12n2（2）SYMF——对称函数程序库（2．1）调用软件包[with(SYMF);显示结果如下[Bump,Bump2,ConjPar,Expectationplot,Expectv,InvBump,IsStdTab,IsTab,Par2StdTab,RSKcorresp1,RSKcorresp2,RSKinsert,Tab2Mat,Tab2Par,canonical,cellfilling,growthdia,insertone,invRSK,lattpermins,lattpermlist,longestisubs,mat2oscil,onerowinsert,onerowinvinsert,oscil2mat,pair2vacilla,parrank,reducode,skewrank,srank,vacilla2pair]（2．2）函数pair2vacilla和vacilla2pair理论背景：函数调用格式[pair2vacilla({{1},{5},{2,6},{3},{4,7}},[[1,7],[5]]);显示结果如下[[],[],[[1]],[[1]],[[1,2]],[[1,2]],[[1,2]],[[1,2]],[[1,2],[4]],[[1,2],[4]],[[1,2],[4],[5]]