tailieunhanh - Báo cáo toán học: "Strings with maximally many distinct subsequences and substrings"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Strings with maximally many distinct subsequences and substrings. | Strings with maximally many distinct subsequences and substrings Abraham Flaxman Department of Mathematical Sciences Carnegie Mellon University Pittsburgh PA USA abie@ Aram W. Harrow Department of Physics Massachusetts Institute of Technology Cambridge MA USA aram@ Gregory B. Sorkin Department of Mathematical Sciences IBM Research Yorktown Heights NY USA sorkin@ Submitted Nov 18 2003 Accepted Dec 9 2003 Published Jan 5 2004 MR Subject Classifications 68R15 05D40 05A15 05A16 Abstract A natural problem in extremal combinatorics is to maximize the number of distinct subsequences for any length-n string over a finite alphabet E this value grows exponentially but slower than 2n. 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 E 1 2 1 2 1 2 . has the maximum number of distinct subsequences namely Fib n 3 1 1 G5 2 ra 3 A5. 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. 1 Introduction In this article we consider a natural problem in the extremal combinatorics of strings namely to find a string whose number of subsequences is as large as possible and to determine the number. Strings and texts are themselves one of the basic combinatorial structures and the sorting searching and compression of strings is even more important THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R8 1 with strings comprising one of the most important facets of the World-Wide Web and the only facet currently indexable . We would thus have expected such an elementary question already to have been considered but we have been unable to find the problem or its solution in .