Encuentre el número de buenas permutaciones

Dados dos enteros N y K . La tarea es encontrar el número de buenas permutaciones de los primeros N números naturales. Una permutación se dice buena si existen al menos N – K índices i (1 ≤ i ≤ N) tales que P _i = i .

Ejemplos: 

Entrada: N = 4, K = 1 
Salida: 1 
{1, 2, 3, 4} es la única permutación buena posible.

Entrada: N = 5, K = 2 
Salida: 11 

Enfoque: iteremos en m , que es el número de índices tales que P _i no es igual a i . Obviamente, 0 ≤ metro ≤ k . 
Para contar el número de permutaciones con m fijo , necesitamos elegir los índices que tienen la propiedad P _i no es igual a i – hay ⁿ C _m formas de hacer esto, entonces necesitamos construir una permutación Q para los índices elegidos tal que para cada índice elegido Q _i no se iguala a i . Las permutaciones con esta propiedad se denominan desarreglos.y el número de trastornos de tamaño fijo puede calcularse mediante una búsqueda exhaustiva de m ≤ 4 .

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of good permutations
int Permutations(int n, int k)
{
    // For m = 0, ans is 1
    int ans = 1;
 
    // If k is greater than 1
    if (k >= 2)
        ans += (n) * (n - 1) / 2;
 
    // If k is greater than 2
    if (k >= 3)
        ans += (n) * (n - 1) * (n - 2) * 2 / 6;
 
    // If k is greater than 3
    if (k >= 4)
        ans += (n) * (n - 1) * (n - 2) * (n - 3) * 9 / 24;
 
    return ans;
}
 
// Driver code
int main()
{
    int n = 5, k = 2;
    cout << Permutations(n, k);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the count of good permutations
static int Permutations(int n, int k)
{
    // For m = 0, ans is 1
    int ans = 1;
 
    // If k is greater than 1
    if (k >= 2)
        ans += (n) * (n - 1) / 2;
 
    // If k is greater than 2
    if (k >= 3)
        ans += (n) * (n - 1) * (n - 2) * 2 / 6;
 
    // If k is greater than 3
    if (k >= 4)
        ans += (n) * (n - 1) * (n - 2) * (n - 3) * 9 / 24;
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 5, k = 2;
    System.out.println(Permutations(n, k));
}
}
 
// This code contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to return the count
# of good permutations
def Permutations(n, k):
 
    # For m = 0, ans is 1
    ans = 1
 
    # If k is greater than 1
    if k >= 2:
        ans += (n) * (n - 1) // 2
 
    # If k is greater than 2
    if k >= 3:
        ans += ((n) * (n - 1) *
                (n - 2) * 2 // 6)
 
    # If k is greater than 3
    if k >= 4:
        ans += ((n) * (n - 1) * (n - 2) *
                      (n - 3) * 9 // 24)
 
    return ans
 
# Driver code
if __name__ == "__main__":
 
    n, k = 5, 2
    print(Permutations(n, k))
     
# This code is contributed
# by Rituraj Jain

// C# implementation of the above approach.
using System;
 
class GFG
{
 
// Function to return the count of good permutations
static int Permutations(int n, int k)
{
    // For m = 0, ans is 1
    int ans = 1;
 
    // If k is greater than 1
    if (k >= 2)
        ans += (n) * (n - 1) / 2;
 
    // If k is greater than 2
    if (k >= 3)
        ans += (n) * (n - 1) * (n - 2) * 2 / 6;
 
    // If k is greater than 3
    if (k >= 4)
        ans += (n) * (n - 1) * (n - 2) * (n - 3) * 9 / 24;
 
    return ans;
}
 
// Driver code
public static void Main()
{
    int n = 5, k = 2;
    Console.WriteLine(Permutations(n, k));
}
}
 
/* This code contributed by PrinciRaj1992 */

<?php
// PHP implementation of the approach
 
// Function to return the count
// of good permutations
function Permutations($n, $k)
{
    // For m = 0, ans is 1
    $ans = 1;
 
    // If k is greater than 1
    if ($k >= 2)
        $ans += ($n) * ($n - 1) / 2;
 
    // If k is greater than 2
    if ($k >= 3)
        $ans += ($n) * ($n - 1) *
                       ($n - 2) * 2 / 6;
 
    // If k is greater than 3
    if ($k >= 4)
        $ans += ($n) * ($n - 1) * ($n - 2) *
                       ($n - 3) * 9 / 24;
 
    return $ans;
}
 
// Driver code
$n = 5; $k = 2;
echo(Permutations($n, $k));
 
// This code contributed by Code_Mech.
?>

<script>
 
// JavaScript implementation of the approach
 
// Function to return the count of good permutations
function Permutations(n, k)
{
     
    // For m = 0, ans is 1
    var ans = 1;
 
    // If k is greater than 1
    if (k >= 2)
        ans += (n) * (n - 1) / 2;
 
    // If k is greater than 2
    if (k >= 3)
        ans += (n) * (n - 1) *
           (n - 2) * 2 / 6;
 
    // If k is greater than 3
    if (k >= 4)
        ans += (n) * (n - 1) * (n - 2) *
                     (n - 3) * 9 / 24;
 
    return ans;
}
 
// Driver Code
var n = 5, k = 2;
document.write(Permutations(n, k));
   
// This code is contributed by Khushboogoyal499
 
</script>

11

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)