Count the number of special permutations

0 0 13 minutes read

Given two positive integers n and k, the task is to count the number of special permutations. A special permutation P is defined as a permutation of first n natural numbers in which there exists at least (n – k) indices such that P_i = i.
Prerequisite: Derangements

Examples:

Input: n = 4, k = 2
Output: 7
{1, 2, 3, 4}, {1, 2, 4, 3}, {4, 2, 3, 1}, {2, 1, 3, 4}, {1, 4, 3, 2}, {1, 3, 2, 4} and {3, 2, 1, 4} are the only possible special permutations.

Input: n = 5, k = 3
Output: 31

Approach: Let the function f_x denote the number of special permutations in which there exists exactly x indices such that P_i = i. Hence, the required answer will be:

f_{(n – k)} + f_{(n – k + 1)} + f_{(n – k + 2)} + … + f_{(n – 1)} + f_n

Now, f_x can be calculated by choosing x indices from n where P_i = i and calculating the number of derangements for (n – i) other indices as for them P_i should not be equal to i then multiplying the result by ⁿC_x as there can be different ways to select x indices from n.

Steps to solve the problem:

Define a function nCr to calculate the number of combinations of n items taken r at a time using the formula n! / (r! * (n-r)!)
Define a function countDerangements to calculate the number of derangements of n items using the formula der(n) = (n-1) * (der(n-1) + der(n-2)) where der(0) = 1 and der(1) = 0.
Define a function countPermutations to calculate the number of permutations of n items where no more than k items are in their original positions using the following steps.
- Initialize a variable ans to 0.
- Loop through i from n-k to n.
- Calculate the number of ways to choose i items from n items using the nCr function.
- Calculate the number of derangements of n-i items using the countDerangements function.
- Multiply the number of ways and the number of derangements and add the result to and.
- Return ans as the result of the function.

Below is the implementation of the above approach:

C++

// C++ program to count the number
// of required permutations
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to return the number of ways
// to choose r objects out of n objects
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;
}
 
// Function to return the number
// of derangements of n
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];
}
 
// Function to return the required
// number of permutations
ll countPermutations(int n, int k)
{
    ll ans = 0;
    for (int i = n - k; i <= n; i++) {
 
        // Ways to choose i indices from n indices
        int ways = nCr(n, i);
 
        // Derangements of (n - i) indices
        ans += ways * countDerangements(n - i);
    }
    return ans;
}
 
// Driver Code to test above functions
int main()
{
    int n = 5, k = 3;
    cout << countPermutations(n, k);
    return 0;
}

Java

// Java program to count the number 
// of required permutations
     
public class GFG{
     
    // Function to return the number of ways 
    // to choose r objects out of n objects 
    static 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; 
    } 
     
    // Function to return the number 
    // of derangements of n 
    static int countDerangements(int n) 
    { 
        int der[] = new int[ n + 3]; 
     
        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]; 
    } 
     
    // Function to return the required 
    // number of permutations 
    static int countPermutations(int n, int k) 
    { 
        int ans = 0; 
        for (int i = n - k; i <= n; i++) { 
     
            // Ways to choose i indices from n indices 
            int ways = nCr(n, i); 
     
            // Derangements of (n - i) indices 
            //System.out.println(ans) ;
            ans += (ways * countDerangements(n- i)); 
        } 
        return ans; 
    } 
     
    // Driver Code to test above functions 
    public static void main(String []args)
    { 
        int n = 5, k = 3; 
        System.out.println(countPermutations(n, k)) ;
    } 
    // This code is contributed by Ryuga
}

Python3

# Python 3 program to count the number
# of required permutation
 
# function to return the number of ways 
# to chooser objects out of n objects
def nCr(n, r):
    ans = 1
    if r > n - r:
        r = n - r
    for i in range(r):
        ans *= (n - i)
        ans /= (i + 1)
    return ans
 
# function to return the number of
# degrangemnets of n
def countDerangements(n):
    der = [0 for i in range(n + 3)]
     
    der[0] = 1
    der[1] = 0
    der[2] = 1
     
    for i in range(3, n + 1):
        der[i] = (i - 1) * (der[i - 1] +
                            der[i - 2])
         
    return der[n]
 
# function to return the required 
# number of permutations
def countPermutations(n, k):
    ans = 0
    for i in range(n - k, n + 1):
         
        # ways to choose i indices 
        # from n indices
        ways = nCr(n, i)
         
        # Derangements of (n-i) indices
        ans += ways * countDerangements(n - i)
    return ans
 
# Driver Code
n, k = 5, 3
 
print(countPermutations(n, k))
 
# This code is contributed by
# Mohit kumar 29 (IIIT gwalior)

C#

     
// C# program to count the number 
// of required permutations
using System;    
public class GFG{
      
