The Factor Spectrum and Derived Sequence

DOI：10.3770/j.issn:2095-2651.2019.06.015

 作者 单位 黄煜可 北京邮电大学理学院, 北京 100876 文志英 清华大学数学科学系, 北京 100084

对于任意给定的性质${\mathcal{P}}$和序列$\rho$, 词上的组合领域一个重要的研究课题是找出所有的因子$\omega$和序数$p$,使得序列$\rho$中第$p$次出现的因子$\omega$ (记为$\omega_p$) 满足性质${\mathcal{P}}$.这个问题等价于研究因子谱''.确定因子谱是一个困难的问题. 为了实现目标,我们引入并研究了一系列的概念:核词、包络词、回归词和任意因子的诱导序列. 利用因子谱和诱导序列,我们可以解决序列中的一些计数问题.例如:在序列的任意一个片段中回文或者高次方词的个数. 本文中,我们将结合几个特殊的序列展示相关的研究结果.这些序列包括: Fibonacci序列、Tribonacci序列、Period-doubling序列等等. 我们相信这些概念和方法对于所有的一致常返序列都是有效的.

Given a sequence $\rho$ over a finite alphabet $\mathcal{A}$, an important topic in combinatorics on words is to find out all factors $\omega$ of $\rho$ and positive integers $p$ such that $\omega_p$ (the $p$-th occurrence of $\omega$) fulfills property ${\mathcal{P}}$. This problem is equivalent to determining a notion called the factor spectrum. Determining the factor spectrum is a difficult problem. To this aim, we introduce several notions, such as: kernel word, envelope word, return word and derived sequence of each factor $\omega$. Using the factor spectrum and derived sequence, we can solve some enumerations of factors, such as the numbers of palindromes, fractional powers, etc. We will show some results for several sequences, such as the Fibonacci sequence, the Tribonacci sequence, the Period-doubling sequence, etc. And we think that these notions and methods are suitable for all recurrent sequences.