论文标题
从Hertzsprung的问题到模式练习系统
From Hertzsprung's problem to pattern-rewriting systems
论文作者
论文摘要
在1887年Hertzsprung提出的问题上，我们说，给定的置换$π\在\ Mathcal {s} _n $中包含Hertzsprung模式$σ\ in \ in \ Mathcal {s} _K $，如果有$π（d+1）π（d+1）π（d+2+2）$ $π（d+1）-σ（1）= \ cdots =π（d+k）-σ（k）$。使用Goulden-Jackson群集方法和转移矩阵方法的组合，我们确定了任何一组（无与伦比的）Hertzsprung模式的发生的联合分布，因此Jackson等人的早期结果实质上概括了早期的结果。关于排列的上升和下降的分布。我们将结果应用于计数排列的问题，直到模式替代等效性，并使用模式练习系统（一种类似于研究众所周知的弦乐练习系统类似的新型形式主义） - 我们解决了Linton等人提出的几个开放问题。 2012年。
Drawing on a problem posed by Hertzsprung in 1887, we say that a given permutation $π\in\mathcal{S}_n$ contains the Hertzsprung pattern $σ\in\mathcal{S}_k$ if there is factor $π(d+1)π(d+2)\cdotsπ(d+k)$ of $π$ such that $π(d+1)-σ(1) =\cdots = π(d+k)-σ(k)$. Using a combination of the Goulden-Jackson cluster method and the transfer-matrix method we determine the joint distribution of occurrences of any set of (incomparable) Hertzsprung patterns, thus substantially generalizing earlier results by Jackson et al. on the distribution of ascending and descending runs in permutations. We apply our results to the problem of counting permutations up to pattern-replacement equivalences, and using pattern-rewriting systems -- a new formalism similar to the much studied string-rewriting systems -- we solve a couple of open problems raised by Linton et al. in 2012.
