Strings with maximally many distinct subsequences and substrings (Q1422149): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: author (P16): Item:Q452815
RedirectionBot (talk | contribs)
Changed an Item
Property / author
 
Property / author: Abraham D. Flaxman / rank
 
Normal rank

Revision as of 09:07, 15 February 2024

scientific article
Language Label Description Also known as
English
Strings with maximally many distinct subsequences and substrings
scientific article

    Statements

    Strings with maximally many distinct subsequences and substrings (English)
    0 references
    0 references
    0 references
    0 references
    5 February 2004
    0 references
    Summary: 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,...)\) has the maximum number of distinct subsequences, namely Fib \((n+3)-1\sim ((1+\sqrt5)/2)^{n+3} / \sqrt5\). We also consider the same problem with substrings in lieu of subsequences. 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.
    0 references
    extremal combinatorics
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references