极小置换和2-正则斜杨表

摘要

这篇论文的主要结果是关于极小置换的计数问题。称一个含有d个下降数的置换开是极小置换是指不存在包含在π中的模式τ，使得τ．含有d个下降数。极小置换来源于基因组重组问题。基因组重组是基因组改变基因排列顺序的生化过程，其中的基因组重组排序问题的主要目标是找到最短的重组操作序列，将一个基因组转变为另一个基因组。基因组重组操作包括复制、缺失、易位、倒位、和插入等。乔杜里、陈、米哈埃斯库和饶在中提出了全基因组复制-随机损失模型，在这种模型中，只考虑复制和损失这两种基因组重组操作类型。用组合的语言可以描述为：给定恒等置换12…n，复制任意长的一段连续子序列i，i+1，…，j，并将复制的这段子序列放至原子序列后面，此时的序列中有两段i，i+1…．，j；再随机去掉i i+1，…，j中的每一个数，使得剩余部分仍是一个置换。布沃尔和珀格证明了在全基因组复制．随机损失模型中，至多p个复制．随机损失操作可以得到的置换是一类模式避免置换，这类模式避免置换的基Bv就是由含2p个下降数的极小置换组成。
　　 令fd(n)表示长为n且有d下降数的极小置换的个数。布沃尔和珀格勒证明了极小置换可以由两类四长的模式避免刻划。根据这个刻划，他们得到了fn(2n)和fn-2(n)的计数公式。曼苏尔和严计算了fn+1(2n+1)的值。在这篇论文中，为了计算其它情况的极小置换的个数，我们引入2．正则斜杨表的概念，然后在给定上升集的极小置换集合与有固定形状的2-正则斜杨表之间构造了一个一一对应。通过计算斜杨表的雅克比-楚迪等式，我们得到了n长，且有d个下降数的极小置换的计数公式。特别地，关于有n+1个下降数，且2n+1长的极小置换，由RSK算法和克努斯等价条件，我们给出了其计数公式的一个组合证明。
　　 在第一章中，我们主要介绍了极小置换在基因学中的理论背景，即，基因组复制-随机损失模型，并介绍了模式避免的概念，从而极小置换是一类避免某些模式的排列的基。
　　 在第二章中，我们介绍了关于杨表的基本概念及其计数公式，以及我们在后面的工作中需要用到的RSK算法和克努斯等价条件，并定义了2-正则斜杨表的概念。在第三章中，我们先介绍了极小置换的计数问题的发展和一些已有结论。我们引入了2-正则斜杨表的概念，然后构造了有相同上升集的极小置换集合和有固定形状的2-正则斜杨表的双射。由斜杨表的计数公式：雅克比-楚迪等式，我们得到了由行列式表达的有固定下降数的极小置换的计数公式，并且给出了含n-3个下降数的n-长的极小置换的具体表达式。
　　 在第四章中，对含n+1个下降数，且2n+1长的极小置换，根据RSK算法和克努斯等价条件，我们给出了其计数公式的一个组合证明。事实上，我们给出了它的一个加细，得到了具有固定的上升序列的极小置换的个数。