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

1、PAGE .PAGE 30PAGE ：.；PAGE 30用户手册引言本系统的称号为“组合数学机械化通用程序库软件V1.0，是由南开大学研发的。本软件的首批用户是南开大学组合数学中心的教师和研讨生。本用户手册是关于组合数学机械化通用程序库软件的协助 性文件，目的在于描画软件的安装和运用，重点在于论述程序库中主要函数的实际背景、调用格式及输出结果。预期参考人员包括用户、测试人员、开发人员、工程管理者和其他质量管理人员。 本用户手册中涉及到如下公用术语和外文单词缩写方式：组合恒等式机器证明：Zeilberger在Gosper算法的根底上提出了一套证明组合恒等式的系统方法，后来又提出了WZ-对的方法，

2、不仅能证明许多已有的恒等式，还能发现一些新的恒等式。其主要思想是证明组合恒等式的两边满足一样的递推关系，然后验证等式两边在初值情况下相等。对称函数实际：对称函数实际是代数组合学中的一个重要研讨领域，它主要研讨对称群和对称多项式的代数性质和组合性质，在数学的其他分支和数学物理中有宽广的运用，是一个遭到广泛关注的研讨方向。组合双射实际：组合双射是指在同样数量的两个对象之间的对应。该实际是组合计数实际的一个重要研讨方向，有助于了解各种组合对象之间的亲密联络。q-级数：主要内容为超几何级数的q-模拟。利用组合对应、算子实际、根本变换、反演、自动证明等方法研讨q-恒等式和q-级数的性质。APCI：Aut

3、oproof of Combinatorical IdentitiesSYMF：Symmetric FunctionsEPPT：Enuemrating Paths, Permutations and TreesCPQS：Computation Package for q-SeriesEVST：Extremal Value of Set TheoryPAPM：Package for Applications in Probability Method相关参考资料包括：组合数学机械化通用程序库软件V1.0技术总结报告组合数学机械化通用程序库软件V1.0概要设计阐明书组合数学机械化通用程序库软件V1

4、.0详细设计阐明书 HYPERLINK bbs.scmlife/thread-8686-1-1.html t _blank 软件设计文档国家规范GB8567-88功能引见本软件共完成了六个通用程序库，重点实现了机器证明、q-级数、对称函数和组合计数等四个领域的常用函数包。这些程序库包括了机器证明、q-级数、对称函数、陈列和路及树、集合论和概率方法等领域中常用的根本函数和过程。在组合恒等式机器证明方面，我们实现了Sister Celine算法求正那么超几何项递归关系、算子消元法、q-Zeilberger算法、Gosper算法、素性判别的随机算法、正交多项式的关联络数求解、求多项式解的多项式算法等

5、内容。其中Gosper算法和q-Zeilberger算法的算法实现尤为重要。在q-级数方面，我们重点实现了有关q-级数等式方面的组合双射算法。主要包括Sylvester 映射、特定分拆生成、Corteel-Lovejoy 映射、Euler 定理的组合证明、Bressoud 映射、Franklin 对合、Durfee 方块和共轭分拆。这些组合双射算法是该领域的根本算法，为进一步构造双射提供了强大的工具。在对称函数方面，我们实现了该领域常用的一些函数和过程，包括置换的轮换分解、格陈列生成、分拆与杨表表示、分拆与斜分拆的秩、寻觅最长递增子序列、RSK 算法、陈列的 Growth diagram生成、

6、犹疑杨表和集合划分之间的对应、匹配和 Oscillating tableaux 之间的对应等根本组合对象生成算法和根本组合算法。其中，RSK算法是对称函数的中心算法，具有广泛的运用，它的软件实现将大大有助于我们研讨对称函数。在组合计数方面，我们重点研讨了有关路、陈列和树的程序实现。陈列中的根本函数包括PermInsertion、PermPosition、PermList、PermSubseqN、IsPermutation等生成和判别函数。有禁方式的陈列是计算机科学中重要的组合构造。在这方面我们编写了PermSamepatternt、PermNbpattern、PermNbpatterns、Pe

7、rmNbpatternT、PermNbpatternsT、PermDistpattern、PermDistpatterns、PermAvoidP、PermAvoidPs等方式陈列生成函数。此外我们编写了陈列的根本统计量等生成函数。在路的算法实现方面，我们编写了Dyck 路、自在Dyck 路、有2k 个缺陷的n-Dyck 路的生成函数。匹配在生物信息学中有很多运用，我们实现了MatchingList、 MatchingNbpattern、MatchingAvoidP、RNASSN和RNA 二级构造等生成算法。在标号树方面，我们给出了标号树的序列表示和函数表示。在集合论方面，我们实现了具有特定性质

