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