Mansour Toufik, Rastegar Reza, Roitershtein Alexander
Department of Mathematics, University of Haifa, 199 Abba Khoushy Ave, 3498838 Haifa, Israel.
Occidental Petroleum Corporation, Houston, TX 77046 and Departments of Mathematics and Petroleum Engineering, University of Tulsa, OK 74104, USA - Adjunct Professor.
SIAM J Discret Math. 2020;34(2):1011-1038. doi: 10.1137/19m1262206. Epub 2020 Apr 8.
The main theme of this paper is the enumeration of the order-isomorphic occurrence of a pattern in words and permutations. We mainly focus on asymptotic properties of the sequence , the number of -array -ary words that contain a given pattern exactly times. In addition, we study the asymptotic behavior of the random variable , the number of pattern occurrences in a random -array word. The two topics are closely related through the identity . In particular, we show that for any ≥ 0, the Stanley-Wilf sequence converges to a limit independent of , and determine the value of the limit. We then obtain several limit theorems for the distribution of , including a central limit theorem, large deviation estimates, and the exact growth rate of the entropy of . Furthermore, we introduce a concept of weak avoidance and link it to a certain family of non-product measures on words that penalize pattern occurrences but do not forbid them entirely. We analyze this family of probability measures in a small parameter regime, where the distributions can be understood as a perturbation of a uniform measure. Finally, we extend some of our results for words, including the one regarding the equivalence of the limits of the Stanley-Wilf sequences, to pattern occurrences in permutations.
本文的主题是对单词和排列中模式的序同构出现进行计数。我们主要关注序列(a_n)的渐近性质，(a_n)是包含给定模式恰好(k)次的(m)元(n)数组单词的数量。此外，我们研究随机变量(X_n)的渐近行为，(X_n)是随机(m)元(n)数组单词中模式出现的次数。这两个主题通过等式(E(X_n)=ka_n)紧密相关。特别地，我们证明对于任意(k\geq0)，斯坦利 - 威尔夫序列({a_n^{\frac{1}{n}}})收敛到一个与(k)无关的极限，并确定该极限的值。然后我们得到了关于(X_n)分布的几个极限定理，包括中心极限定理、大偏差估计以及(X_n)熵的精确增长率。此外，我们引入了弱避免的概念，并将其与单词上的某类非乘积测度联系起来，这类测度会对模式出现进行惩罚但并非完全禁止。我们在小参数区域分析这类概率测度，在该区域中分布可理解为均匀测度的一种扰动。最后，我们将关于单词的一些结果，包括斯坦利 - 威尔夫序列极限等价性的结果，推广到排列中的模式出现情况。
