Notes on a problem involving permutations as subsequences.
Malcolm C. Newey · 1973
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.