tailieunhanh - Báo cáo toán học: "On the diagram of Schr¨der permutations o Astrid Reifegerste"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On the diagram of Schr¨der permutations o Astrid Reifegerste | On the diagram of Schroder permutations Astrid Reifegerste Institut fur Mathematik Universitat Hannover Welfengarten 1 30167 Hannover Germany reifegerste@ Submitted Oct 11 2002 Accepted Jan 13 2003 Published Jan 22 2003 MR Subject Classifications 05A05 05A15 Abstract. Egge and Mansour have recently studied permutations which avoid 1243 and 2143 regarding the occurrence of certain additional patterns. Some of the open questions related to their work can easily be answered by using permutation diagrams. As for 132-avoiding permutations the diagram approach gives insights into the structure of 1243 2143 -avoiding permutations that yield simple proofs for some enumerative results concerning forbidden patterns in such permutations. 1 Introduction Let Sn be the set of all permutations of 1 . n . Given a permutation n n1 nn E Sn and a permutation T T1 Tk E Sk we say that n contains the pattern T if there is a sequence 1 i1 i2 . ik n such that the elements nir ni2 nik are in the same relative order as T1 T2 Tk. Otherwise n avoids the pattern T or alternatively n is T-avoiding. The set of T-avoiding permutations in Sn is denoted by Sn t . For an arbitrary finite collection T of patterns we write Sn T to denote the permutations of 1 . n which avoid each pattern in T. Egge and Mansour 2 studied permutations which avoid both 1243 and 2143. This work was motivated by the parallels to 132-avoiding permutations. In 6 Lem. 2 and Cor. 9 it was shown that the number of elements of Sn 1243 2143 is counted by the n 1 st Schroder number rn 1. The large Schroder numbers may be defined by n 1 ro 1 rn Vn 1 rirn 1 i for n 1. i 0 For this reason the authors of 2 called the permutations which avoid 1243 and 2143 Schroder permutations we will do this as well. The reference to Schroder numbers may the electronic journal of combinatorics 9 2 2003 R8 1 be somewhat inexact because there are ten inequivalent pairs T1 T2 E S4 for which Sn T1 t2 rn-1 see 6 Theo. 3 . However it is