Count the number of special permutations | C ++ program to count the number of required 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE int nCr ( int n , int r ) { int ans = 1 ; if ( r > n - r ) r = n - r ; for ( int i = 0 ; i < r ; i ++ ) { ans *= ( n - i ) ; ans /= ( i + 1 ) ; } return ans ; } int countDerangements ( int n ) { int der [ n + 1 ] ; der [ 0 ] = 1 ; der [ 1 ] = 0 ; der [ 2 ] = 1 ; for ( int i = 3 ; i <= n ; i ++ ) der [ i ] = ( i - 1 ) * ( der [ i - 1 ] + der [ i - 2 ] ) ; return der [ n ] ; } ll countPermutations ( int n , int k ) { ll ans = 0 ; for ( int i = n - k ; i <= n ; i ++ ) { int ways = nCr ( n , i ) ; ans += ways * countDerangements ( n - i ) ; } return ans ; } int main ( ) { int n = 5 , k = 3 ; cout << countPermutations ( n , k ) ; return 0 ; }