    // Function to return the number of ways 
    // to choose r objects out of n objects 
    static 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; 
    } 
      
    // Function to return the number 
    // of derangements of n 
    static int countDerangements(int n) 
    { 
        int []der = new int[ n + 3]; 
      
        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]; 
    } 
      
    // Function to return the required 
    // number of permutations 
    static int countPermutations(int n, int k) 
    { 
        int ans = 0; 
        for (int i = n - k; i <= n; i++) { 
      
            // Ways to choose i indices from n indices 
            int ways = nCr(n, i); 
      
            // Derangements of (n - i) indices 
            //System.out.println(ans) ;
            ans += (ways * countDerangements(n- i)); 
        } 
        return ans; 
    } 
      
    // Driver Code to test above functions 
    public static void Main()
    { 
        int n = 5, k = 3; 
        Console.WriteLine(countPermutations(n, k)) ;
    } 
}
// This code is contributed by 29AjayKumar

Javascript

<script>
 
      // JavaScript program to count the number
      // of required permutations
      // Function to return the number of ways
      // to choose r objects out of n objects
      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 to return the number
      // of derangements of n
      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 to return the required
      // number of permutations
      function countPermutations(n, k) {
        var ans = 0;
        for (var i = n - k; i <= n; i++) {
          // Ways to choose i indices from n indices
          var ways = nCr(n, i);
 
          // Derangements of (n - i) indices
          ans += ways * countDerangements(n - i);
        }
        return ans;
      }
 
      // Driver Code to test above functions
      var n = 5,
        k = 3;
      document.write(countPermutations(n, k));
       
</script>

PHP

<?php
// PHP program to count the number
// of required permutations
 
// Function to return the number of ways
// to choose r objects out of n objects
function nCr($n, $r)
{
    $ans = 1;
    if ($r > $n - $r)
        $r = $n - $r;
    for ($i = 0; $i < $r; $i++)
    {
        $ans *= ($n - $i);
        $ans /= ($i + 1);
    }
    return $ans;
}
 
// Function to return the number
// of derangements of n
function countDerangements($n)
{
    $der = array($n + 1);
 
    $der[0] = 1;
    $der[1] = 0;
    $der[2] = 1;
 
    for ($i = 3; $i <= $n; $i++)
        $der[$i] = ($i - 1) * 
                   ($der[$i - 1] + 
                    $der[$i - 2]);
    return $der[$n];
}
 
// Function to return the required
// number of permutations
function countPermutations($n, $k)
{
    $ans = 0;
    for ($i = $n - $k; $i <= $n; $i++)
    {
 
        // Ways to choose i indices
        // from n indices
        $ways = nCr($n, $i);
 
        // Derangements of (n - i) indices
        $ans += $ways * countDerangements($n - $i);
    }
    return $ans;
}
 
// Driver Code
$n = 5;
$k = 3;
echo (countPermutations($n, $k));
 
// This code is contributed 
// by Shivi_Aggarwal 
?>

Output

Time Complexity: O(N^2), since there runs a loop inside another loop.
Auxiliary Space: O(N), since N extra space has been taken.

Efficient approach : Space optimization O(1)

In previous approach we the current value dp[i] is only depend upon the previous 2 values i.e. dp[i-1] and dp[i-2]. So to optimize the space we can keep track of previous and current values by the help of three variables prev1, prev2 and curr which will reduce the space complexity from O(N) to O(1).

Implementation Steps:

Create 2 variables prev1 and prev2 to keep track o previous values of DP.
Initialize base case prev1 = 0 and prev2 = 1.
Create a variable curr to store current value.
Iterate over subproblem using loop and update curr.
After every iteration update prev1 and prev2 for further iterations.
At last return curr.

Implementation:

C++

// C++ program to count the number
// of required permutations
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to return the number of ways
// to choose r objects out of n objects
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;
}
 
// Function to return the number
// of derangements of n
int countDerangements(int n)
{
    // to store previous values of DP
    int prev0=1 , prev1=0 , prev2=1;
    // to store current value
    int curr;
     
    // Base Case
    if(n == 0)
        return prev0;
    if(n == 1)
        return prev1;
    if(n == 2)
        return prev2;
     
    // iterate over subproblems to gee the current 
    // value from previous computations
    for (int i = 3; i <= n; i++){
        curr = (i-1) * ( prev2 + prev1 ) ;
         
        // assigning values for further iterations
        prev1 = prev2;
        prev2 = curr;
    }
     
    // return answer
    return curr;
}
 
// Function to return the required
// number of permutations
ll countPermutations(int n, int k)
{
    ll ans = 0;
    for (int i = n - k; i <= n; i++) {
 
        // Ways to choose i indices from n indices
        int ways = nCr(n, i);
 
        // Derangements of (n - i) indices
        ans += ways * countDerangements(n - i);
    }
    return ans;
}
 
// Driver Code to test above functions
int main()
{
    int n = 5, k = 3;
    cout << countPermutations(n, k);
    return 0;
}

Java

import java.util.*;
 
public class Main {
 
