Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Distribution of crossings, nestings and alignments of two edges in matchings and partitions. | Distribution of crossings nestings and alignments of two edges in matchings and partitions Anisse Kasraoui and Jiang Zeng Institut Camille Jordan Universite Claude Bernard Lyon I F-69622 Villeurbanne Cedex France anisse@ zeng@ Submitted Nov 11 2005 Accepted Mar 30 2006 Published Apr 4 2006 Mathematics Subject Classifications 05A18 05A15 05A30 Abstract We construct an involution on set partitions which keeps track of the numbers of crossings nestings and alignments of two edges. We derive then the symmetric distribution of the numbers of crossings and nestings in partitions which generalizes a recent result of Klazar and Noy in perfect matchings. By factorizing our involution through bijections between set partitions and some path diagrams we obtain the continued fraction expansions of the corresponding ordinary generating functions. 1 Introduction A partition of n 1 2 ng is a collection of disjoint nonempty subsets of n called blocks whose union is n . A perfect matching of 2n is a partition of 2n in n two-element blocks. The set of partitions resp. matchings of n will be denoted by nn resp. Mn . A standard way of writing a partition with k blocks is Bl B2 Bk where the blocks are ordered in the increasing order of their minimum elements and within each block the elements are written in the numerical order. It is convenient to identify a partition of n with a partition graph on the vertex set n such that there is an edge joining i and j if and only if i and j are consecutive elements in a same block. We note such an edge e as a pair i j with i j and say that i is the left-hand endpoint of e and j is the right-hand endpoint of e. A singleton is the element of a block which has only one element so a singleton corresponds to an isolated vertex in the graph. Conversely a graph on the vertex set n is a partition graph if and only if each vertex is the left-hand resp. right-hand endpoint of at most one edge. By convention the vertices 1
