Structure of random 312-avoiding permutations

DOI10.1002/RSA.20601MaRDI QIDQ2830242zbMATH OpenOpenAlexFDO

Authors Neal Madras, Lerna Pehlivan

Publication date 9 November 2016

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.6230

zbMATH Keywords

asymptotic probabilityDyck pathpattern-avoiding permutationrandom permutationrandom walk

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Sums of independent random variables; random walks (60G50)

Abstract: We evaluate the probabilities of various events under the uniform distribution on the set of 312-avoiding permutations of 1,...,N. We derive exact formulas for the probability that the ith element of a random permutation is a specific value less than i, and for joint probabilities of two such events. In addition, we obtain asymptotic approximations to these probabilities for large N when the elements are not close to the boundaries or to each other. We also evaluate the probability that the graph of a random 312-avoiding permutation has k specified decreasing points, and we show that for large N the points below the diagonal look like trajectories of a random walk.

Recommendations

• Patterns in random permutations avoiding the pattern 321
• Patterns in random permutations avoiding the pattern 132
• The shape of random pattern-avoiding permutations
• Patterns in random permutations avoiding some other patterns
• Patterns in random permutations avoiding some sets of multiple patterns

Cites work

• A variant of the tandem duplication-random loss model of genome rearrangement
• An area-to-inv bijection between Dyck paths and 312-avoiding permutations
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• scientific article; zbMATH DE number 5370481 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• Large deviations and ratio limit theorems for pattern-avoiding permutations
• Patterns in permutations and words.
• Permutations with restricted patterns and Dyck paths
• Random walk: A modern introduction
• Restricted permutations
• The shape of random pattern-avoiding permutations

Cited in

(20)

• The Brownian limit of separable permutations
• Avoiding patterns and making the best choice
• Sorting probability of Catalan posets
• Scaling limits of permutation classes with a finite specification: a dichotomy
• Universal limits of substitution-closed permutation classes
• Strategy-indifferent games of best choice
• Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
• Positional strategies in games of best choice
• A simple bijection between 312-avoiding permutations and triangulations
• Fixed points of 321-avoiding permutations
• Large deviations for permutations avoiding monotone patterns
• The location of the first ascent in a 123-avoiding permutation
• An algorithm computing combinatorial specifications of permutation classes
• Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
• Highly sorted permutations with respect to a 312-avoiding stack
• Rowmotion on 321-avoiding permutations
• A logical limit law for \(231\)-avoiding permutations
• Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
• A Galton-Watson tree approach to local limits of permutations avoiding a pattern of length three
• Pattern-avoiding permutations and Brownian excursion. II: Fixed points

This page was built for publication: Structure of random \(312\)-avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830242)