What are the smallest sets of $n$-permutations of $\{1, 2, \ldots, n\}$ where all n-combinations are "prefix-permutation" of one element of the set?

Question

What are the smallest sets of $n$-permutations of $\{1, 2, \ldots, n\}$ where all combinations of $\{1, 2, \ldots, n\}$ are "prefix-permutation" of at least one element of the set?

Notation

Solution

Let's call $S_n$ a set of permutations that satisfy the property:

Set of n-permutations of $\{1, 2, \ldots, n\}$ where all combinations of $\{1, 2, \ldots, n\}$ are "prefix-permutation" of at least one element of the set?

Combinations

Let's call $C_n$ the set of all combinations of $\{1, 2, \ldots, n\}$.

prefix-permutation

$a=(a_1,\ldots,a_n)$ is prefix-permutation of $b=(b_1,\ldots,b_m)$ if there is a permutations of $b$ that is prefix of $a$.

Solutions for $n \in \{1, 2, 3, 4, 5, 6\}$

$S_1=\{(0)\}$

Trivial.

$S_2=\{(0,1), (1,0)\}$

There is only one minimal solution for $n=2$. Every combination of $C_2=\{(0), (1), (0,1)\}$ is prefix-permutation of at least one element of $S_2$. One can recognize that $S_2$ is the set of $1$-cycle permutations of $\{0,1\}$ called rotations.

$S_3=\{(0,1,2), (1,2,0), (2,0,1)\}$

There is several minimal solution for for $n=3$. We recognize that $S_3$ is the set of rotations.

$S_3=\{(0,2,1), (1,0,2), (2,1,0)\}$

A solution is not necessarly a superset of rotations.

$n=4$

There is 1024 solutions with a size 6. Among them there is 16 solutions that are superset of rotations, here is one of them, $S_4$:

• $(0,1,2,3)$
• $(1,2,3,0)$
• $(2,3,0,1)$
• $(3,0,1,2)$
• $(0,2,1,3)$
• $(1,3,0,2)$

Apparently, there is no solution of size 5 that includes all rotations.

$n=5$

Here is a solution that includes all rotations of size 10:

• $(0,1,2,3,4)$
• $(1,2,3,4,0)$
• $(2,3,4,0,1)$
• $(3,4,0,1,2)$
• $(4,0,1,2,3)$
• $(4,2,1,0,3)$
• $(3,1,0,2,4)$
• $(3,0,2,4,1)$
• $(2,0,4,1,3)$
• $(1,4,3,0,2)$

Apparantly, there is no solution of size 9.

$n=6$

Here is a solution of size 25 that is superset of rotations:

(5 0 1 2 3 4)
(4 5 0 1 2 3)
(3 4 5 0 1 2)
(2 3 4 5 0 1)
(1 2 3 4 5 0)
(0 1 2 3 4 5)
(0 2 1 3 4 5)
(0 3 2 1 5 4)
(0 4 3 1 5 2)
(0 4 2 3 1 5)
(2 1 5 3 0 4)
(3 2 1 5 0 4)
(3 1 4 5 0 2)
(3 1 5 4 2 0)
(3 0 1 4 2 5)
(3 5 2 0 1 4)
(4 3 1 0 2 5)
(4 2 1 5 3 0)
(4 1 0 2 5 3)
(4 5 2 1 0 3)
(5 4 1 2 3 0)
(5 3 0 1 4 2)
(5 2 1 3 4 0)
(5 1 2 4 0 3)
(5 0 2 4 3 1)

Answer 1

The size of minimal $S_n$ is $n \choose \lfloor \frac n2 \rfloor$, the central binomial coefficient.

Actually, what are you looking for is the covering of the boolean lattice by minimal number of maximal chains, which is obviously equal to minimal number in its chain parition. In turn, by Dilworth's theorem, the latter minimal number coincides with the cardinality of maximal antichain, which for boolean lattice is well known to be $n \choose \lfloor \frac n2 \rfloor$.

Answer 2

Consider the set of combinations of size $\lfloor n/2\rfloor$. There are $\binom{n}{\lfloor n/2\rfloor}$ of these, and each is a prefix of at most one permutation, so you need at least $\binom{n}{\lfloor n/2\rfloor}$ permutations in your set.

It is possible to find a set with $\binom{n}{\lfloor n/2\rfloor}$ permutations. To do this, first, enumerate all of the combinations of size $\lfloor n/2\rfloor$. For each combination, $C$, perform the following procedure to turn in into a permutation:

1. Let $L$ be an $n$ element list whose $i^{th}$ element is $(i,1)$ if $i\in C$, and $(i,0)$ otherwise.

2. Let $A$ and $B$ be empty lists.

3. While $L$ has an element $(i,0)$ followed by an element $(j,1)$,

   • Delete $(i,0)$ and $(j,1)$ from $L$.
   • Add $j$ to $A$ and add $i$ to $B$.

4. Replace each remaining element $(i,b)$ of $L$ with $i$.

5. Return the concatenation $A+L+B$.