Notes on a Problem Involving Permutations as Subsequences
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
The problem attributed to R. M. Karp by Knuth is to describe the sequences of minimum length which contain, as subsequences, all the permutations of an alphabet of n symbols. The paper catalogs come of the easy observations on the problem and proves that the minimum lengths for n5, n6 and n7 are 19, 28 and 39 respectively. Also presented is a construction which yields for n2 many appropriate sequences of length n sup 2-2n4 so giving an upper bound on length of minimum strings which matches exactly all known values.
- Theoretical Mathematics