Shorter strings containing all k-element permutations

We consider the problem of finding short strings that contain all permutations of order k over an alphabet of size n  , with k⩽nk⩽n. We show constructively that k(n−2)+3k(n−2)+3 is an upper bound on the length of shortest such strings, for n⩾k⩾10n⩾k⩾10. Consequently, for n⩾10n⩾10, the shortest strings that contain all permutations of order n   have length at most n2−2n+3n2−2n+3. These two new upper bounds improve with one unit the previous known upper bounds.

► We build n2−2n+3n2−2n+3 length strings containing all permutations of order n  , for n⩾10n⩾10. ► This new upper bound improves with one unit the previous known upper bound. ► We present a generalization to permutations of order k over an alphabet of size n.