置换群上的组合结构及其应用

A permutation group is a group whose elements are permutations of a given finite set and whose group operation is composition of permutations. In addition to algebric structrues, there are many combinatorial structures on a permutation group. In recent years, the study of permutation patterns is a thriving area of combinatorics that relates to many other areas of mathematics, including graph theory, enumerative combinatorics,the theory of automata and languages,and bioinformatics.For a permutation A written in one-line notation, we say that it contains a pattern p if it has a subword q which is order-isomorphic to p,otherwise, we say that A avoids p. By order-isomorphic we mean that the usual order on the integers is the same for both sequences. For example,the permutation 124635 contains the pattern 132 by noting that 263 is order-isomorphic to 132,but 124635 is 321-avoiding. There are two basic problems in counting occurrences of patterns. They are the avoidance problem and the counting problem. The former deals with finding the number of permutations with no occurrence of a given pattern, whereas the latter deals with counting permutations with a prescribed number of occurrences of a given pattern. Many combinatorial questions may be considered in a framework of permutation patterns. Permutation patterns has proved to be a useful language in a variety of seemingly unrelated problems,from theory of Kazhdan-Lusztig polynomials,to Chebyshev polynomials, to rook polynomials for a rectangular board, to various sorting algorithms, sorting stacks and sortable permutations..In this project, by using generating function, generating tree and Riordan array methods, we shall study the following problems:(1) the enumeration of special class of pattern-avoiding permutations, such as the even permutations , involutions, and alternating permutations that avoid a particular pattern, (2) the enumeration of permutations with a prescribed number of occurrences of a given pattern. We also considered a number of cases when permutations have to avoid two or more patterns simultaneously. (3) the enumeration of certain class of permutations that contain some restricted patterns or generalized patterns.We will show how to use Young tableau to count the number of permutations which avoid a set of forbidden patterns and have a given number of inversions. We also show how to use ECO method to count pattern-avoiding permutations with a given number of copies of a given consecutive pattern. For every question, we shall find an explicit formula or generating function of enumerative sequence, and derive exhaustive generating algorithms for the enumerative objects by ECO method, and explore the relationship between the permutation patterns and some classical combinatorial objects.The goal here is to find connections between different kinds of combinatorial objects,in the form of bijections that send a set of statistics on one side to a set of statistics on the other.

一个有限集合上的若干置换关于复合运算构成的群叫做置换群。置换群上除代数结构外有丰富的组合结构。置换模式问题是近十几年来组合数学研究的热点问题。把置换A看作序列时，若它有一个子序列q与置换p序同构，就称A包含模式p，否则就说A不包含模式p。置换模式的基本问题是：在n元对称群中不包含某个模式的置换有多少？包含某个模式恰好r次的置换有多少?很多问题都能统一在置换模式的框架下来研究，置换模式也有广泛的应用。本项目用发生函数、生成树、Riordan矩阵等方法研究以下问题：n元对称群中不包含某些模式的特定置换（对合置换、交错置换、偶置换）的计数问题；n元对称群中包含某个模式恰好等于给定次数的置换的计数问题；当模式有限定条件时一定范围内置换的计数问题。我们将给出所讨论问题的计数公式或者计数序列的发生函数，用ECO方法给出生成满足一定条件的所有置换的算法，给出置换模式问题与经典组合问题之间的对应关系。

置换模式问题是近年来组合数学研究的热点问题之一。很多组合问题都能统一在置换模式的框架下来研究。置换模式问题与组合数、多项式序列、组合矩阵理论都有着紧密联系。 本项目用发生函数和Riordan矩阵的方法， 主要研究了Sheffer序列的递推关系，Schroder矩阵与Delannoy 矩阵的关系，Catalan 矩阵与反演关系，Bessel数与Bessel多项式，高阶Catalan 数的发生函数的Taylor展式等问题。其中Schroder矩阵、Delannoy 矩阵和Catalan 矩阵的应用为研究置换模式问题提供了一个很好的范例。 该项目的研究也为Riordan矩阵的应用提供了广阔的背景，为我们今后的工作打下了坚实的基础。