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"

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

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter