Define a $k$-*permutation* of $\{1,\ldots, n\}$ to be a word $\tau\_1 \ldots \tau\_k$ such that $\{\tau\_1,\ldots,\tau\_k\}$ is a $k$-subset of $\{1,\ldots, n\}$. Thus an $n$-permutation of $\{1,\ldots, n\}$ is a permutation written in one-line form. Given a $k$-permutation $\tau$ and a permutation $\sigma$ of $\{1,\ldots, n\}$, say that $\sigma$ *contains* $\tau$ if there exist positions $i\_1 < \ldots < i\_k$ such that $\sigma\_{i\_1} = \tau\_1, \ldots, \sigma\_{i\_k} = \tau\_k$.


For $k \le n$, let $f\_k(n)$ be the minimum $m$ such that there exist permutations $\sigma^{(1)}, \ldots, \sigma^{(m)}$ of $\{1,\ldots, n\}$ that taken together contain every $k$-permutation of $\{1,\ldots, n\}$. 



> 
> What is known about the asymptotics of $f\_k(n)$ as $n \rightarrow \infty$?
> 
> 
> 


It's easy to see that $f\_k(n) \ge k!$ for all $n \ge k$, and that $f\_2(n) = 2$ for all $n \ge 2$: just take $\sigma^{(1)} = 12\ldots n$ and $\sigma^{(2)} = n\ldots 21$. Some case-by-case checking shows that $f\_3(4) \ge 7$; since 


$$1234,4321,3412,2413,3214,1432,4231$$ 


together contain every $3$-permutation of $\{1,2,3,4\}$, we have $f\_3(4) = 7$. A simple greedy algorithm gives the upper bounds 


$$f\_3(5) \le 8, f\_3(6) \le 9, f\_3(7) \le 11, f\_3(8) \le 12$$ 


and $f\_4(5) = 24$, $f\_4(6) \le 36$, $f\_4(7) \le 44$, $f\_4(8) \le 47$.



> 
> What specific values of $f\_k(n)$ have been computed and what techniques were used?
> 
> 
> 



Minimum number of permutations of $\{1,\ldots, n\}$ that together contain every $k$-subpermutation
Sorry, I do not remember the appropriate reference. 


For the lower bound (for $k\geqslant 3$) we may apply the following argument, which uses much less information that is given and in particular does not depend on $k$. We have $m$ permutations, without loss of generality let the first be identical. For each $i=0,1,2,\dots,m-1$ we inductively construct a set $A\_i\subset A\_{i-1}\subset A\_0:=\{1, \ldots, n-1\} $ such that $|A\_i|\geqslant 2^{-i}(n-1)$ and the whole $A\_i$ is on the same side of the element $n$ in each of permutations $\pi\_1,\dots,\pi\_{i+1}$. If $|A\_{m-1}|>1$, we get two elements which are never separated by $n$, a contradiction. Therefore $n-1\leqslant 2^{m-1}$.


For the upper bound, choose $m$ permutations at random independently. The probability that a fixed word of length $k$ is never realized equals $(1-1/k!)^m$. So the total expected number of not-realized words equals $n(n-1)\dots (n-k+1)(1-1/k!)^m$. If it is less than 1, it happens with positive probability that all words are realized. This is so when $m>k\cdot k! \log n$. Applying Lovasz Local Lemma we probably should slightly improve this bound, but the coefficient is still huge. 


