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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 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

来源：评论

学校读者我要写书评

暂无评论

Some generalizations of a Simion-Schmidt bijection

引用

COMPUTER JOURNAL 2007年第5期50卷 574-580页

作者： Juarna, Asep Vajnovszki, Vincent Univ Bourgogne CNRS UMR LE21 F-47870 Dijon France

In 1985, Simion and Schmidt gave a constructive bijection phi from the set of all length (n - 1) binary strings having no two consecutive 1s to the set of all length n permutations avoiding all patterns in {123,132,213}. In this paper, we generalize p to an injective function from {0,1}(n-1) to the set S. of all length n permutations and derive from it four bijections phi : P -> Q where P subset of{0,1}(n-1) and Q subset of S-n. The domains are sets of restricted binary strings and the codomains are sets of pattern-avoiding permutations. As a particular case we retrieve the original Simion-Schmidt bijection. We also show that the bijections obtained are actually combinatorial isomorphisms, i.e. closeness-preserving bijections. Three of them have known Gray codes and generating algorithms for their domains and we present similar results for each corresponding codomain, under the appropriate combinatorial isomorphism.

关键词： pattern-avoiding permutations Fibonacci and Lucas strings constructive bijections combinatorial isomorphisms Gray codes

来源：评论

学校读者我要写书评

暂无评论

Wilf classification of three and four letter signed patterns

引用

DISCRETE MATHEMATICS 2008年第15期308卷 3125-3133页

作者： Dukes, W. M. B. Mansour, T. Reifegerste, A. Univ Coll Dublin Sch Math Sci Dublin Ireland Univ Haifa Dept Math IL-31905 Haifa Israel Leibniz Univ Hannover Fak Math & Phys D-30167 Hannover Germany

We give some new Wilf equivalences for signed patterns which allow the complete classification of signed patterns of lengths three and four. The problem is considered for pattern avoidance by general as well as involu... 详细信息

关键词： forbidden subsequences pattern-avoiding permutations signed permutations signed involutions Wilf equivalence

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：