    // Function to return the number of ways
    // to choose r objects out of n objects
    public static 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;
    }
 
    // Function to return the number
    // of derangements of n
    public static int countDerangements(int n) {
        // to store previous values of DP
        int prev0=1 , prev1=0 , prev2=1;
        // to store current value
        int curr;
         
        // Base Case
        if(n == 0)
            return prev0;
        if(n == 1)
            return prev1;
        if(n == 2)
            return prev2;
         
        // iterate over subproblems to gee the current 
        // value from previous computations
        for (int i = 3; i <= n; i++){
            curr = (i-1) * ( prev2 + prev1 ) ;
             
            // assigning values for further iterations
            prev1 = prev2;
            prev2 = curr;
        }
         
        // return answer
        return prev2;
    }
 
    // Function to return the required
    // number of permutations
    public static long countPermutations(int n, int k) {
        long ans = 0;
        for (int i = n - k; i <= n; i++) {
 
            // Ways to choose i indices from n indices
            int ways = nCr(n, i);
 
            // Derangements of (n - i) indices
            ans += ways * countDerangements(n - i);
        }
        return ans;
    }
 
    // Driver Code to test above functions
    public static void main(String[] args) {
        int n = 5, k = 3;
        System.out.println(countPermutations(n, k));
    }
}

Python

# Python program to count the number
# of required permutations
import math
 
# Function to return the number of ways
# to choose r objects out of n objects
def nCr(n, r):
    ans = 1
    if (r > n - r):
        r = n - r
    for i in range(r):
        ans *= (n - i)
        ans //= (i + 1)
    return ans
 
# Function to return the number
# of derangements of n
def countDerangements(n):
    # to store previous values of DP
    prev0, prev1, prev2 = 1, 0, 1
     
    # Base Case
    if n == 0:
        return prev0
    if n == 1:
        return prev1
    if n == 2:
        return prev2
     
    # iterate over subproblems to get the current 
    # value from previous computations
    for i in range(3, n + 1):
        curr = (i - 1) * (prev2 + prev1)
         
        # assigning values for further iterations
        prev1 = prev2
        prev2 = curr
     
    # return answer
    return curr
 
# Function to return the required
# number of permutations
def countPermutations(n, k):
    ans = 0
    for i in range(n - k, n + 1):
 
        # Ways to choose i indices from n indices
        ways = nCr(n, i)
 
        # Derangements of (n - i) indices
        ans += ways * countDerangements(n - i)
    return ans
 
# Driver Code to test above functions
if __name__ == '__main__':
    n = 5
    k = 3
    print(countPermutations(n, k))

C#

using System;
 
public class Program
{
    // Function to return the number of ways
    // to choose r objects out of n objects
    static 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;
    }
 
    // Function to return the number
    // of derangements of n
    static int CountDerangements(int n)
    {
        // to store previous values of DP
        int prev0 = 1, prev1 = 0, prev2 = 1;
        // to store current value
        int curr = 0; // Initialize curr
 
        // Base Case
        if (n == 0)
            return prev0;
        if (n == 1)
            return prev1;
        if (n == 2)
            return prev2;
 
        // iterate over subproblems to get the current 
        // value from previous computations
        for (int i = 3; i <= n; i++)
        {
            curr = (i - 1) * (prev2 + prev1);
 
            // assigning values for further iterations
            prev1 = prev2;
            prev2 = curr;
        }
 
        // return answer
        return curr;
    }
 
    // Function to return the required
    // number of permutations
    static long CountPermutations(int n, int k)
    {
        long ans = 0;
        for (int i = n - k; i <= n; i++)
        {
            // Ways to choose i indices from n indices
            int ways = nCr(n, i);
 
            // Derangements of (n - i) indices
            ans += ways * CountDerangements(n - i);
        }
        return ans;
    }
 
    // Driver Code
    public static void Main()
    {
        int n = 5, k = 3;
        Console.WriteLine(CountPermutations(n, k));
    }
}

Javascript

// Function to return the number of ways
// to choose r objects out of n objects
function nCr(n, r) {
    let ans = 1;
    if (r > n - r)
        r = n - r;
    for (let i = 0; i < r; i++) {
        ans *= (n - i);
        ans /= (i + 1);
    }
    return ans;
}
 
// Function to return the number
// of derangements of n
function countDerangements(n) {
    // to store previous values of DP
    let prev0 = 1, prev1 = 0, prev2 = 1;
    // to store current value
    let curr;
 
    // Base Case
    if (n === 0)
        return prev0;
    if (n === 1)
        return prev1;
    if (n === 2)
        return prev2;
 
    // iterate over subproblems to get the current 
    // value from previous computations
    for (let i = 3; i <= n; i++) {
        curr = (i - 1) * (prev2 + prev1);
 
        // assigning values for further iterations
        prev1 = prev2;
        prev2 = curr;
    }
 
    // return answer
    return curr;
}
 
// Function to return the required
// number of permutations
function countPermutations(n, k) {
    let ans = 0;
    for (let i = n - k; i <= n; i++) {
 
        // Ways to choose i indices from n indices
        let ways = nCr(n, i);
 
        // Derangements of (n - i) indices
        ans += ways * countDerangements(n - i);
    }
    return ans;
}
 
// Driver Code to test above functions
let n = 5, k = 3;
console.log(countPermutations(n, k));

Output

Time Complexity: O(N^2), since there runs a loop inside another loop.
Auxiliary Space: O(1), since no extra space is used.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!