### flame_boy's blog

By flame_boy, 5 months ago,

Given an array of first n natural numbers. Calculate number of total permutations with exactly k pairs satisfy the condition a[i]<a[j] and i<j.

Example — n = 3, k = 2

All permutations — [1,2,3][1,3,2][2,1,3][2,3,1][3,2,1][3,1,2]

Output — 2 ([2,1,3][1,3,2])

• +1

 » 5 months ago, # | ← Rev. 2 →   -11 Check this. The solution to your problem is $\frac{n(n - 1)}{2} - S$ where $S$ is the number of inversions.
•  » » 5 months ago, # ^ |   0 But above solution does not guarantee exactly k number of required pairs
•  » » » 5 months ago, # ^ |   0 Can it be solved using dp?
•  » » » 5 months ago, # ^ |   0 are you sure? check again
•  » » » » 5 months ago, # ^ |   0 Yes
•  » » » » » 5 months ago, # ^ |   0 True
 » 5 months ago, # | ← Rev. 2 →   +18 I don't know if there is a close formula, probably you can get something doing some algebra with generating functions, but since I haven't found anything I'll just explain a no brainer solution.Notice that the generating function of the number of inversions is (1+$x$)(1+$x$+$x^2$)...(1+$x$+...+$x^{n-1}$).Just use d&c NTT and output the $k$-th term in $O(n^2log^2n)$.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +8 For smaller $k$ you can actually solve it in $\mathcal{O}(k \log k)$. You need to find $\dfrac{(1-x)(1-x^2) \cdots (1-x^n)}{(1-x)^n}$. The numerator can be found by finding it's $ln$ (in $\mathcal{O}(k \log n)$, since $ln(1-x^n)$ has only $k/n$ non-zero coefficients before $k$) and finding it's exponent, then we'll only need to divide it by the denominator, so for $k > n$ it's $\mathcal{O}(k \log k)$. I doudt it can be done faster than $\mathcal{O}(k)$, so I think it's pretty close to optimal.
 » 5 months ago, # |   0 maybe this will help(dp O(n^3)): https://cses.fi/problemset/result/8023530/
•  » » 4 weeks ago, # ^ |   0 Hey, can you please share the problem and solution again, this link is not working.@ravenr
•  » » » 2 weeks ago, # ^ |   0 Bit late, but here it is: https://ideone.com/kLkpPi, prob https://cses.fi/problemset/task/2229/
 » 2 weeks ago, # |   0 Imagine a permutation of elements $1,2,\ldots,n-1$ with $k'$ desired pairs then inserting $n$ in the position $k-k'$. This will make it a permutation of $1,2,\ldots,n$ with exactly $k$ desired pairs. (only possible if $0 \leq k-k' \leq n$ or in other words, $k-n \leq k' \leq k$)You can count with DP in $O(nk)$, which is technically $O(n^{3})$ since $k \leq n^{2}$.Pseudocode: fn dp(n, k) { if k < 0 { return 0 } if k == 0 { return 1 } ans = 0 for k' = k-n ... k { ans += dp(n-1, k') } return ans }