Report Number: CS-TR-73-340
Institution: Stanford University, Department of Computer Science
Title: Notes on a problem involving permutations as subsequences.
Author: Newey, Malcolm C.
Date: March 1973
Abstract: 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. This paper catalogs some of the easy observations on the problem and proves that the minimum lengths for n=5, n=6 & n=7 are 19, 28 and 39 respectively. Also presented is a construction which yields (for n>2) many appropriate sequences of length $n^2$-2n+4 so giving an upper bound on length of minimum strings which matches exactly all known values.