TAILIEUCHUNG - Báo cáo toán học: "Enumeration of Pin-Permutations"

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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Enumeration of Pin-Permutations. | Enumeration of Pin-Permutations Frederique Bassino LIPN UMR 7030 Universite Paris 13 and CNRS 99 avenue B. Clement 93430 Villetaneuse France. Mathilde Bouvel LaBRI UMR 5800 Universite de Bordeaux and CNRS 351 cours de la Liberation 33405 Talence cedex France. Dominique Rossin LIX UMR 7161 Ecole Polytechnique and CNRS 91128 Palaiseau France. Submitted Dec 19 2008 Accepted Feb 28 2011 Published Mar 11 2011 Mathematics Subject Classification 05A15 05A05 Abstract In this paper we study the class of pin-permutations that is to say of permutations having a pin representation. This class has been recently introduced in 16 where it is used to find properties algebraicity of the generating function decidability of membership of classes of permutations depending on the simple permutations this class contains. We give a recursive characterization of the substitution decomposition trees of pin-permutations which allows us to compute the generating function of this class and consequently to prove as it is conjectured in 18 the rationality of this generating function. Moreover we show that the basis of the pin-permutation class is infinite. 1 Introduction In the combinatorial study of permutations simple permutations have been the core objects of many recent works 2 3 15 16 17 18 20 . These simple permutations are the building blocks on which all permutations are built through their substitution decomposition. Recently substitution decomposition of permutations has also been used to exhibit relations between the basis of permutation classes and the simple permutations This work was completed with the support of the ANR projects GAMMA and MAGNUM ANR-2010-BlAN-0204 . THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P57 1 this class contains 2 16 17 18 . Similar decompositions for other objects have been widely used in the literature for relations 25 26 32 34 for graphs 13 36 or in a variety of other fields 19 22 35 . In the algorithmic field the substitution .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học