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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/73/340/CS-TR-73-340.pdf