This is a problem I asked on <https://math.stackexchange.com/questions/647382/union-of-permutations>. Feel free to close it if you think it below research level.


Having $k$ different permutations, $\pi\_{1},\dots,\pi\_{k}: \{1\ \ldots\ n\}\rightarrow \{1\ \ldots\ n\}$, the union of permutations is defined as follows: 


$$\forall i{\in}[n],\ U\_i=\{{\pi}\_1(i),{\pi}\_2(i),\dots,{\pi}\_k(i)\}$$


Note that in $U\_i$ there may be repetitions, so $|U\_i|{\leq}k$, let $s=\sum\_i^n|U\_i|$, so I want to ask, what is the minimum $\sigma(n\ k)$ of all $s$ as above for any $k$ permutations? 


For example, if we let $n=4,k=3$, we have three permutations 
\begin{equation}\pi\_1=1234,\pi\_2=2134,\pi\_3=3421\end{equation}
coded in the obvious way, then
\begin{equation}U\_1=\{1,2,3\},U\_2=\{2,1,4\},U\_3=\{3,2\},U\_4=\{4,1\}\end{equation}
so $s=3+3+2+2=10$. But we have a better choice:
\begin{equation} \pi\_1=1234,\pi\_2=2134,\pi\_3=1324 \end{equation}
here 
\begin{equation}
U\_1=\{1,2\},U\_2=\{2,1,3\},U\_3=\{3,2\},U\_4=\{4\}
\end{equation}, $s=2+3+2+1=8$.


Intuitively, the more the different permutations share common parts, the less $s$ will be, so if we let $k=i!$, then for permutations in the form $\pi=(\pi^{\*})(i+1)(i+2){\dots}n$ where $\pi^{\*}$ is any permutation of $1,2,\dots,i$, namely the $k$ different permutations differ only on the first $i$ elements, then $s$ may be minimum, and $s=i^2-i+n$. Take $n=6, k=6$ for example, the best choices of 6 different permutations may be:
\begin{equation}
\pi\_1=123456, \pi\_2=132456, \pi\_3=213456, \pi\_4=231456, \pi\_5=312456, \pi\_6=321456
\end{equation}
and the best $s=3+3+3+1+1+1=12$.
But this is a simple intuition; does anyone know what is the exact answer to this question?



Union of Permutations
$\def\perm{\mathop{\rm perm}}$This is a partial answer for the case when $n$ is large enough. In particular, we show that for $k=2^\ell$ and $n\geq 2\ell$ we have $s\geq n+2\ell$, supported by the model $U\_{2i}=U\_{2i-1}=\{2i-1,2i\}$, $i=1,\dots,\ell$.


For convenience, let us consider the permanent reformulation of the problem. Let us show that for every $s=n+\delta$, if the sum of elements of a 0-1 matrix $A$ is $s$ then $\perm A\leq 2^{\delta/2}$. The base case $\delta\leq 1$ is clear.


Take the row or column of $A$ containing the least number $t$ of 1's (WLOG this is the first row). If $t=0$, the statement is clear. So assume that $t\geq 1$. Then
$$
 \perm A=\sum\_{i=1}^t \perm A\_i,
$$
where $A\_i$ is obtained from $A$ by deletion of the first row and the column with $i$th one. Let $s\_i=(n-1)+\delta\_i$ be the sum of elemtents of $A\_i$; then $\delta\_i\leq \delta-2t+2$, because the deleted column had at least $t$ ones. 
Thus 
$$
 \perm A\leq t2^{(\delta-2t+2)/2}.
$$
Notice that $t2^{-t}\leq 1/2$ for positive integer $t$; so $\perm A\leq 2^{\delta/2}$ as required.


**Remarks.** Notice that if $t\geq 3$ on some step, then the estimate makes less by a factor of at most $3/4$. On the other hand, if in some deleted column we have more than $t$ ones (for $t=1$ or $t=2$), then the estimate also decreases by at most $\displaystyle\frac{\sqrt2+1}2<\frac34$. In particular, one may see that this estimate can be tighten for all odd $\delta$.


Right now I do not see how to extend this for larger values of $k$; but it may happen that the optimal example still consists of several blocks on the diagonal of almost the same size.


