1

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$?

Arcanefoam
  • 113
  • Do you consider ${1,2}\to {3}$ different than ${2,1}\to {3}$ (for $n=3, k=2$)? – JMoravitz May 24 '16 at 17:26
  • sum of binomial coefficient n choose k.from k=1 to n. equal to the powerset of n.with 2^n elements – shai horowitz May 24 '16 at 17:28
  • @shaihorowitz for starters.. $\sum\limits_{k=1}^n\binom{n}{k} = 2^n - 1$, not $2^n$. You need to start the summation from $k=0$ to have that occur. Secondly, what does that have anything to do with the current problem being asked? – JMoravitz May 24 '16 at 17:34
  • @JMoravitz Yes, the order is important, hence they are different. – Arcanefoam May 24 '16 at 17:41

1 Answers1

0

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).

JMoravitz
  • 79,518
  • I see the pattern. I edited the OP to explain in more detail the idea of the recursive permutation. So I think there is more to it. – Arcanefoam May 24 '16 at 17:49
  • @Arcanefoam Add more or fewer lines to your notebook paper. Does this change the number of ordinary permutations? If you remove all braces and arrows and read one of your "recursive" permutations as an ordinary one, do you ever get the same answer more than once? Do you get every answer at least once? – JMoravitz May 24 '16 at 17:52
  • I see your point. Yes, I would get the same answer more than once and in my case ${1}\rightarrow {2, 3}$ is different from ${1,2}\rightarrow{3}$. But it looks like it boils down to $T^2$, where $T$ is all the number of permutations of $k$ from $n$ for all $k$. – Arcanefoam May 24 '16 at 18:03
  • So, you wish to count all possibilities for $k$, $k_r,\dots$, then for each ordinary permutation, pick where the braces and arrows go. you can think of open spaces between each number where you have the option to place things. For each space, answer "yes" or "no" (two options) for whether there is an arrow and braces there. If you don't want the situation of no arrows, you can correct your count. Depending on what exactly you want, it sounds like perhaps you want the answer $(2^{n-1}-1)n!$ – JMoravitz May 24 '16 at 18:09
  • Thanks! That sounds about right.. will do a couple of manual tests to double check. Would you mind editing your question with this information so I can select it as correct? – Arcanefoam May 24 '16 at 18:31