8、的集合的生成函数，包括列出包含某特定集合的子集的函数shade、列出包含于某特定子集的函数shadow、匹配布尔代数元素的函数matchtofirst、布尔代数对称链分解函数schd和寻觅特定对称链函数symchain和寻觅与集系有特殊性质的特定子集的函数Bondy。组合中的概率方法是经过设定概率空间，将某个存在性稳定转化为概率非零事件问题。在开发的程序库中，我们重点实现了离散随机变量和延续随机变量的期望和方差函数，快速排序算法和超图的二染色算法。这是概率方法中最经典的例子和最根本的算法。运转环境 硬件环境：Intel Pentium III 650 MHz、128M RAM、2G硬盘空间或更

9、高 操作系统：Windows 2000或Windows XP 支持软件：Maple 10安装方法 本系统共有三个安装文件combmech.lib、combmech.hdb和combmech.ind，假设它们位于E盘根目录下，安装步骤如下：翻开数学软件Maple 10。在Maple命令行内输入如下命令设定程序库途径 libname:=libname,E:;将程序库combmech.lib读入当前程序库途径readlib(E:combmech.lib);输入如下命令with(APCI);假设显示结果如下Gosper2, Gosper3, Polysolve, Primetest, Rrop, Tr

10、an, 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) ，那么显示为.软件运用本系统共包括六个程序库，下面将分别阐明每个程序库主要函数如何运用。APCI自动证明程序库调用软件包 with(APCI);显示结果如下Gosper2, Gosper3, Polysolve, Prim

11、etest, Rrop, Tran, cancel_operator, cceline, celine, celine1, re, sequence_to_tree, tree_to_sequenceGosper2和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函数的实际背景如下：

12、满足上述条件的多项式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);显示结果如下 函数celine和cce

13、line实际背景如下：下面以函数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)!);显示结果如下函数re实际算法阐明：运用该函数时需求运用软件包qsum9.mpl read:= E:qsum9.mpl;函数调用格式re(qhyperterm(0, , q, z, k), z);显示结果如下 The recurrence relation satisfies: 函数Tran功能阐明：此函数也需求软

14、件包qsum9.mpl的支持，函数调用格式 Tran(qhyperterm(a, b, c, q, z, k), z);显示结果如下The condition that the Transformation Formulas should comply with is: |c/q|Rrop(pochhammer(x,n);显示结果如下 we can get a,b,c,y 函数Polysolve实际背景函数调用格式Polysolve(N-1, n);显示结果如下 the solve of y(n) is: SYMF对称函数程序库调用软件包 with(SYMF);显示结果如下Bump, Bump

15、2, 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

16、, reducode, skewrank, srank, vacilla2pair函数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

17、, 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调用函数mat2oscil将一个匹配变成振荡杨表mat2oscil(1,4,2,6,3,5); 显示结果如下 然后调用函数oscil2mat将振荡杨表变回匹配oscil2mat(, 1, 1, 1, 2, 1, 2, 1, );显示结果如下 这两个函数的实际背景如下：函数RSKcorresp1和RSKcorres

18、p2实际背景：函数调用格式RSKcorresp1(5,7,1,3,2);显示结果如下 函数调用格式RSKcorresp2(5,7,1,3,2);显示结果：2函数growthdia实际背景：函数调用格式growthdia(3, 1, 2);显示结果： 函数longestisubs是用来求一个序列的极大递增子列。函数调用格式longestisubs(5, 6, 2, 1, 7, 4, 3, 9, 8);显示结果：分拆与斜分拆的秩相关函数实际背景：函数调用格式parrank(8, 6, 6, 4, 2);显示结果： 4函数调用格式skewrank(6, 6, 4, 2, 3, 2, 1);显示结果：

19、 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分拆与杨表相关函数实际背景：函数调用格式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);显示结果： 函数cano

20、nical给出置换的规范既约分解，其实际背景如下：函数调用格式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函数lattpermlist实际背景：函数调用格式lattpermlist(2, 1);显示结果：1,2,1 1,1,2EPPT路、陈列和树程序库调用软件包 with(EPPT);显示结果如下DOtoDif, DRT_FunctionToTree, DRT_TreeToFunction, D

21、iftoDO, DyckPath, FindPosition, FindPosition2, FlawDyckPath, FreeDyckPath, Inv2MajII, Inv2Perm, IsPermutation, Istree, Maj2InvII, Maj2Perm, MatchingAvoidP, MatchingInsertion, MatchingList, MatchingNbpattern, MatchingSamepattern, MatchingSubseqN, PathFlaw, Patience_sort, Perm2Inv, Perm2Maj, PermAvoid

22、P, 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

23、_sequence函数PermList用来枚举特定长度的陈列。函数调用格式如下PermList(3);显示结果：3, 2, 1, 2, 3, 1, 2, 1, 3, 3, 1, 2, 1, 3, 2, 1, 2, 3函数PermInsertion前往把一个元素插入陈列得到的一切陈列。调用格式PermInsertion(3,1,2,4);显示结果：4, 3, 1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, 4函数PermPosition前往特定元素在陈列中的位置。调用格式PermPosition(3,1,3,2);显示结果：2函数PermSubseqN列举陈列中一切

24、特定长度的子序列。调用格式PermSubseqN(1,3,4,2, 3);显示结果：1, 3, 4, 1, 3, 2, 1, 4, 2, 3, 4, 2函数Patience_sort以贪婪战略寻觅最长递增子序列。调用格式Patience_sort(2,3,1,6,4,5,6);显示结果：2，3，4，5函数IsPermutation判别给定序列能否陈列。调用格式IsPermutation(2,3,2,1,4);显示结果：It is not a permutation.方式陈列实际背景：下面以枚举不含特定方式的陈列函数PermAvoidP和PermAvoidPs阐明PermAvoidP(3,1,3

25、,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列举含有单个方式特定个数的陈列。

26、调用格式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函数PermDistPat

27、terns列举对称群中元素及所含特定多个方式次数。调用格式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陈列统计量相关函数实际背景： 调用格式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调用格式Perm

28、Exceed(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函数FreeDyckPath实际背景

29、：调用格式FreeDyckPath(1);显示结果：调用格式DyckPath(2);显示结果：调用格式FlawDyckPath(2,1);显示结果：匹配相关函数背景：函数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,

30、 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函数RNASSN列举特定基序列的一切RNA二级构造。调用格式RNASSN(3);显示结果：1, 3, 2, 1, 3, 2函数DOtoDif和DiftoDO相关实际背景：调用格式DOtoDif(45,37,33,31,25,23,15,11,5,3,1);显示

31、结果：76，60，38，27，19，8，1调用格式DiftoDO(3,11,17,28);显示结果：23，17，9，7，3标号树函数相关实际背景：调用格式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_TreeToF

32、unction(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_FunctionToTree3, 3, 9, 3, 8, 8, 8, 3, 8，9;显示结果：CPQSq-级数程序库调用软件包 with(CPQS);显示结果如下Bressouddis2supdis, Bressoudsupdis2dis, Durfee1to3, Durfee3to1, Franklin, Frobenius2, Partitionlod, Sylves

33、terdis2odd, Sylvesterodd2dis, qconjugate, qeuler, qfrobenius函数Sylvesterdis2odd和Sylvesterodd2dis阐明，这是Sylvester映射的两个函数。函数Sylvesterdis2odd将一个各部分互不一样的分拆变成各部分为奇数的分拆。 Sylvesterdis2odd(11, 10, 78, 5, 4, 1); 显示结果如下 Sylvesterdis2odd(11, 10, 7, 5, 4, 1); 显示结果如下 函数Sylvesterodd2dis将一个各部分为奇数的分拆变成各部分互不一样的分拆。 Sylv

34、esterodd2dis(11, 7, 7, 5, 5, 3); 显示结果如下 函数Partitionlod是生成各种不同条件的分拆，其调用格式为Partitionlod(n,k,distinct,odd)，参数阐明如下：举例调用格式如下 Partitionlod(6, 5, 1, 0); 显示结果如下 函数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,

35、 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函数qeuler实际背景：调用格式qeuler(4, 2, 1);显示结果如下 Bressoud映射两函数实际背景：调用格式Bressoudsupdis2dis14, 11, 6, 4, 1；显示结果如下14, 8, 7, 6, 1调用格式Bressouddis2supdis(14, 8, 7, 6, 1)；显示结果如下14, 11, 6, 4,

36、 1Franklin函数实际背景：调用格式Franklin(5，2)；显示结果如下4,2,1函数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, 1PAPM概率方法运用程序库调用软件包 with

37、(PAPM);显示结果如下Color, Firstpass, Hgame, Hyper, RandomCut, Secondpass, Thirdpass, Ylocal, colorable, contexpectation, contvariation, csort, discexpectation, discvariation, quicksort, sapp期望和方差相关实际背景：调用格式contexpectation(1/sqrt(2*Pi)*exp(-x2/2)；显示结果如下0调用格式contvariation(exp(-1/2*x2)/sqrt(2*Pi)；显示结果如下1调用格式discexpectation(exp(-1)/i!)；显示结果如下1调用格式discvar