交错排列与集合分拆中有禁模式的研究

摘要

排列，集合分拆等组合结构中有禁模式的研究是组合数学研究中一个重要的研究课题，该方向的研究引起了国际上众多组合数学家的高度重视，包括Stanley，Zeilberger等.对于有禁排列的研究成果及研究现状可以参看Bóna和Kitaev的书.类似于普通的排列，Mansour开始着力于避免某种给定模式的交错排列的计数问题的研究.对于任意一个长度为3的给定模式σ∈S3，交错排列中避免σ的所有排列所组成的集合中元素个数为Catalan数.近来，Lewis考虑避免型长为4的给定模式的交错排列的计数问题.
　　对集合分拆中的有禁模式的研究引起了众多组合数学家的高度重视，包括Gessel，Klazar，Chen等.Zagier得到了由Stoimenow提出的避免左嵌套与右嵌套的完美匹配的生成函数.近来，Bousquet-Mélou et al.证明了避免左嵌套与右嵌套的完美匹配与无标号的(2+2)-free的偏序集，特殊有禁排列以及上三角非负矩阵具有相同的计数，并建立了它们之间的对应关系.Chen等人研究了避免相邻分布的不完全匹配，同时避免相邻分布与左嵌套的不完全匹配，以及避免右嵌套的集合分拆，得到了它们的生成函数.
　　本文主要致力于研究交错排列与集合分拆中有禁模式的计数问题，共分为四章.
　　第一章给出了交错排列以及集合分拆中有禁模式的计数问题的历史发展和研究现状及其一些基础知识.本章是后面几章的基础.
　　第二章，我们建立了长度为2n的避免4123的下降-上升交错排列所组成的集合和型为（n，n，n）的标准Young表所组成的集合之间的一一对应关系，通过Yamanouchi字建立了长度为2n-1的避免4123的下降-上升的交错排列所组成的集合.而且，我们证明长度为2n+1的避免4123的上升-下降的交错排列所组成的集合与型为（n+1，n，n-1）的标准Young表所组成的集合之间存在一一对应关系，并且证明了长度为2n的避免4123的上升-下降交错排列所组成的集合与型为（n+2，n，n-2）的平移的标准Young表之间存在一一对应关系.
　　第三章，我们研究了避免右相交的集合分拆的计数问题，建立了同时避免2-右相交与右嵌套的不完全匹配和避免右相交的集合分拆之间的一一对应关系，从而推导出避免右相交的集合分拆的生成函数.
　　第四章，给出了精简的总结概括及以后的展望.

目录

摘要

1 绪论

1．1 基本概念

1．1．1 交错排列与Wilf-等价

1．1．2 杨图与标准杨表

1．1．3 集合分拆

1．2 问题的研究背景与研究意义

1．2．1 交错排列的研究背景与研究意义

1．2．2 集合分拆中有禁模式的研究背景与研究意义

1．3 本文的主要结构

2 交错排列中的长度为4的有禁模式与标准杨表

2．1 避免4123的下降-上升的交错排列

2．1．1 基本定义及相关引理

2．1．2 构造——对应关系

2．2 避免4123的上升-下降的交错排列

3 避免右相交的分拆

3．1 本章概述

3．2 避免2-右相交和右嵌套的不完全匹配

3．3 避免右相交的分拆

4 研究展望

参考文献

在学期间的研究成果及发表的论文

致谢

声明

浙江师范大学学位论文诚信承诺书