Strings with maximally many distinct subsequences and substrings
type: Item
instance of: scholarly article
title: Strings with maximally many distinct subsequences and substrings
zbMATH Open document ID: 1034.68067
author: Aram W. Harrow
author: Gregory B. Sorkin
author: Abraham D. Flaxman
published in: The Electronic Journal of Combinatorics
publication date: 2004-02-05T00:00:00Z
full work available at URL: https://eudml.org/doc/123417
full work available at URL: v11i1r8.html
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.
Mathematics Subject Classification ID: 68R15
Mathematics Subject Classification ID: 05D40
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A16
zbMATH DE Number: 2038354
zbMATH Keywords: extremal combinatorics
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2038354