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