Contar parejas cuando una persona puede formar pareja como máximo con una

Considere una competencia de codificación sobre la práctica de geeksforgeeks . Ahora hay n participantes distintos participando en la competencia. Un solo participante puede formar pareja como máximo con otro participante. Necesitamos contar el número de formas en que n participantes participan en la competencia de codificación.
Ejemplos: 
 

Input : n = 2
Output : 2
2 shows that either both participant 
can pair themselves in one way or both 
of them can remain single.

Input : n = 3 
Output : 4
One way : Three participants remain single
Three More Ways : [(1, 2)(3)], [(1), (2,3)]
and [(1,3)(2)]

1) Cada participante puede emparejarse con otro participante o permanecer soltero. 
2) Consideremos al X-ésimo participante, puede permanecer soltero o 
puede emparejarse con alguien de [1, x-1] .
 

// Number of ways in which participant can take part.
#include<iostream>
using namespace std;
 
int numberOfWays(int x)
{
    // Base condition
    if (x==0 || x==1)    
        return 1;
 
    // A participant can choose to consider
    // (1) Remains single. Number of people
    //     reduce to (x-1)
    // (2) Pairs with one of the (x-1) others.
    //     For every pairing, number of people
    //     reduce to (x-2).
    else
        return numberOfWays(x-1) +
               (x-1)*numberOfWays(x-2);
}
 
// Driver code
int main()
{
    int x = 3;
    cout << numberOfWays(x) << endl;
    return 0;
}

// Number of ways in which
// participant can take part.
import java.io.*;
 
class GFG {
 
static int numberOfWays(int x)
{
    // Base condition
    if (x==0 || x==1)    
        return 1;
 
    // A participant can choose to consider
    // (1) Remains single. Number of people
    //     reduce to (x-1)
    // (2) Pairs with one of the (x-1) others.
    //     For every pairing, number of people
    //     reduce to (x-2).
    else
        return numberOfWays(x-1) +
            (x-1)*numberOfWays(x-2);
}
 
// Driver code
public static void main (String[] args) {
int x = 3;
System.out.println( numberOfWays(x));
     
    }
}
 
// This code is contributed by vt_m.

# Python program to find Number of ways
# in which participant can take part.
 
# Function to calculate number of ways.
def numberOfWays (x):
 
    # Base condition
    if x == 0 or x == 1:
        return 1
         
    # A participant can choose to consider
    # (1) Remains single. Number of people
    # reduce to (x-1)
    # (2) Pairs with one of the (x-1) others.
    # For every pairing, number of people
    # reduce to (x-2).
    else:
        return (numberOfWays(x-1) +
              (x-1) * numberOfWays(x-2))
 
# Driver code
x = 3
print (numberOfWays(x))
 
# This code is contributed by "Sharad_Bhardwaj"

// Number of ways in which
// participant can take part.
using System;
 
class GFG {
 
    static int numberOfWays(int x)
    {
         
        // Base condition
        if (x == 0 || x == 1)
            return 1;
     
        // A participant can choose to
        // consider (1) Remains single.
        // Number of people reduce to
        // (x-1) (2) Pairs with one of
        // the (x-1) others. For every
        // pairing, number of people
        // reduce to (x-2).
        else
            return numberOfWays(x - 1) +
            (x - 1) * numberOfWays(x - 2);
    }
     
    // Driver code
    public static void Main ()
    {
        int x = 3;
         
        Console.WriteLine(numberOfWays(x));
    }
}
 
// This code is contributed by vt_m.

<?php
// Number of ways in which
// participant can take part.
 
function numberOfWays($x)
{
    // Base condition
    if ($x == 0 || $x == 1)    
        return 1;
 
    // A participant can choose
    // to consider (1) Remains single.
    // Number of people reduce to (x-1)
    // (2) Pairs with one of the (x-1)
    // others. For every pairing, number
    // of peopl reduce to (x-2).
    else
        return numberOfWays($x - 1) +
            ($x - 1) * numberOfWays($x - 2);
}
 
