# Notes on a problem involving permutations as subsequences

- Title:
- Notes on a problem involving permutations as subsequences
- Author:
- Newey, Malcolm C.
- Author (no Collectors):
- Newey, Malcolm C.
- Collector:
- Newey, Malcolm C.
- Description:
- 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.
- Topic:
- Computer science
- Subject:
- Stanford University. Computer Science Department
- Language:
- English
- Physical Description:
- 1 text file
- Publication Info:
- Stanford (Calif.) and cau
- Date:
- March 1, 1973
- Place created:
- Stanford (Calif.)
- Imprint:
- Stanford (Calif.), March 1, 1973
- Genre:
- technical reports
- Identifier:
- CS-TR-1973-340
- Repository:
- Stanford University. Libraries. Department of Special Collections and University Archives
- Collection:
- Stanford University, Department of Computer Science, Technical Reports and Stanford Artificial Intelligence Laboratory records, 1963-2009
- Manuscript number:
- 3840/2