0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ When $k=2$, it's ${1\over2}{n\choose2}{n-2\choose2}+2{n\choose3}$. $\endgroup$ Sep 18, 2016 at 12:33
  • $\begingroup$ Thanks @BarryCipra ! Any idea on how to extend this to $k\ge3$ ? $\endgroup$ Sep 18, 2016 at 12:47
  • $\begingroup$ 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.... $\endgroup$ Sep 18, 2016 at 20:04
  • $\begingroup$ That is what I was thinking! At least a recursive formula might be of value here! $\endgroup$ Sep 19, 2016 at 4:22

1 Answer 1

0
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ What is the meaning of the index $i$ in $dp_{i,j}$? Isn't your PS the actual answer to the question (if correct)? $\endgroup$ Mar 30 at 5:37
  • $\begingroup$ Sorry, forgot to mention it, it represents the length of the permutation. Not sure I understand your second question $\endgroup$ Mar 31 at 6:56
  • $\begingroup$ 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. $\endgroup$ Mar 31 at 8:54

You must log in to answer this question.

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