**Originator**: R. Karp and D. Knuth
(presented by David Galvin - REGS 2011)

**Definitions:**
Let $S_n$ denote the set of permutations of $[n]$. For $1\le k\le n$,
let $S_n(k)$ be the set of $k$-permutations from $[n]$, meaning the
$k!\binom nk$ permutations of $k$-subsets of $[n]$. A *word* is a list
of elements of $[n]$; here we treat permutations as words. A word $w$
*contains* a word $\pi$ if the elements of $\pi$ occur somewhere in $w$ in
the same order as in $\pi$ (not necessarily consecutively).

**Problem 1:**
Determine the minimum length, $f(n)$, of a word that contains every element of
$S_n$.

**Problem 2:**
For $1\le k\le n$, determine the minimum length, $g(n,k)$, of a word that
contains every element of $S_n(k)$.

**Problem 3:**
For $1\le m\le n!$, determine the minimum length, $h(n,m)$, of a word that
contains at least $m$ elements of $S_n$. (Similarly, one could ask for the
shortest word to contain at least $m$ element of $S_n(k)$.)

**Background:**
Problem 1 was posed by Knuth in a 1972 Stanford Computer Science Technical
report, where he atributes the problem to Karp. Adleman [A] reports that Karp
discovered the problem studying the complexity of some shortest path
algorithms. Problem 2 was asked by Savage [S], and Problem 3 seems to be
due to Galvin.

**Comments:**
Using $n-1$ repetitions of $1,.~.~.,n$ plus a single $1$ at the end yields
$f(n)\leq n^2 -n+1$. Adleman [A] (and many authors around the same time)
improved this to $f(n) \leq n^2-2n+4$, proved that this is tight for $n\le7$,
and conjectured equality for all $n$. However, Zălinescu [Z] disproved
the conjecture, giving a construction to show that $f(n)\le n^2-2n+3$ when
$n\ge10$.

For a lower bound, consider a word containing all permutations. It has at least $n$ characters until the last occurrence of a new symbol; let $a$ be that symbol. Subsequently there are at least $n-1$ characters until all pairs starting with $a$ have been seen; let $ab$ be the last. Subsequently there are at least $n-2$ characters until all triples starting with $ab$ have been seen, and so on. Thus $f(n) \geq \binom{n+1}{2}$. Kleitman and Kwiatkowsky improved this to $f(n) \geq (1-o(1))n^2$ (specifically, they showed that for $\varepsilon > 0$ there exist $C(\varepsilon)$ such that $f(n)\geq n^2-C(\varepsilon)n^{7/4+\varepsilon}$).

Savage [S] observed that $g(n,k)\le k(n-2)+4$. For $n\ge k\ge 10$, Zălinescu [Z] improved this to $g(n,k) \leq k(n-2)+3$; we write the upper bound as $kn-(2k-3)$. The argument above for $f(n)\ge\binom{n+1}2$ more generally yields $g(n,k)\ge kn-\binom k2$.

An easy lower bound on $h(n,m)$ is given by ${h(n,m) \choose n}\geq m$. When $m=1$ or $m=n!$ this bound is correct up to a multiplicative constant.

**Question 4:** For $n \geq 1$ and $1 \leq m \leq n!$, let $\ell(m,n)$
be the least integer such that ${\ell(m,n) \choose n} \geq m$. Is there a
positive constant $C$ such that $h(n,m) \leq C\ell(m,n)$?

**References:**

[A] L. Adleman, Short permutation strings, Discrete Mathmatics, 1974.

[KK] D. Kleitman and D. Kwiatkowsky, A lower bound on the length of a sequence containing all permutations as subsequences, Journal of Combinatorial Theory Series A, 1976.

[S] C. Savage, Short strings containing all $k$-element permutations, Discrete Mathematics, 1982.

[Z] E. Zălinescu, Shorter strings containing all $k$-element permutations, Information Processing Letters, 2011.