第1页共30页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共30页《组合数学机械化通用程序库软件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详细设计说明书d)软件设计文档国家标准GB8567-88第2页共30页第1页共30页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共30页二、功能介绍本软件共完成了六个通用程序库，重点实现了机器证明、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-Dyc...
