Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations

Area of Science:

• Combinatorics on words
• Statistical physics of disordered systems
• Probability theory

Background:

• The enumeration of pattern occurrences in combinatorial structures like words and permutations is a fundamental problem.
• Understanding the asymptotic behavior of these occurrences is crucial for analyzing large structures and developing statistical models.
• Existing research often focuses on exact avoidance or enumeration, with less emphasis on the distribution of multiple occurrences.

Purpose of the Study:

• To investigate the asymptotic properties of the number of occurrences of a specific pattern in n-array k-ary words.
• To analyze the distribution of the random variable representing pattern occurrences in random words.
• To extend these findings to pattern occurrences in permutations and introduce novel concepts like weak avoidance.

Main Methods:

• Asymptotic analysis of sequences related to pattern enumeration.
• Derivation of limit theorems, including central limit theorems and large deviation estimates.
• Introduction and analysis of weak avoidance and non-product probability measures on words.

Main Results:

• The Stanley-Wilf sequence, counting words with exactly r pattern occurrences, converges to a limit independent of r.
• Established limit theorems for the distribution of random pattern occurrences, including growth rate of entropy.
• Extended results on pattern occurrences and Stanley-Wilf sequences to permutations.

Conclusions:

• The number of pattern occurrences in large words and permutations exhibits predictable asymptotic behavior.
• The introduced concept of weak avoidance provides a new framework for studying pattern distributions.
• The study offers a comprehensive analysis of pattern occurrences, bridging combinatorics and probability theory.