# Number of distinct permutations of first n integers by making exactly k swaps

Imagine that we have the $n$ distinct integers ${1,2,...,n}$ arranged in that order initially. How many distinct permutations of this initial arrangement can be obtained by making exactly $k$ swaps among these integers? Here $1 \le k \le n-1$.

I have observed that for $k=1$, the answer is $n(n-1)/2$ since every pair of elements that we chose to swap as the intial swap gives us a unique arrangement.

How do I extend this for $k \gt 1$ ? Is is possible to obtain a "nice" formula for this?

• When $k=2$, it's ${1\over2}{n\choose2}{n-2\choose2}+2{n\choose3}$. Sep 18, 2016 at 12:33
• Thanks @BarryCipra ! Any idea on how to extend this to $k\ge3$ ? Sep 18, 2016 at 12:47
• For any finite $k$, you can, in principle, work out a "nice" formula by carefully considered the combinatorial possibilities, but the approach clearly gets complicated quite quickly. I'm reasonably confident I could work out a formula for $k=3$, but not at all confident the formula would be correct.... Sep 18, 2016 at 20:04
• That is what I was thinking! At least a recursive formula might be of value here! Sep 19, 2016 at 4:22

I know it's a pretty late answer, but we have a recursive formula.

Let $$dp_{i,j}$$ be the number of distinct permutations of length $$i$$ we can get by using exactly $$j$$ swaps (note that permutations that we can get using $$j-2k$$ for some $$k$$ swaps are not counted here).

We have $$dp_{i,j} = dp_{{i-1},j} + (i - 1)\cdot dp_{{i-1},{j-1}}$$.

And $$ans_{n,k} = dp_{n,k} + \displaystyle\sum_{i=0}^{\left\lfloor\frac{k} {2}\right\rfloor} dp_{n,k-2\cdot i}$$

Therefore, we have an $$\mathcal{O}(nk)$$ algorithm to compute the answer, note that I also have an $$\mathcal{O}(k^3\log{n})$$ algorithm, let me know if you are interested in it, it could also be possible that there exists a faster algorithm.

P.S. Notice that $$dp_{i,j} = \begin{bmatrix} i \\ i - j \end{bmatrix} = \displaystyle\sum_{0 < i_1 < \dots < i_k < i}i_1i_2\dots i_k$$

• What is the meaning of the index $i$ in $dp_{i,j}$? Isn't your PS the actual answer to the question (if correct)? Mar 30 at 5:37
• Sorry, forgot to mention it, it represents the length of the permutation. Not sure I understand your second question Mar 31 at 6:56
• OK, now what is the length of a permutation? I thought that $i$ has a different meaning, so that $dp_{i,j}$ were the desired quantity. Mar 31 at 8:54