Strings with Maximally Many Distinct Subsequences and Substrings
Strings with Maximally Many Distinct Subsequences and Substrings
复制标题
具有最多多个不同子序列和子字符串的字符串
DOI：
--
复制
发表时间：
2004
影响因子：
0.7
通讯作者：
G. Sorkin
中科院分区：
文献类型：
--
作者：
A. Flaxman;A. Harrow;G. Sorkin
极端组合学中的一个自然问题是，在有限字母$ sigma $上，任何长度 - $ n $ string的不同子序列的数量最大化；该值呈指数增长，但速度较慢$ 2^n $。我们使用概率方法来确定最大化的字符串，这是一个周期性重复的字符串。不同的子序列的数量是通过生成函数列举的，我们还从中得出了渐近估计。对于字母$ sigma = {1,2} $，$，（1,2,1,2，dots）$具有最大数量的不同子序列，即$ {
m fib}（n+3）-1 sim左（（1+sqrt5）/2
ight）^{n+3}！ / sqrt {5} $。我们还考虑了子字符串代替子序列的同样问题。在这里，我们表明，一个适当的截断的de bruijn单词达到了最大值。对于这两个问题，我们将随机字符串的性能与最佳字符串的性能进行比较。
A natural problem in extremal combinatorics is to maximize the number of distinct subsequences for any length-$n$ string over a finite alphabet $Sigma$; this value grows exponentially, but slower than $2^n$. We use the probabilistic method to determine the maximizing string, which is a cyclically repeating string. The number of distinct subsequences is exactly enumerated by a generating function, from which we also derive asymptotic estimates. For the alphabet $Sigma={1,2}$, $,(1,2,1,2,dots)$ has the maximum number of distinct subsequences, namely ${
m Fib}(n+3)-1 sim left((1+sqrt5)/2
ight)^{n+3} ! / sqrt{5}$. We also consider the same problem with sub strings in lieu of sub sequences . Here, we show that an appropriately truncated de Bruijn word attains the maximum. For both problems, we compare the performance of random strings with that of the optimal ones.