数学机械化程序文档-用户手册.doc

7组合数学机械化通用程序库软件用户手册一、 引言本系统的名称为“组合数学机械化通用程序库软件”，是由南开大学研发的。本软件的首批用户是南开大学组合数学中心的老师和研究生。本用户手册是关于组合数学机械化通用程序库软件的帮助性文件，目的在于描述软件的安装和使用，重点在于阐述程序库中主要函数的理论背景、调用格式及输出结果。预期参考人员包括用户、测试人员、开发人员、项目管理者和其他质量管理人员。 本用户手册中涉及到如下专用术语和外文单词缩写形式：a) 组合恒等式机器证明：zeilberger在gosper算法的基础上提出了一套证明组合恒等式的系统方法， 后来又提出了wz-对的方法，不仅能证明许多已有的恒等式，还能发现一些新的恒等式。其主要思想是证明组合恒等式的两边满足相同的递推关系，然后验证等式两边在初值情况下相等。b) 对称函数理论：对称函数理论是代数组合学中的一个重要研究领域，它主要研究对称群和对称多项式的代数性质和组合性质，在数学的其他分支和数学物理中有广阔的应用，是一个受到广泛关注的研究方向。c) 组合双射理论：组合双射是指在同样数量的两个对象之间的对应。该理论是组合计数理论的一个重要研究方向，有助于理解各种组合对象之间的密切联系。d) q-级数：主要内容为超几何级数的q-模拟。利用组合对应、算子理论、基本变换、反演、自动证明等方法研究q-恒等式和q-级数的性质。e) apci：autoproof of combinatorics 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) 组合数学机械化通用程序库软件技术总结报告b) 组合数学机械化通用程序库软件概要设计说明书c) 组合数学机械化通用程序库软件详细设计说明书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则表示已正确安装软件。五、 软件使用本系统共包括六个程序库，下面将分别从每个程序库中举一个例子进行说明如何使用。（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函数为例进行说明，该函数给出有理函数的gp分解，该分解是唯一的。首先我们先引入一个有理函数 t:=binomial(2*n-3,n)/4n;显示结果如下然后调用函数gosper2 gosper2(t);显示结果如下 备注：关于gosper2函数的理论背景参考技术报告第10页。（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） 调用函数mat2oscil将一个匹配变成振荡杨表mat2oscil(1,4,2,6,3,5); 显示结果如下 然后调用函数oscil2mat将振荡杨表变回匹配oscil2mat(, 1, 1, 1, 2, 1, 2, 1, );显示结果如下 备注：关于mat2oscil和oscil2mat函数的理论背景参考技术报告第48页。（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） 下面以枚举不含特定模式的排列函数permavoidp和permavoidps说明permavoidp(3,1,3,2); 显示结果如下 permavoidps(4,1,2,3,1,3,2,3,1,2); 显示结果如下 备注：关于permavoidp和permavoidps函数的理论背景参考技术报告第58页。（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); 显示结果如下 备注：关于sylvesterdis2odd和sylvesterodd2dis函数的理论背景参考技术报告第17页。（5） evst极值集合论程序库（51） 调用软件包 with(evst);显示结果如下bondy, schd, shade, shift1, symchain（52） 下面我们以布尔代数分解的两个函数schd和symchain进行说明。函数schd将布尔代数分解成互不包含的链的并。 schd(4); 显示结果如下 函数symchain给出过某一特定子集的对称链。symchain(7, 3, 4, 7); 显示结果如下 备注：关于schd和symchain函数的理论背景参考技术报告第84页。（6） papm概率方法应用程序库（61） 调用软件包 with(papm);显示结果如下color, firstpass, hgame, hyper, randomcut, secondpass, thirdpass, ylocal, colorable, con