Finite Automata, Probabilistic Method, and Occurrence Enumeration of a Pattern in Words and Permutations

DOI10.1137/19M1262206zbMath1437.05010arXiv1905.05646WikidataQ91788432 ScholiaQ91788432MaRDI QIDQ5107065

Alexander Roitershtein, Reza Rastegar, Toufik Mansour

Publication date: 22 April 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

limit theoremsrandom wordsfinate automatapattern occurrencesStanley-Wilf type limitsweak avoidance

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Exact enumeration problems, generating functions (05A15) Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Combinatorial probability (60C05) Large deviations (60F10) Asymptotic enumeration (05A16)

Related Items (5)

On avoiding 1233 ⋮ Shifting powers in Spivey’s Bell number formula ⋮ Fixed points of a random restricted growth sequence ⋮ On Stanley-Wilf limit of the pattern 1324 ⋮ Pattern occurrences in \(k\)-ary words revisited: a few new and old observations

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Patterns in permutations and words.
• Large deviations techniques and applications.
• Normal convergence by higher semi-invariants with applications to sums of dependent random variables and random graphs
• Two moments suffice for Poisson approximations: The Chen-Stein method
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• On the cycle structure of Mallows permutations
• Finite automata and pattern avoidance in words
• On normal approximation rates for certain sums of dependent random variables
• Central limit theorems for patterns in multiset permutations and set partitions
• Lengths of monotone subsequences in a Mallows permutation
• On the asymptotic statistics of the number of occurrences of multiple permutation patterns
• Regenerative random permutations of integers
• Some open problems on permutation patterns
• Approaches for enumerating permutations with a prescribed number of occurrences of patterns
• Thermodynamic limit for the Mallows model on Sn
• Pattern Avoidance for Random Permutations
• Better upper bounds on the Füredi-Hajnal limits of permutations
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Large deviations for sums of partly dependent random variables
• Combinatorics of Compositions and Words
• Formulae and Asymptotics for Coefficients of Algebraic Functions
• Lectures on Self-Avoiding Walks
• On the Convergence of Sequences of Moment Generating Functions

This page was built for publication: Finite Automata, Probabilistic Method, and Occurrence Enumeration of a Pattern in Words and Permutations