Number of permutation with K inversions | C # program to find number of permutation with K inversion using Memoization ; Limit on N and K ; 2D array memo for stopping solving same problem again ; method recursively calculates permutation with K inversion ; base cases ; if already solved then return result directly ; calling recursively all subproblem of permutation size N - 1 ; Call recursively only if total inversion to be made are less than size ; store result into memo ; Driver Code
using System ; class GFG { static int M = 100 ; static int [ , ] memo = new int [ M , M ] ; static int numberOfPermWithKInversion ( int N , int K ) { if ( N == 0 ) return 0 ; if ( K == 0 ) return 1 ; if ( memo [ N , K ] != 0 ) return memo [ N , K ] ; int sum = 0 ; for ( int i = 0 ; i <= K ; i ++ ) { if ( i <= N - 1 ) sum += numberOfPermWithKInversion ( N - 1 , K - i ) ; } memo [ N , K ] = sum ; return sum ; } static public void Main ( ) { int N = 4 ; int K = 2 ; Console . WriteLine ( numberOfPermWithKInversion ( N , K ) ) ; } }