Accession Number:

AD0759714

Title:

Notes on a Problem Involving Permutations as Subsequences

Descriptive Note:

Technical rept.

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1973-03-01

Pagination or Media Count:

25.0

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. The paper catalogs come of the easy observations on the problem and proves that the minimum lengths for n5, n6 and n7 are 19, 28 and 39 respectively. Also presented is a construction which yields for n2 many appropriate sequences of length n sup 2-2n4 so giving an upper bound on length of minimum strings which matches exactly all known values.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE