0
$\begingroup$

Given a list {1,2,3,4,5}. There are 5!=120 permutations of {1,2,3,4,5}. Every permutation can be written as the product of cycles ("factors"), for instance the permutation {1,2,3,4,5}→{2,1,3,5,4} can be written (1,2)(3)(4,5). This is typically written as (1,2)(4,5), the product of two interchanges. Thus this particular permutation requires 2 element interchanges. All permutations are computed from the identity permutation {1,2,3,4,5}, in other words going from one permutation to another is not legal.

Question: If we wrote out all 120 permutations as such cycles, in total how many interchanges of two would we find?

Edit: I did some programming and simulated this question. I found that 326 transpositions are required. If anybody has the analytical answer to this, it would be much appreciated.

$\endgroup$
15
  • $\begingroup$ like permuting $1$ with $2$, $1$ with $3$, $1$ with $4$, and $1$ with $5$? (or $1$ with $2$, $2$ with $3$, $3$ with $4$, and $4$ with $5$?) cf. this Wikipedia information $\endgroup$ Apr 22, 2020 at 17:08
  • $\begingroup$ "how many permutations of 2" I don't understand what you mean by this. Are you perhaps asking for a minimal set of transpositions which generate the group $S_5$? $\endgroup$
    – JMoravitz
    Apr 22, 2020 at 17:09
  • $\begingroup$ @JMoravitz: I think OP indeed means a $2$-cycle; cf. OP's usage of "permutations of $5$" $\endgroup$ Apr 22, 2020 at 17:12
  • $\begingroup$ This question is poorly posed. I think the OP is asking: There are $120$ permutations of $\{ 1,2,3,4,5 \}$. Every permutation can be written as the product of cycles ("factors"), for instance the permutation $\{1,2,3,4,5\} \to \{ 2,1,3,5,4 \}$ can be written $(1,2)(3)(4,5)$. This is typically written as $(1,2)(4,5)$... the product of two interchanges. Thus this particular permutation requires 2 element interchanges. Q: If we wrote out all 120 permutations as such cycles, in total how many interchanges of two would we find? (These are sometimes called permutation factors.) $\endgroup$ Apr 22, 2020 at 17:22
  • 1
    $\begingroup$ @JanMarxen: What have you tried? $\endgroup$ Apr 22, 2020 at 17:28

1 Answer 1

0
$\begingroup$

Here's one approach to the problem, based (loosely) on generating functions. First of all, note that all the permutations of a set of $n$ elements can be obtained by starting with all the permutations of a set of $n-1$ elements, placing the new element at the end of each permutation, and then swapping it with the element at position $i$ for $i=1\ldots n$ (note that the last 'swap' here is just swapping it with itself; this essentially corresponds to just appending $(n)$ to the cycle notation for the previous permutation). (The $n$ possible swaps for the new element mean that the total number of permutations, $P_n$, satisfies $P_n=n\cdot P_{n-1}$, giving $P_n=n!$, just as you'd expect.) Now, when we generate our new permutations this way, there are two distinct ways that we can get a two-cycle. Either it can exist in the 'parent' permutation, and then the new element has to be swapped with something other than it; or it can involve the new element swapping with an element in the parent permutation that was fixed by the parent permutation. Since there's some dependency among these items, I'm going to write $p_{i,j;n}$ for the number of permutations of $n$ things with $i$ fixed points and $j$ two-cycles.

Now, let's consider the ways in which the new element corresponding to $n$ can be inserted into a permutation that's a member of $p_{i,j;n-1}$. It can be a new fixed point; this creates a permutation in $p_{(i+1),j;n}$. It can swap with one of the $i$ fixed points of the permutation, creating $i$ different permutations in $p_{i-1,j+1;n}$. Or it can swap with one of the $2j$ elements that was in a two-cycle in the previous permutation, creating $2j$ different permutations in $p_{i,j-1;n}$. Or it can swap with one of the $n-(i+2j+1)$ elements that's in a longer cycle, in which case neither $i$ nor $j$ change and we have $n-(i+2j+1)$ new permutations in $p_{i,j;n}$.

Now, we can 'reverse-engineer' this: if we have a permutation in $p_{i,j;n}$, then there's one way it could have come from a permutation in $p_{i-1,j;n-1}$. There are $(i+1)$ ways it could have come from a permutation in $p_{i+1,j-1;n-1}$. There are $(2j+2)$ ways it could have come from a permutation in $p_{i,j+1;n-1}$. And there are $n-(i+2j+1)$ ways it could have come from a permutation in $p_{i,j;n-1}$. In other words, we have the recurrence relation:

$$p_{i,j;n} = p_{i-1,j;n-1}+(i+1)p_{i+1,j-1;n-1}+(2j+2)p_{i,j+1;n-1}+(n-(i+2j+1))p_{i,j;n-1}$$

Now, if we imagine writing the polynomial $p_n(s,t)=\sum_{i,j}p_{i,j;n}s^it^j$, then the coefficients in the recurrence relation can be broken down as follows: $p_{i-1,j;n-1}s^it^j$ corresponds to a term $sp_{n-1}(s,t)$ (since it's $s\cdot p_{i-1, j;n-1}s^{i-1}t^j$ and we can renumber the indices). Similarly, the term $(i+1)p_{i+1,j-1;n-1} s^it^j$ corresponds to a term $t\frac{\partial}{\partial s}p_{n-1}(s,t)$; applying the (partial) derivative accounts for the presence of $i+1$, and multiplying by $t$ shifts the $j$-index. Likewise, the $(2j+2)p_{i,j+1;n-1}s^it^j$ term corresponds to a term $2\frac{\partial}{\partial t}p_{n-1}(s,t)$.

Finally, there's the term $n-(i+2j+1)p_{i,j;n-1}$. I'll write this as $(n-1)p_{i,j;n-1}-ip_{i,j;n-1}-2jp_{i,j;n-1}$. Similarly to the above, these terms correspond to $(n-1)p_{n-1}(i,j)$, $-s\frac{\partial}{\partial s}p_{n-1}(s,t)$; and $-2t\frac{\partial}{\partial t}p_{n-1}(s,t)$. Putting this all together, we have the following polynomial recurrence relation for a partial generating function of the coefficients:

$$p_n(s,t) = sp_{n-1}(s,t)+t\frac{\partial}{\partial s}p_{n-1}(s,t) + 2\frac{\partial}{\partial t}p_{n-1}(s,t)+(n-1)p_{n-1}(s,t)-s\frac{\partial}{\partial s}p_{n-1}(s,t)-2t\frac{\partial}{\partial t}p_{n-1}(s,t)$$

Or, combining terms, $$p_n(s,t) = (s+n-1)p_{n-1}(s,t)+(t-s)\frac{\partial}{\partial s}p_{n-1}(s,t) + (2-2t)\frac{\partial}{\partial t}p_{n-1}(s,t)$$.

Now, you could go a step further than this, and obtain an overall generating function $\mathcal{P}(x;s,t) = \sum_n x^np_n(s,t)$, and get a differential equation for $\mathcal{P}$ relating the partial derivative in $x$ to the other partial derivatives by using the same sort of operations again. This leads to a pretty messy differential equation, and you'll likely need to take much more care with boundary conditions. Still, this approach should in theory get towards the destination.

Finally, once this is together, then the quantity you're interested in, the total number of interchanges among all length n permutations, is $\mathcal{I}_n = \sum_i\sum_j 2jp_{i,j;n}$. In terms of the generating function, this is essentially $2(\frac{\partial}{\partial t}p(s,t)|_{(s,t)=(1,1)})-2p(1,1)$ where the notation in the first term means 'compute the partial derivative as a function, then evaluate it at $s=1,t=1$'.

$\endgroup$
3
  • $\begingroup$ Is the previous permutation n-1 simply a list with less one element? So if we are talking about the list [1,2,3,4,5] it would have to be [1,2,3,4]? $\endgroup$
    – Marx
    Apr 23, 2020 at 8:45
  • $\begingroup$ @Marx The previous permutation specifically here is the one that generates the 'new' permutation via the process I describe at the start of this. So if, for instance, the new permutation is $1\mapsto 3, 2\mapsto 2, 3\mapsto 5, 4\mapsto 1, 5\mapsto 4$ — or, in cycle notation, $(1 3 5 4)(2)$ — then the previous permutation would be $1\mapsto 3, 2\mapsto 2, 3\mapsto 4, 4 \mapsto 1$; in cycle notation, $(1 3 4)(2)$. $\endgroup$ Apr 23, 2020 at 16:17
  • $\begingroup$ I like your idea very much, but I am asking for the number of transposition when all permutations work independently from each other. So one permutation cannot be generated by the last one, nor can more than one permutation be generated from the same "parent" permutation. $\endgroup$
    – Marx
    Apr 23, 2020 at 18:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .