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

30组合数学机械化通用程序库软件V1.0用户手册一、 引言本系统的名称为“组合数学机械化通用程序库软件V1.0”，是由南开大学研发的。本软件的首批用户是南开大学组合数学中心的老师和研究生。本用户手册是关于组合数学机械化通用程序库软件的帮助性文件，目的在于描述软件的安装和使用，重点在于阐述程序库中主要函数的理论背景、调用格式及输出结果。预期参考人员包括用户、测试人员、开发人员、项目管理者和其他质量管理人员。 本用户手册中涉及到如下专用术语和外文单词缩写形式：a) 组合恒等式机器证明：Zeilberger在Gosper算法的基础上提出了一套证明组合恒等式的系统方法，后来又提出了WZ-对的方法，不仅能证明许多已有的恒等式，还能发现一些新的恒等式。其主要思想是证明组合恒等式的两边满足相同的递推关系，然后验证等式两边在初值情况下相等。b) 对称函数理论：对称函数理论是代数组合学中的一个重要研究领域，它主要研究对称群和对称多项式的代数性质和组合性质，在数学的其他分支和数学物理中有广阔的应用，是一个受到广泛关注的研究方向。c) 组合双射理论：组合双射是指在同样数量的两个对象之间的对应。该理论是组合计数理论的一个重要研究方向，有助于理解各种组合对象之间的密切联系。d) q-级数：主要内容为超几何级数的q-模拟。利用组合对应、算子理论、基本变换、反演、自动证明等方法研究q-恒等式和q-级数的性质。e) APCI：Autoproof of Combinatorical Identitiesf) SYMF：Symmetric Functionsg) EPPT：Enuemrating Paths, Permutations and Treesh) CPQS：Computation Package for q-Seriesi) EVST：Extremal Value of Set Theoryj) PAPM：Package for Applications in Probability Method相关参考资料包括：a) 组合数学机械化通用程序库软件V1.0技术总结报告b) 组合数学机械化通用程序库软件V1.0概要设计说明书c) 组合数学机械化通用程序库软件V1.0详细设计说明书d) 软件设计文档国家标准GB8567-88二、 功能介绍本软件共完成了六个通用程序库，重点实现了机器证明、q-级数、对称函数和组合计数等四个领域的常用函数包。这些程序库包括了机器证明、q-级数、对称函数、排列和路及树、集合论和概率方法等领域中常用的基本函数和过程。在组合恒等式机器证明方面，我们实现了Sister Celine算法求正则超几何项递归关系、算子消元法、q-Zeilberger算法、Gosper算法、素性判别的随机算法、正交多项式的关联系数求解、求多项式解的多项式算法等内容。其中Gosper算法和q-Zeilberger算法的算法实现尤为重要。在q-级数方面，我们重点实现了有关q-级数等式方面的组合双射算法。主要包括Sylvester 映射、特定分拆生成、Corteel-Lovejoy 映射、Euler 定理的组合证明、Bressoud 映射、Franklin 对合、Durfee 方块和共轭分拆。这些组合双射算法是该领域的基本算法，为进一步构造双射提供了强大的工具。在对称函数方面，我们实现了该领域常用的一些函数和过程，包括置换的（轮换）分解、格排列生成、分拆与杨表表示、分拆与斜分拆的秩、寻找最长递增子序列、RSK 算法、排列的 Growth diagram生成、犹豫杨表和集合划分之间的对应、匹配和 Oscillating tableaux 之间的对应等基本组合对象生成算法和基本组合算法。其中，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。组合中的概率方法是通过设定概率空间，将某个存在性稳定转化为概率非零事件问题。在开发的程序库中，我们重点实现了离散随机变量和连续随机变量的期望和方差函数，快速排序算法和超图的二染色算法。这是概率方法中最经典的例子和最基本的算法。三、 运行环境 硬件环境：Intel Pentium III 650 MHz、128M RAM、2G硬盘空间或更高 操作系统：Windows 2000或Windows XP 支持软件：Maple 10四、 安装方法 本系统共有三个安装文件combmech.lib、combmech.hdb和combmech.ind，假设它们位于E盘根目录下，安装步骤如下：（1） 打开数学软件Maple 10。（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中数学的符号显示与实际表达方式不同，如输入“m2”显示为下标m2；输入“matrix(1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0) ”，则显示为.六、 软件使用本系统共包括六个程序库，下面将分别说明每个程序库主要函数如何使用。（1） APCI自动证明程序库（11） 调用软件包> with(APCI);显示结果如下Gosper2, Gosper3, Polysolve, Primetest, Rrop, Tran, cancel_operator, cceline, celine, celine1, re, sequence_to_tree, tree_to_sequence（12） Gosper2和Gosper3函数Gosper算法给出了如下问题的解答：给定一个超几何项tn（相邻两项之比tn+1/tn为有关于n的有理函数），求超几何项zn使得zn+1-zn=tn。其算法可以分为三步：1、求tn相邻两项之比r(n)，2、求r(n)的GP表示，3、求Gosper方程的多项式解。函数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)/4n; 显示结果如下 调用函数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);显示结果如下 （13） 函数celine和cceline理论背景如下：下面以函数f(n,k)= kn!/(k!(n-k)!)为例进行说明如何调用函数celine和cceline.调用格式>celine(n,k)->k*n!/(k!*(n-k)!),1,2);显示结果如下调用格式>cceline(n,k)->k*n!/(k!*(n-k)!);显示结果如下（14） 函数re理论算法说明：使用该函数时需要使用软件包qsum9.mpl> read:= "E:qsum9.mpl"函数调用格式>re(qhyperterm(0, , q, z, k), z)"显示结果如下 The recurrence relation satisfies: （15） 函数Tran功能说明：此函数也需要软件包qsum9.mpl的支持，函数调用格式> Tran(qhyperterm(a, b, c, q, z, k), z);显示结果如下The condition that the Transformation Formulas should comply with is: |c/q|<1.The recurrence relation satisfies:（16） 函数Rrop理论背景函数调用格式>Rrop(pochhammer(x,n);显示结果如下 we can get a,b,c,y （17） 函数Polysolve理论背景函数调用格式>Polysolve(N-1, n);显示结果如下 the solve of y(n) is: （2） SYMF对称函数程序库（21） 调用软件包> 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（22） 函数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, 1, 4, 5, 1, 4, 5, 1, 5, 1, 7, 5 Vacillating tableau V =, 0, 0, 1, 1, 2, 2, 2, 2, 2, 1,2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1函数调用格式>vacilla2pair(0, 0, 1, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1);显示结果如下P=, 1, 5, 2, 6, 3, 4, 7T=, 1, 7, 5（23） 调用函数mat2oscil将一个匹配变成振荡杨表>mat2oscil(1,4,2,6,3,5); 显示结果如下 然后调用函数oscil2mat将振荡杨表变回匹配>oscil2mat(, 1, 1, 1, 2, 1, 2, 1, );显示结果如下 这两个函数的理论背景如下：（24） 函数RSKcorresp1和RSKcorresp2理论背景：函数调用格式>RSKcorresp1(5,7,1,3,2);显示结果如下 函数调用格式>RSKcorresp2(5,7,1,3,2);显示结果：2（25） 函数growthdia理论背景：函数调用格式>growthdia(3, 1, 2);显示结果： （26） 函数longestisubs是用来求一个序列的极大递增子列。函数调用格式>longestisubs(5, 6, 2, 1, 7, 4, 3, 9, 8);显示结果：（27） 分拆与斜分拆的秩相关函数理论背景：函数调用格式>parrank(8, 6, 6, 4, 2);显示结果： 4函数调用格式>skewrank(6, 6, 4, 2, 3, 2, 1);显示结果： 3函数调用格式>reducode(6, 6, 4, 2, 3, 2, 1);显示结果：0 1 0 1 0 1 0 1 1 11 1 0 1 1 0 1 1 0 0（28） 分拆与杨表相关函数理论背景：函数调用格式>IsTab(1,1,2,3,4);显示结果：true函数调用格式>IsStdTab(1,5,2,3,4);显示结果：false函数调用格式>Par2StdTab(2,1);显示结果：具有形状2,1的标准杨表共有2个: 1, 2, 3, 1, 3, 2函数调用格式>Tab2Par(1,2,3,2,3,4);显示结果：3,2,1函数调用格式>Tab2Mat(1,2,3,2,3,4);显示结果： （29） 函数canonical给出置换的标准既约分解，其理论背景如下：函数调用格式>canonical(5, matrix(1, 5, 3, 4, 5, 2, 1);显示结果：The canonical reduced decomposition of the input permutation is:1 2 1 3 2 4 3（210） 函数lattpermlist理论背景：函数调用格式>lattpermlist(2, 1);显示结果：1,2,1 1,1,2（3） EPPT路、排列和树程序库（31） 调用软件包> with(EPPT);显示结果如下DOtoDif, DRT_FunctionToTree, DRT_TreeToFunction, DiftoDO, DyckPath, FindPosition, FindPosition2, FlawDyckPath, FreeDyckPath, Inv2MajII, Inv2Perm, IsPermutation, Istree, Maj2InvII, Maj2Perm, MatchingAvoidP, MatchingInsertion, MatchingList, MatchingNbpattern, MatchingSamepattern, MatchingSubseqN, PathFlaw, Patience_sort, Perm2Inv, Perm2Maj, PermAvoidP, PermAvoidPs, PermDistpattern, PermDistpatterns, PermExceed, PermInsertion, PermList, PermMaj, PermMajPos, PermNbpattern, PermNbpatternT, PermNbpatterns, PermNbpatternsT, PermPosition, PermSamepattern, PermSubseqN, RNASS, RNASSN, belong, double_root_tree, sequence_to_tree, tree_to_seq_num, tree_to_sequence（32） 函数PermList用来枚举特定长度的排列。函数调用格式如下>PermList(3);显示结果：3, 2, 1, 2, 3, 1, 2, 1, 3, 3, 1, 2, 1, 3, 2, 1, 2, 3（33） 函数PermInsertion返回把一个元素插入排列得到的所有排列。调用格式>PermInsertion(3,1,2,4);显示结果：4, 3, 1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, 4（34） 函数PermPosition返回特定元素在排列中的位置。调用格式>PermPosition(3,1,3,2);显示结果：2（35） 函数PermSubseqN列举排列中所有特定长度的子序列。调用格式>PermSubseqN(1,3,4,2, 3);显示结果：1, 3, 4, 1, 3, 2, 1, 4, 2, 3, 4, 2（36） 函数Patience_sort以贪婪策略寻找最长递增子序列。调用格式>Patience_sort(2,3,1,6,4,5,6);显示结果：2，3，4，5（37） 函数IsPermutation判断给定序列是否排列。调用格式>IsPermutation(2,3,2,1,4);显示结果：It is not a permutation.（38） 模式排列理论背景：下面以枚举不含特定模式的排列函数PermAvoidP和PermAvoidPs说明>PermAvoidP(3,1,3,2); 显示结果如下 >PermAvoidPs(4,1,2,3,1,3,2,3,1,2); 显示结果如下 函数PermSamepatternt判断两个模式是否相同。调用格式>PermSamepattern(1,3,2,4,7,6);显示结果：true函数PermNbpattern返回单个模式出现在序列中的次数。调用格式>PermNbpattern(4,2,1,3,1,2);显示结果：2函数PermNbpatterns返回多个模式出现在序列中的次数。调用格式>PermNbpatterns(4,2,1,3,1,2,2,1);显示结果：2，4函数PermNbpatternT列举含有单个模式特定个数的排列。调用格式>PermNbpatternT(4,1,2,1);显示结果：3, 4, 2, 1, 4, 2, 3, 1, 4, 3, 1, 2函数PermNbpatternsT列举含有多个模式特定个数的排列。调用格式>PermNbpatternsT(4,1,2,3,1,2,1,1);显示结果：4, 2, 3, 1函数PermDistPattern列举对称群中元素及所含特定单个模式次数。调用格式>PermDistpattern(3,2,1);显示结果： 3, 2, 1, 3 2, 3, 1, 2 2, 1, 3, 1 3, 1, 2, 2 1, 3, 2, 1 1, 2, 3, 0函数PermDistPatterns列举对称群中元素及所含特定多个模式次数。调用格式>PermDistpatterns(3, 1, 2, 2, 3, 1);显示结果： 3, 2, 1, 0, 0 2, 3, 1, 1, 1 2, 1, 3, 2, 0 3, 1, 2, 1, 0 1, 3, 2, 2, 0 1, 2, 3, 3, 0（39） 排列统计量相关函数理论背景： 调用格式>Perm2Inv(7,8,4,2,6,9,1,3,5);显示结果：0, 0, 2, 3, 2, 0, 6, 5, 4调用格式>Inv2Perm(0,0,2,3,2,0,6,5,4);显示结果：7, 8, 4, 2, 6, 9, 1, 3, 5调用格式>PermExceed(3,2,5,4,1);显示结果：2调用格式>Perm2Maj(7,8,4,2,6,9,1,3,5);显示结果：0, 1, 0, 2, 0, 1, 3, 3, 1调用格式>Maj2Perm(0,1,0,2,0,1,3,3,1);显示结果：7, 8, 4, 2, 6, 9, 1, 3, 5调用格式>Inv2MajII(4,4,2,3,4,1,3,2,3);显示结果：3, 2, 1, 4, 4, 4, 3, 2, 3调用格式>Maj2InvII(3, 2, 1, 4, 4, 4, 3, 2, 3);显示结果：4, 4, 2, 3, 4, 1, 3, 2, 3（310） 函数FreeDyckPath理论背景：调用格式>FreeDyckPath(1);显示结果：调用格式>DyckPath(2);显示结果：调用格式>FlawDyckPath(2,1);显示结果：（311） 匹配相关函数背景：函数MatchingList列举所有特定长度的匹配。调用格式>MatchingList(2);显示结果：1, 2, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2调用格式>MatchingNbpattern(1,2,2,3,1,4,4,3,1,2,1);显示结果：5调用格式>MatchingAvoidP(3,1,2,3,1,2);显示结果：1, 2, 3, 3, 2, 1, 1, 2, 3, 2, 3, 1, 1, 2, 3, 2, 1, 3, 1, 2, 2, 3, 3, 1, 1, 2, 2, 3, 1, 3, 1, 2, 2, 1, 3, 3, 1, 2, 1, 3, 3, 2, 1, 2, 1, 3, 2, 3, 1, 2, 1, 2, 3, 3, 1, 1, 2, 3, 3, 2, 1, 1, 2, 3, 2, 3, 1, 1, 2, 2, 3, 3（312） 函数RNASSN列举特定基序列的所有RNA二级结构。调用格式>RNASSN(3);显示结果：1, 3, 2, 1, 3, 2（313） 函数DOtoDif和DiftoDO相关理论背景：调用格式>DOtoDif(45,37,33,31,25,23,15,11,5,3,1);显示结果：76，60，38，27，19，8，1调用格式>DiftoDO(3,11,17,28);显示结果：23，17，9，7，3（314） 标号树函数相关理论背景：调用格式>tree_to_sequence*(Array(8, 6, 5, 4, 2, 3, 1, 3, 4, 4, 7, 3, 7, 7), 8);显示结果：3,4,4,7,3,7result_seq调用格式>sequence_to_tree(3, 4, 4, 7, 3, 7, 8);显示结果： 8 6 5 4 2 3 1 3 4 4 7 3 7 7T_edges函数DRT_TreeToFunction把双根树映射成函数。调用格式>DRT_TreeToFunction(3,3,3,3,8,8,8,8,2,1,4,9,9,5,6,7,8,3);显示结果：3, 3, 9, 3, 8, 8, 8, 3, 8函数DRT_FunctionToTree把函数映射成双根树。调用格式>DRT_FunctionToTree（3, 3, 9, 3, 8, 8, 8, 3, 8，9）;显示结果：（4） CPQSq-级数程序库（41） 调用软件包> with(CPQS);显示结果如下Bressouddis2supdis, Bressoudsupdis2dis, Durfee1to3, Durfee3to1, Franklin, Frobenius2, Partitionlod, Sylvesterdis2odd, Sylvesterodd2dis, qconjugate, qeuler, qfrobenius（42） 函数Sylvesterdis2odd和Sylvesterodd2dis说明，这是Sylvester映射的两个函数。函数Sylvesterdis2odd将一个各部分互不相同的分拆变成各部分为奇数的分拆。> Sylvesterdis2odd(11, 10, 78, 5, 4, 1); 显示结果如下 > Sylvesterdis2odd(11, 10, 7, 5, 4, 1); 显示结果如下 函数Sylvesterodd2dis将一个各部分为奇数的分拆变成各部分互不相同的分拆。> Sylvesterodd2dis(11, 7, 7, 5, 5, 3); 显示结果如下 （43） 函数Partitionlod是生成各种不同条件的分拆，其调用格式为Partitionlod(n,k,distinct,odd)，参数说明如下：举例调用格式如下 >Partitionlod(6, 5, 1, 0); 显示结果如下 （44） 函数qfrobenius和Frobenius2是用来演示Corteel-Lovejoy映射的。其具体背景如下：调用格式>qfrobenius(5, 3, 3, 3, 1, 0, 1, 3, 4, 5, 4, 4, 1, 1, 1, 1, 2, 3, 4, 5, 6);显示结果如下2, 2, 7, 2, 7, 1, 3, 2, 1调用格式>Frobenius2(2, 2, 7, 2, 7, 1, 3, 2, 1);显示结果如下5, 3, 3, 3, 1, 0, 1, 3, 4, 5, 4, 4, 1, 1, 1, 1, 2, 3, 4, 5, 6（45） 函数qeuler理论背景：调用格式>qeuler(4, 2, 1);显示结果如下 （46） Bressoud映射两函数理论背景：调用格式>Bressoudsupdis2dis（14, 11, 6, 4, 1）；显示结果如下14, 8, 7, 6, 1调用格式>Bressouddis2supdis(14, 8, 7, 6, 1)；显示结果如下14, 11, 6, 4, 1（47） Franklin函数理论背景：调用格式>Franklin(5，2)；显示结果如下4,2,1（48） 函数Durfee1to3、Durfee3to1和qconjugate理论背景：调用格式>Durfee3to1(4, 4, 4, 4, 5, 3, 1, 4, 3)；显示结果如下9, 7, 5, 4, 4, 3调用格式>Durfee1to3(9, 7, 5, 4, 4, 3)；显示结果如下4, 4, 4, 4, 5, 3, 1, 4, 3调用格式>qconjugate(9, 7, 5, 4, 4, 3)；显示结果如下6, 6, 6, 5, 3, 2, 2, 1, 1（5） PAPM概率方法应用程序库（51） 调用软件包> with(PAPM);显示结果如下Color, Firstpass, Hgame, Hyper, RandomCut, Secondpass, Thirdpass, Ylocal, colorable, contexpectation, contvariation, csort, discexpectation, discvariation, quicksort, sapp（52） 期望和方差相关理论背景：调用格式>contexpectation(1/sqrt(2*Pi)*exp(-x2/2)；显示结果如下0调用格式>contvariation(exp(-1/2*x2)/sqrt(2*Pi)；显示结果如下1调用格式>discexpectation(exp(-1)/i!)；显示结果如下1调用格式>discvariation(exp(-1)/i!)；显示结果如下1（53） 序列排序相关函数理论背景：调用格式>quicksort(29,32,18,49,512)；显示结果如下18, 29, 32, 49, 512调用格式>csort(29,32,18,49,512)；显示结果如下18, 29, 32, 49, 512（54） 函数Ylocal根据图的关联结构和特定顺序改变顶点状态。调用格式>with(networks)；>Ylocal(cycle(4),1,2,4,3,4,1,0,0,1)；显示结果如下0, 1, 0, 1（55） 下面我们以简单交错路求解函数sapp为例进行说明。函数sapp在交错路存在的条件下返回一个顶点序列。> sapp(0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1); 显示结果如下 下面看一个交错路不存在的例子> sapp(0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0);显示结果 （6） EVST极值集合论程序库（61） 调用软件包> with(EVST);显示结果如下（62） 函数shade和shadow理论背景：调用格式>shade(5,2,1,2,2,5)；显示结果如下1, 2, 3, 1, 2, 4, 1, 2, 5, 2, 3, 5, 2, 4, 5调用格式>shadow(5, 3, 1, 2, 5, 2, 4, 3)；显示结果如下1, 2, 1, 5, 2, 3, 2, 4, 2, 5, 3, 4（63） 函数MatchToFirst理论背景：调用格式>MatchToFirst(4, 1)；显示结果如下 1, 1, 2 2, 2, 3 3, 1, 3 4, 1, 4 （64） 下面我们以布尔代数分解的两个函数schd和symchain进行说明。函数schd将布尔代数分解成互不包含的链的并。> schd(4); 显示结果如下 函数symchain给出过某一特定子集的对称链。>symchain(7, 3, 4, 7); 显示结果如下