Count the number of special permutations | Function to return the number of ways to choose r objects out of n objects ; Function to return the number of derangements of n ; Function to return the required number of permutations ; Ways to choose i indices from n indices ; Dearangements of ( n - i ) indices ; Driver Code to test above functions
function nCr ( n , r ) { var ans = 1 ; if ( r > n - r ) r = n - r ; for ( var i = 0 ; i < r ; i ++ ) { ans *= n - i ; ans /= i + 1 ; } return ans ; } function countDerangements ( n ) { var der = [ ... Array ( n + 1 ) ] ; der [ 0 ] = 1 ; der [ 1 ] = 0 ; der [ 2 ] = 1 ; for ( var i = 3 ; i <= n ; i ++ ) der [ i ] = ( i - 1 ) * ( der [ i - 1 ] + der [ i - 2 ] ) ; return der [ n ] ; } function countPermutations ( n , k ) { var ans = 0 ; for ( var i = n - k ; i <= n ; i ++ ) { var ways = nCr ( n , i ) ; ans += ways * countDerangements ( n - i ) ; } return ans ; } var n = 5 , k = 3 ; document . write ( countPermutations ( n , k ) ) ;