flame_boy's blog

Calculate number of permutations with ai<aj
By flame_boy, 4 months ago, In English

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])

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 months ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

Check this. The solution to your problem is $$$\frac{n(n - 1)}{2} - S$$$ where $$$S$$$ is the number of inversions.

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

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)$$$.

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

maybe this will help(dp O(n^3)): https://cses.fi/problemset/result/8023530/

→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, can you please share the problem and solution again, this link is not working.

    @ravenr

    → Reply
    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bit late, but here it is: https://ideone.com/kLkpPi, prob https://cses.fi/problemset/task/2229/

      → Reply