论文部分内容阅读
有禁排列的概念是1968年由Knuth在研究栈排序时提出的。Simion和Schmidt首先系统地研究了有禁排列并提出了“模式”这一概念。之后，有禁模式的概念被推广到许多其它组合结构，如上升序列，交错排列，集合划分，有序集合划分等。结果表明，有禁模式的研究与许多其它问题密切相关，包括Kazhdan-Lusztig理论，Schubert簇的奇异性，Ferrers棋盘上的车多项式和多种排序算法。 本文主要研究有禁交错排列和有禁有序集合划分中的计数问题。我们解决了Lewis提出的两个关于避免4长模式的交错排列Wilf-等价的猜想。令[n]表示集合{1，2，…，n}。我们回答了Godbole，Goyt，Herdan和Pudwell提出的关于计数避免123模式且含有k块的[n]上有序集合划分的问题。同时，我们解决了Godbole等人提出的关于避免123模式并且每一块大小都是2的[2n]上有序集合划分数的递推关系的猜想。此外，我们对有禁有序集合划分的概念进行了推广。我们考虑了避免模式是一个有序集合划分，而并非排列的有序集合划分的计数问题，并且给出了避免模式大小等于2或3的有序集合划分的计数公式。 本文共分为四章。在第一章，我们回顾了一些有禁交错排列和有禁有序集合划分的背景知识，并介绍了本文的主要结果。 在第二章，我们主要研究了避免一个4长模式的交错排列的计数问题。若一个排列π=π1π2…πn满足π1＜π2＞π3＜π4＞…，我们就称它为一个z长的交错排列。令An为所有z长的交错排列构成的集合，令An(σ)为所有避免σ模式的n长交错排列构成的集合。最近，Lewis用生成树的方法对A2n(1234)，A2n(2143)和A2n+1(2143)进行了计数。他提出了一些关于避免4长模式的交错排列的Wilf-等价的猜想。其中一些猜想已被Bóna，Xu和Yan解决。本章中，我们通过构造生成树，解决了Lewis的两个猜想:|A2n+1(1243)|=|A2n+1(2143)|和|A2n(4312)|=|A2n(1234)[。 在第三章，我们主要研究了避免一个3长模式的有序集合划分的计数问题。对于一个[n]上的集合划分，若对它的块赋予一个线性序，它就变成一个[n]上的有序集合划分。令(GJ)n，k为所有含有k块的[n]上有序集合划分构成的集合，令(GJ)n，k（σ)为(GJ)n，k中所有避免σ模式的有序集合划分构成的集合。对于任意一个3长排列σ，Godbole，Goyt，Herdan和Pudwell给出了避免σ模式的含有3块和含有n-1块的[n]上有序集合划分的计数公式。他们还得到对于任意一个3长排列σ，都有|(GJ)n，k(σ)|=|(GJ)n，k(123)|。此外，他们提出对(GJ)n，k(123)进行计数的问题并且猜想避免123模式且每一块大小都是2的[2n]上有序集合划分数满足一个2阶线性递推关系。为计数(GJ)n，k(123)，我们建立了|(GJ)n，k(123)|与避免123模式的含有d个下降位的[n]上排列个数en，d的一个联系。基于这个联系，利用Barnabei，Bonetti和Silimbani给出的en,d的双变量生成函数，我们得到了|(GJ)n，k(123)|的双变量生成函数。同时，我们通过求得避免123模式并且每一块大小都是2的[2 n]上有序集合划分数的生成函数，解决了Godbole等人提出的猜想。 在第四章，我们推广了Godbole等人提出的有禁有序集合划分的概念。我们考虑了避免模式是一个有序集合划分，而并非排列的有序集合划分的计数问题。我们称上述模式为广义模式。给定一个有序集合划分σ，令(GJ)n，k（σ)为(GJ)n,k中所有避免σ广义模式的的有序集合划分构成的集合。对于任意一个大小为2或3的有序集合划分σ，我们给出了|(GJ)n，k(σ)|的明确公式。此外，我们建立了一个(GJ)n,k(13/2)到(GJ)n，k(12/3)的双射。