Number of recursive permutations of all sizes Consider you have a set of $n$ elements. Now, create all the possible permutations of $k$ elements. Finally, for each permutation create all the possible combinations with the permutations of the remaining $n-k$ elements of the original set (recursive permutations). For example $S = \{1, 2, 3\}$, with $k = 1$, we would have:
$$\{1\} \rightarrow \{2, 3\} \\
\{1\} \rightarrow \{3, 2\} \\
\{2\} \rightarrow \{1, 3\} \\
\{2\} \rightarrow \{3, 1\} \\
\{3\} \rightarrow \{1, 2\} \\
\{3\} \rightarrow \{2, 1\} \\
$$
Now we can apply the same idea to the permutations of the $n-k$ elements, thus why I call it recursive permutation. So if we consider the case $n = 4$ $k = 1$ , we would have for all $k_r$ of the $n-k$ set:
$k_r = 3$
$$
\{1\} \rightarrow \{2, 3, 4\}\\
\{1\} \rightarrow \{2, 4, 3\} \\
\{1\} \rightarrow \{3, 2, 4\} \\
\{1\} \rightarrow \{3, 4, 2\} \\
\{1\} \rightarrow \{4, 2, 3\} \\
\{1\} \rightarrow \{4, 3, 2\} \\
$$
$k_r=2$
$$
\{1\} \rightarrow \{2, 3\}\rightarrow \{4\} \\
\{1\} \rightarrow \{3, 2\}\rightarrow \{4\}
$$
... and so on and so forth.
What is the total number of recursive permutations for all values of $k$ at all recursion levels, where $1<k\leq n$?
 A: Hint: imagine we have lined paper, like college ruled notebook paper, and we write the list of our permutations such that the line always occurs between the $k^{th}$ and $(k+1)^{st}$ entry of the permutation.
What do you notice about the similarity between:
$\begin{array}{cc|cc} 1&2&3&4\\1&2&4&3\\1&3&2&4\\1&3&4&2\\\vdots\end{array}$ and $\begin{array}{c}\{1,2\}\rightarrow \{3,4\}\\ \{1,2\}\rightarrow \{4,3\}\\ \{1,3\}\rightarrow \{2,4\}\\ \{1,3\}\rightarrow\{4,2\}\\\vdots\end{array}$
Do you expect there to be more of one type than the other?

Assuming that you are curious about all possible ways of writing a permutation with any number of braces and arrows and each section of any size but zero: e.g. for $n=3$ we are curious for things of the form $\{1,2,3\}, \{1\}\rightarrow \{2\}\rightarrow \{3\}$, $\{1,2\}\rightarrow\{3\}$, $\{1\}\rightarrow\{2,3\}$
Break up via multiplication principle:


*

*pick the order of the numbers: ($n!$ options)

*pick which spaces (if any) arrows/braces are placed: ($2^{n-1}$ options)


*

*if you want at least one arrow, remove one from the number of options in the previous step for instead $2^{n-1} - 1$ options



There are then $n!2^{n-1}$ such arrangements (or $n!(2^{n-1}-1)$ such arrangements if ignoring case of no arrows).