// Driver code
$x = 3;
echo numberOfWays($x);
 
// This code is contributed by Sam007
?>

<script>
// Number of ways in which
// participant can take part.
 
    function numberOfWays(x)
    {
     
        // Base condition
        if (x == 0 || x == 1)
            return 1;
 
        // A participant can choose to consider
        // (1) Remains single. Number of people
        // reduce to (x-1)
        // (2) Pairs with one of the (x-1) others.
        // For every pairing, number of people
        // reduce to (x-2).
        else
            return numberOfWays(x - 1) + (x - 1) * numberOfWays(x - 2);
    }
 
    // Driver code
    var x = 3;
    document.write(numberOfWays(x));
 
// This code is contributed by gauravrajput1
</script>

Producción : 
 

4

Como hay subproblemas superpuestos, podemos optimizarlo usando programación dinámica . 
 

// Number of ways in which participant can take part.
#include<iostream>
using namespace std;
 
int numberOfWays(int x)
{
    int dp[x+1];
    dp[0] = dp[1] = 1;
 
    for (int i=2; i<=x; i++)
       dp[i] = dp[i-1] + (i-1)*dp[i-2];
 
    return dp[x];
}
 
// Driver code
int main()
{
    int x = 3;
    cout << numberOfWays(x) << endl;
    return 0;
}

// Number of ways in which
// participant can take part.
import java.io.*;
class GFG {
 
static int numberOfWays(int x)
{
    int dp[] = new int[x+1];
    dp[0] = dp[1] = 1;
 
    for (int i=2; i<=x; i++)
    dp[i] = dp[i-1] + (i-1)*dp[i-2];
 
    return dp[x];
}
 
// Driver code
public static void main (String[] args) {
int x = 3;
System.out.println(numberOfWays(x));
     
    }
}
// This code is contributed by vipinyadav15799

# Python program to find Number of ways
# in which participant can take part.
 
# Function to calculate number of ways.
def numberOfWays (x):
 
    dp=[]
    dp.append(1)
    dp.append(1)
    for i in range(2,x+1):
        dp.append(dp[i-1]+(i-1)*dp[i-2])
    return(dp[x])
     
 
# Driver code
x = 3
print (numberOfWays(x))
 
# This code is contributed by "Sharad_Bhardwaj"

// Number of ways in which
// participant can take part.
using System;
 
class GFG {
 
    static int numberOfWays(int x)
    {
        int []dp = new int[x+1];
        dp[0] = dp[1] = 1;
     
        for (int i = 2; i <= x; i++)
            dp[i] = dp[i - 1] +
                 (i - 1) * dp[i - 2];
     
        return dp[x];
    }
     
    // Driver code
    public static void Main ()
    {
        int x = 3;
         
        Console.WriteLine(numberOfWays(x));
    }
}
 
// This code is contributed by vt_m. 

<?php
// PHP program for Number of ways
// in which participant can take part.
 
function numberOfWays($x)
{
     
    $dp[0] = 1;
    $dp[1] = 1;
    for ($i = 2; $i <= $x; $i++)
    $dp[$i] = $dp[$i - 1] + ($i - 1) *
                         $dp[$i - 2];
 
    return $dp[$x];
}
 
    // Driver code
    $x = 3;
    echo numberOfWays($x) ;
     
// This code is contributed by Sam007
?>

<script>
// Number of ways in which
// participant can take part.
 
    function numberOfWays( x)
    {
        let dp = Array(x + 1).fill(0);
        dp[0] = dp[1] = 1;
 
        for ( i = 2; i <= x; i++)
            dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
 
        return dp[x];
    }
 
    // Driver code
    let x = 3;
    document.write(numberOfWays(x));
 
// This code is contributed by gauravrajput1
</script>

Producción: 
 

4

Este artículo es una contribución de nikunj_agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.