Strings with maximally many distinct subsequences and substrings

MaRDI QIDQ1422149zbMATH OpenFDO

Authors Aram W. Harrow, Gregory B. Sorkin, Abraham D. Flaxman

Publication date 5 February 2004

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/123417, http://www.emis.de/journals/EJC/Volume_11/Abstracts/v11i1r8.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal combinatorics

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorics on words (68R15)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 2185636
• Algorithms for subsequence combinatorics
• Subsequence Combinatorics and Applications to Microarray Production, DNA Sequencing and Chaining Algorithms
• Two-pattern strings. II: Frequency of occurrence and substring complexity
• scientific article; zbMATH DE number 1992419

Cited in

(16)

• Counting distinct strings
• On extending de Bruijn sequences
• Maximal state complexity and generalized de Bruijn words
• Finding binary words with a given number of subsequences
• On the maximum number of distinct factors of a binary string
• Algorithms for subsequence combinatorics
• Test sequence construction using minimum information on the tested system
• scientific article; zbMATH DE number 2185636 (Why is no real title available?)
• Maximal Words in Sequence Comparisons Based on Subword Composition
• On the Number of Subsequences When Deleting Symbols From a String
• scientific article; zbMATH DE number 1062562 (Why is no real title available?)
• Diagonal Asymptotics for Products of Combinatorial Classes
• Combined super-/substring and super-/subsequence problems
• Subsequence frequency in binary words
• On average sequence complexity
• Upper bounds on distinct maximal (sub-)repetitions in compressed strings

This page was built for publication: Strings with maximally many distinct subsequences and substrings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1422149)