Tutorialspoint.dev

Counting pairs when a person can form pair with at most one

Consider a coding competition on . Now their are n distinct participants taking part in the competition. A single participant can make pair with at most one other participant. We need count the number of ways in which n participants participating in the coding competition.

Examples :

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) Every participant can either pair with another participant or can remain single.
2) Let us consider X-th participant, he can either remain single or
he can pair up with someone from [1, x-1].

C++

// 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;

Java

// 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.

Python3

# 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"

/div>

C#

// 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

<?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
?>


Output :

4

Since there are overlapping subproblems, we can optimize it using dynamic programming.

C++

// 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;

Java

// 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 vt_m.

Python3

# 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"

C#

// 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
// 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
?>


Output:

4

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter