检索结果-内蒙古大学图书馆

The feasible regions for consecutive patterns of pattern-avoiding permutations

DISCRETE MATHEMATICS 2023年第2期346卷

作者： Borga, Jacopo Penaguiao, Raul Stanford Univ Dept Math Stanford CA USA San Francisco State Univ Dept Math San Francisco CA 94132 USA

We study the feasible region for consecutive patterns of pattern-avoiding permutations. More precisely, given a family C of permutations avoiding a fixed set of patterns, we consider the limit of proportions of consecutive patterns on large permutations of C. These limits form a region, which we call the consecutive patterns feasible region for C. We determine the dimension of the consecutive patterns feasible region for all families C closed either for the direct sum or the skew sum. These families include for instance the ones avoiding a single pattern and all substitution-closed classes. We further show that these regions are always convex and we conjecture that they are always polytopes. We prove this conjecture when C is the family of t-avoiding permutations, with either t of size three or t a monotone pattern. Furthermore, in these cases we give a full description of the vertices of these polytopes via cycle polytopes. Along the way, we discuss connections of this work with the problem of packing patterns in pattern-avoiding permutations and to the study of local limits for pattern-avoiding permutations.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Feasible region pattern-avoiding permutations Cycle polytopes Overlap graphs Consecutive patterns

来源：评论

学校读者我要写书评

暂无评论

pattern-avoiding permutations and Brownian excursion part I: Shapes and fluctuations

引用

RANDOM STRUCTURES & ALGORITHMS 2017年第3期50卷 394-419页

作者： Hoffman, Christopher Rizzolo, Douglas Slivken, Erik Univ Washington Dept Math Seattle WA 98195 USA Univ Delaware Dept Math Sci Newark DE 19716 USA Univ Calif Davis Dept Math Davis CA 95616 USA

permutations that avoid given patterns are among the most classical objects in combinatorics and have strong connections to many fields of mathematics, computer science and biology. In this paper we study the scaling limits of a random permutation avoiding a pattern of length 3 and their relations to Brownian excursion. Exploring this connection to Brownian excursion allows us to strengthen the recent results of Madras and Pehlivan [25] and Miner and Pak [29] as well as to understand many of the interesting phenomena that had previously gone unexplained. (c) 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 394-419, 2017

关键词： pattern-avoiding permutations Brownian Excursion fixed point distribution

来源：评论

学校读者我要写书评

暂无评论

Implicit Generation of pattern-avoiding permutations by Using Permutation Decision Diagrams

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2014年第6期E97A卷 1171-1179页

作者： Inoue, Yuma Toda, Takahisa Minato, Shin-ichi Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido 0600814 Japan JST ERATO MINATO Discrete Struct Manipulat Syst P Sapporo Hokkaido 0600814 Japan

pattern-avoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. pattern-avoiding permutations are related to practical and abstract mathematical problems and can provide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration (VLSI) circuit design, can be encoded into pattern-avoiding permutations. The generation of pattern-avoiding permutations is an important topic in efficient VLSI design and mathematical analysis of patten-avoiding permutations. In this paper, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Our approach is based on the data structure pi DDs, which can represent a permutation set compactly and has useful set operations. We demonstrate the efficiency of our algorithm by computational experiments.

关键词： pattern-avoiding permutations generating algorithms decision diagrams pi DD experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

A positional statistic for 1324-avoiding permutations

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2024年第1期26卷

作者： Gil, Juan B. Lopez, Oscar A. Weiner, Michael D. Penn State Altoona Altoona PA 16601 USA Penn State Harrisburg Middletown PA USA

We consider the class S-n(1324) of permutations of size n that avoid the pattern 1324 and examine the subset S-n(a = 1. This notation means that, when written in one line notation, such a permutation must have a to th... 详细信息

We consider the class S-n(1324) of permutations of size n that avoid the pattern 1324 and examine the subset S-n(a < n)(1324) of elements for which a < n <[a-1], a >= 1. This notation means that, when written in one line notation, such a permutation must have a to the left of n, and the elements of {1,& mldr;,a-1} must all be to the right of n. For n >= 2, we establish a connection between the subset of permutations in S-n(1 < n)(1324) having the 1 adjacent to the n (called primitives), and the set of 1324-avoiding dominoes with n-2 points. For a is an element of{1,2}, we introduce constructive algorithms and give formulas for the enumeration of S-n(a < n)(1324) by the position of aa relative to the position of n. For a >= 3, we formulate some conjectures for the corresponding generating functions.

关键词： pattern-avoiding permutations enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

patterns in random permutations avoiding the pattern 321

引用

RANDOM STRUCTURES & ALGORITHMS 2019年第2期55卷 249-270页

作者： Janson, Svante Uppsala Univ Dept Math POB 480 SE-75106 Uppsala Sweden

We consider a random permutation drawn from the set of 321-avoiding permutations of length n and show that the number of occurrences of another pattern sigma has a limit distribution, after scaling by n(m + l) where m is the length of sigma and l is the number of blocks in it. The limit is not normal, and can be expressed as a functional of a Brownian excursion.

关键词： patterns in permutations pattern-avoiding permutations random permutations

来源：评论

学校读者我要写书评

暂无评论

permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences

引用

ADVANCES IN APPLIED MATHEMATICS 2020年 116卷 102002-102002页

作者： Mansour, Toufik Yildirim, Gokhan Univ Haifa Dept Math IL-3498838 Haifa Israel Bilkent Univ Dept Math TR-06800 Ankara Turkey

We study the longest increasing subsequence problem for random permutations avoiding the pattern 312 and another pattern tau under the uniform probability distribution. We determine the exact and asymptotic formulas for the average length of the longest increasing subsequences for such permutation classes specifically when the pattern tau is monotone increasing or decreasing, or any pattern of length four. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Longest increasing subsequence problem pattern-avoiding permutations Chebyshev polynomials Generating functions

来源：评论

学校读者我要写书评

暂无评论

A Note on Flips in Diagonal Rectangulations

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2018年第2期20卷 1页

作者： Cardinal, Jean Sacristan, Vera Silveira, Rodrigo, I Univ Libre Bruxelles Brussels Belgium Univ Politecn Cataluna Barcelona Spain

Rectangulations are partitions of a square into axis-aligned rectangles. A number of results provide bijections between combinatorial equivalence classes of rectangulations and families of pattern-avoiding permutations. Other results deal with local changes involving a single edge of a rectangulation, referred to as flips, edge rotations, or edge pivoting. Such operations induce a graph on equivalence classes of rectangulations, related to so-called flip graphs on triangulations and other families of geometric partitions. In this note, we consider a family of flip operations on the equivalence classes of diagonal rectangulations, and their interpretation as transpositions in the associated Baxter permutations, avoiding the vincular patterns {3 (14) under bar2,2 (41) under bar3} This complements results from Law and Reading (JCTA, 2012) and provides a complete characterization of flip operations on diagonal rectangulations, in both geometric and combinatorial terms.

关键词： rectangulations flip graphs pattern-avoiding permutations

来源：评论

学校读者我要写书评

暂无评论

Another look at bijections for pattern-avoiding permutations

引用

ADVANCES IN APPLIED MATHEMATICS 2010年第3期45卷 395-409页

作者： Bloom, Jonathan Saracino, Dan Colgate Univ Dept Math Hamilton NY 13346 USA

In Bloom and Saracino (2009) [2] we proved that a natural bijection Gamma : S(n)(321) -> S(n)(132) that Robertson defined by an iterative process in Robertson (2004) [8] preserves the numbers of fixed points and excedances in each sigma is an element of S(n)(321). The proof depended on first showing that Gamma(sigma(-1)) = (Gamma(sigma))(-1) for all sigma is an element of S(n)(321). Here we give a noniterative definition of Gamma that frees the result about fixed points and excedances from its dependence on the result about inverses, while also greatly simplifying and elucidating the result about inverses. We also establish a simple connection between Gamma and an analogous bijection phi* : S(n)(213) -> S(n)(321) introduced in Backelin et al. (2007) [1] and studied in Bousquet-Melou and Steingrimsson (2005) [3]. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Bijection pattern-avoiding permutations Templates Fixed-points Excedances

来源：评论

学校读者我要写书评

暂无评论

The maximal-inversion statistic and pattern-avoiding permutations

引用

DISCRETE MATHEMATICS 2009年第9期309卷 2649-2657页

作者： Min, Sook Park, SeungKyung Yonsei Univ Dept Math Wonju South Korea Yonsei Univ Dept Math Seoul 120749 South Korea

We define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number M(n, k) of permutations in S-n with k maximal-inversions is the signless Stirling number c(n, n-k) of the first kind. A permutation pi in S-n is uniquely determined by its maximal-inversion set MI(pi). We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Maximal-inversion pattern-avoiding permutations Signless Stirling numbers

来源：评论

学校读者我要写书评

暂无评论

A variant of the tandem duplication - random loss model of genome rearrangement

引用

THEORETICAL COMPUTER SCIENCE 2009年第8-10期410卷 847-858页

作者： Bouvel, Mathilde Rossin, Dominique Univ Paris Diderot LIAFA CNRS F-75205 Paris 13 France

In [K. Chaudhuri, K. Chen, R. Mihaescu, S. Rao, On the tandem duplication-random loss model of genome rearrangement, in: SODA, 2006, pp. 564-570]. Chaudhuri, Chen, Mihaescu and Rao study algorithmic properties of the tandem duplication - random loss model of genome rearrangement, well-known in evolutionary biology. In their model, the cost of one step of duplication-loss of width k is alpha(k) for alpha = 1 or alpha >= 2. In this paper, we study a variant of this model, where the cost of one step of width k is 1 if k <= K and infinity if k > K, for any value of the parameter K is an element of N boolean OR {infinity}. We first show that permutations obtained after p steps of width K define classes of pattern-avoiding permutations. We also compute the numbers Of duplication-loss steps of width K necessary and sufficient to obtain any permutation of S(n) in the worst case and on average. In this second part, we may also consider the case K = K(n), a function of the size n of the permutation oil which the duplication-loss operations are performed. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Sorting permutations pattern Genome rearrangement Tandem duplication - random loss model pattern-avoiding permutations

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：