This is a problem I asked on http://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?

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?

This is a problem I asked on http://math.stackexchange.com/questions/647382/union-of-permutations. At first I think this is a high school level exercise, but I get troubled. I get this problem in analyzing an algorithm. Feel free to close it if you think it below research level.

Having $k$ different permutations, $\pi_{1},\dots,\pi_{k}$, we write a permutation in one-line nonation, namely $\pi=i_1i_2{\dots}i_n$, that is, $\pi(1)=i_1,\pi(2)=i_2,\dots\pi(n)=i_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 $s$ 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}, 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 permutaions 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 any one know what is the exact answer to this question? Does this condition suggest the optimal case?

This is a problem I asked on http://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?