Recuento de formas en que N elementos pueden formar dos conjuntos diferentes que contienen N/2 elementos cada uno

Dado un número N , que representa el conteo de elementos y es igual a 2K , la tarea es encontrar la cantidad de formas en que estos elementos pueden formar 2 conjuntos que contienen K elementos cada uno.

Ejemplos:

Entrada: N = 4
Salida: 3
Explicación: Los 3 conjuntos que constan de 2 (= N/2) elementos son:
             [1, 2], [3, 4]
             [1, 3], [2, 4]
             [1, 4], [2, 3]           

Entrada: N = 20
Salida: 12164510040883200

Planteamiento: Se debe observar que el concepto de combinaciones tiene que aplicarse para elegir los elementos para cada conjunto.
Se sabe que el número de formas de elegir r cosas de un total de n cosas está dado por:

^{nC _{r = n!/(nr)!*r!}} 
 

Ahora, la fórmula anterior se puede modificar para resolver el problema dado:

• Aquí, se deben elegir N/2 elementos de N elementos para formar cada conjunto. Por lo tanto, r = N/2 .
• Cabe señalar que el mismo elemento no puede estar presente simultáneamente en los dos conjuntos. Entonces, la fórmula de ⁿ C _r tiene que dividirse por 2.
• ¡ Además, el elemento presente en cada conjunto puede organizarse en (N/2-1)! maneras. Como hay dos conjuntos, la fórmula se multiplicará dos veces por este factor.

La fórmula modificada obtenida viene dada por:

Número de vías = ((N! / (N – r)!*r!) / 2) * (N / 2 – 1)!*(N / 2 – 1)! donde r = N / 2

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

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to find the factorial
// of values
long long int fact(long long int N)
{
    // Factorial of 0 is 1
    if (N == 0) {
        return 1;
    }
    else {
 
        // Recursive function call
        return N * fact(N - 1);
    }
}
 
// Driver Code
int main()
{
 
    // Given input
    int N = 20;
 
    // Function Call
    cout << (fact(N) / (fact(N / 2)
                        * fact(N - N / 2)))
                / 2
                * fact(N / 2 - 1)
                * fact(N / 2 - 1);
 
    return 0;
}

// Java code for the above approach
import java.io.*;
class GFG
{
   
    // Function to find the factorial
    // of values
    static long fact(long N)
    {
       
        // Factorial of 0 is 1
        if (N == 0) {
            return 1;
        }
        else {
 
            // Recursive function call
            return N * fact(N - 1);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given input
        int N = 20;
 
        // Function Call
        System.out.println(
            (fact(N) / (fact(N / 2) * fact(N - N / 2))) / 2
            * fact(N / 2 - 1) * fact(N / 2 - 1));
    }
}
 
// This code is contributed by Potta Lokesh

# python program for the above approach
 
# Function to find the factorial
# of values
def fact(N):
 
    # Factorial of 0 is 1
    if (N == 0):
        return 1
 
    else:
 
        # Recursive function call
        return N * fact(N - 1)
 
# Driver Code
if __name__ == "__main__":
 
    # Given input
    N = 20
 
    # Function Call
    print(int((fact(N) / (fact(N / 2) * fact(N - N / 2))) /
              2 * fact(N / 2 - 1) * fact(N / 2 - 1)))
 
# This code is contributed by rakeshsahni

// C# code for the above approach
using System;
public class GFG
{
   
    // Function to find the factorial
    // of values
    static long fact(long N)
    {
       
        // Factorial of 0 is 1
        if (N == 0) {
            return 1;
        }
        else {
 
            // Recursive function call
            return N * fact(N - 1);
        }
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        // Given input
        int N = 20;
 
        // Function Call
        Console.WriteLine(
            (fact(N) / (fact(N / 2) * fact(N - N / 2))) / 2
            * fact(N / 2 - 1) * fact(N / 2 - 1));
    }
}
 
// This code is contributed AnkThon

<script>
// Javascript program for the above approach
 
// Function to find the factorial
// of values
function fact(N)
{
 
    // Factorial of 0 is 1
    if (N == 0) {
        return 1;
    }
    else {
 
        // Recursive function call
        return N * fact(N - 1);
    }
}
 
// Driver Code
 
// Given input
let N = 20;
 
// Function Call
document.write((fact(N) / (fact(N / 2)
                * fact(N - N / 2)))
            / 2
            * fact(N / 2 - 1)
            * fact(N / 2 - 1));
             
// This code is contributed by Samim Hossain Mondal.
</script>

12164510040883200

Complejidad temporal: O(N)
Espacio auxiliar: O(N)