416 research outputs found
Number of pop-stacked permutations
No full textThe number of pop-stacked permutations of [n] for n = 1 to 1000 (sequence A307030 in the OEIS) as well as a triangle of numbers giving the number of pop-stacked permutations of each length grouped by number of ascending runs up to n = 300
Enumerating permutations avoiding a pair of Babson-Steingrimsson patterns
No full textBabson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Subsequently, Claesson presented a complete solution for the number of permutations avoiding any single pattern of type (1, 2) or (2, 1). For eight of these twelve patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers. In the present paper we give a complete solution for the number of permutations avoiding a pair of patterns of type (1, 2) or (2, 1). We also conjecture the number of permutations avoiding the patterns in any set of three or more such patterns
Enumerating permutations avoiding a pair of BabsonSteingrímsson patterns
No full textAbstract. Babson and Steingrímsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Subsequently, Claesson presented a complete solution for the number of permutations avoiding any single pattern of type (1, 2) or (2, 1). For eight of these twelve patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers. In the present paper we give a complete solution for the number of permutations avoiding a pair of patterns of type (1, 2) or (2, 1). We also conjecture the number of permutations avoiding the patterns in any set of three or more such patterns. 1
Enumerating permutations avoiding a pair of Babson-Steingrimsson patterns
No full textBabson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Subsequently, Claesson presented a complete solution for the number of permutations avoiding any single pattern of type (1, 2) or (2, 1). For eight of these twelve patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers. In the present paper we give a complete solution for the number of permutations avoiding a pair of patterns of type (1, 2) or (2, 1). We also conjecture the number of permutations avoiding the patterns in any set of three or more such patterns
matchings, posets (extended abstract)
No full textWe show that there are matchings on points without, so called, left (neighbor) nestings. We also define a set of naturally labelled -free posets, and show that there are such posets on elements. Our work was inspired by Bousquet-Mélou, Claesson, Dukes and Kitaev [J. Combin. Theory Ser. A. 117 (2010) 884―909]. They gave bijections between four classes of combinatorial objects: matchings with no neighbor nestings (due to Stoimenow), unlabelled -free posets, permutations avoiding a specific pattern, and so called ascent sequences. We believe that certain statistics on our matchings and posets could generalize the work of Bousquet-Mélou et al. and we make a conjecture to that effect. We also identify natural subsets of matchings and posets that are equinumerous to the class of unlabeled -free posets. We give bijections that show the equivalence of (neighbor) restrictions on nesting arcs with (neighbor) restrictions on crossing arcs. These bijections are thought to be of independent interest. One of the bijections maps via certain upper-triangular integer matrices that have recently been studied by Dukes and Parviainen [Electron. J. Combin. 17 (2010) #R53].Nous montrons qu'il y a couplages sur points sans emboîtement (de voisins) à gauche. Nous définissons aussi un ensemble d'EPO (ensembles partiellement ordonnés) sans motif naturellement étiquetés, et montrons qu'il y a tels EPO sur éléments. Notre travail a été inspiré par Bousquet-Mélou, Claesson, Dukes et Kitaev [J. Combin. Theory Ser. A. 117 (2010) 884―909]. Ces auteurs donnent des bijections entre quatre classes d'objets combinatoires: couplages sans emboîtement de voisins (dû à Stoimenow), EPO sans motif non étiquetés, permutations évitant un certain motif, et des objets appelés suites à montées. Nous pensons que certaines statistiques sur nos couplages et nos EPO pourraient généraliser le travail de Bousquet-Mélou et al. et nous proposons une conjecture à ce sujet. Nous identifions aussi des sous-ensembles naturels de couplages et d'EPO qui sont énumérés par la même séquence que la classe des EPO sans motif non étiquetés. Nous donnons des bijections qui démontrent l'équivalence entre les restrictions sur les emboîtements (d'arcs voisins) et les restrictions sur les croisements (d'arcs voisins). Nous pensons que ces bijections présentent un intérêt propre. L'une de ces bijections passe par certaines matrices triangulaires supérieures à coefficients entiers qui ont été récemment étudiées par Dukes et Parviainen [Electron. J. Combin. 17 (2010) #R53]
Pattern avoidance in partial permutations
No full textMotivated by the concept of partial words, we introduce an analogous concept of partial permutations. A partial permutation of length n with k holes is a sequence of symbols in which each of the symbols from the set {1,2,...,n-k} appears exactly once, while the remaining k symbols of are "holes". We introduce pattern-avoidance in partial permutations and prove that most of the previous results on Wilf equivalence of permutation patterns can be extended to partial permutations with an arbitrary number of holes. We also show that Baxter permutations of a given length k correspond to a Wilf-type equivalence class with respect to partial permutations with (k-2) holes. Lastly, we enumerate the partial permutations of length n with k holes avoiding a given pattern of length at most four, for each n >= k >= 1
n! matchings, n! posets
No full textWe show that there are matchings on points without, so called, left (neighbor) nestings. We also define a set of naturally labeled -free posets, and show that there are such posets on elements. Our work was inspired by Bousquet-M\'elou, Claesson, Dukes and Kitaev [J. Combin. Theory Ser. A. 117 (2010) 884--909]. They gave bijections between four classes of combinatorial objects: matchings with no neighbor nestings (due to Stoimenow), unlabeled -free posets, permutations avoiding a specific pattern, and so called ascent sequences. We believe that certain statistics on our matchings and posets could generalize the work of Bousquet-M\'elou et al.\ and we make a conjecture to that effect. We also identify natural subsets of matchings and posets that are equinumerous to the class of unlabeled -free posets. We give bijections that show the equivalence of (neighbor) restrictions on nesting arcs with (neighbor) restrictions on crossing arcs. These bijections are thought to be of independent interest. One of the bijections maps via certain upper-triangular integer matrices that have recently been studied by Dukes and Parviainen [Electron. J. Combin. 17 (2010) \#R53
Counting occurrences of a pattern of type (1,2) or (2,1) in permutations
No full textBabson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Claesson presented a complete solution for the number of permutations avoiding any single pattern of type (1,2) or (2,1). For eight of these twelve patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers. With respect to being equidistributed there are three different classes of patterns of type (1,2) or (2,1). We present a recursion for the number of permutations containing exactly one occurrence of a pattern of the first or the second of the aforementioned classes, and we also find an ordinary generating function for these numbers. We prove these results both combinatorially and analytically. Finally, we give the distribution of any pattern of the third class in the form of a continued fraction, and we also give explicit formulas for the number of permutations containing exactly r occurrences of a pattern of the third class when r∈{1,2,3}
Unio mystica III
No full textMusik av Carl-Axel Hall
Videoverk av Petra Johansson, Neta Norrmo och Sarah Schmidt.
Medverkande: Nina Åkerblom Nielsen - flöjt
Anders Jonhäll - flöjt
Urban Claesson - klarinett
Philip Foster - valthorn
Malvakvartetten: Brita Pettersson, Linnea Hällqvist , Maria Jonsson, Stina Larsdotter
Ahmad al-Khatib - oud
Carl-Axel Hall, Fredrik Duvling, Johan Renman - slagverk
Andreas Hall - saxofon
Dirigent: Johannes Landgren
Medverkande
Nina Åkerblom Nielsen - sång
Anders Jonhäll - flöjt
Urban Claesson - klarinett
Philip Foster - valthorn
Malvakvartetten: Brita Pettersson, Linnea Hällqvist - violin, Maria Jonsson - viola, Stina Larsdotter - cello
Ahmad al-Khatib - oud
Carl-Axel Hall, Magnus Ricklund - piano
Daniel Berg, Fredrik Duvling, Johan Renman - slagverk
Andreas Hall - saxofon
Dirgent: Johannes Landgre
Sorting with pattern-avoiding stacks : the 132-machine
No full textThis paper continues the analysis of the pattern-avoiding sorting machines recently introduced by Cerbai, Claesson and Ferrari (2020). These devices consist of two stacks, through which a permutation is passed in order to sort it, where the content of each stack must at all times avoid a certain pattern. Here we characterize and enumerate the set of permutations that can be sorted when the first stack is 132-avoiding, solving one of the open problems proposed by the above mentioned authors. To that end we present several connections with other well known combinatorial objects, such as lattice paths and restricted growth functions (which encode set partitions). We also provide new proofs for the enumeration of some sets of pattern-avoiding restricted growth functions and we expect that the tools introduced can be fruitfully employed to get further similar results
- …
