Rencontres Number (Counting partial derangements)

0 0 11 minutes read

Given two numbers, n >= 0 and 0 <= k <= n, count the number of derangements with k fixed points.
Examples:

Input : n = 3, k = 0
Output : 2
Since k = 0, no point needs to be on its
original position. So derangements
are {3, 1, 2} and {2, 3, 1}

Input : n = 3, k = 1
Output : 3
Since k = 1, one point needs to be on its
original position. So partial derangements
are {1, 3, 2}, {3, 2, 1} and {2, 1, 3}

Input : n = 7, k = 2
Output : 924

In combinatorial mathematics, the rencontres number< or D(n, k) represents count of partial derangements.
The recurrence relation to find Rencontres Number D_{n, k}:

D_{(0, 0)} = 1
D_{(0, 1)} = 0
D_{(n+2, 0)} = (n+1) * (D_{(n+1, 0)} + D_{(n, 0)})
D_{(n, k)} = ⁿC_k * D_{(n-k, 0)})

Given the two positive integer n and k. The task is find rencontres number D(n, k) for giver n and k.
Below is Recursive solution of this approach:

C++

// Recursive CPP program to find n-th Rencontres 
// Number
#include <bits/stdc++.h>
using namespace std;
 
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
    // Base Cases
    if (k == 0 || k == n)
        return 1;
 
    // Recurrence relation
    return binomialCoeff(n - 1, k - 1) +
           binomialCoeff(n - 1, k);
}
 
// Return Recontres number D(n, m)
int RencontresNumber(int n, int m)
{
    // base condition
    if (n == 0 && m == 0)
        return 1;
 
    // base condition
    if (n == 1 && m == 0)
        return 0;
 
    // base condition
    if (m == 0)
        return (n - 1) * (RencontresNumber(n - 1, 0) +
                          RencontresNumber(n - 2, 0));
 
    return binomialCoeff(n, m) * RencontresNumber(n - m, 0);
}
 
// Driver Program
int main()
{
    int n = 7, m = 2;
    cout << RencontresNumber(n, m) << endl;
    return 0;
}

Java

// Recursive Java program to find n-th Rencontres
// Number
import java.io.*;
 
class GFG {
     
    // Returns value of Binomial Coefficient
    // C(n, k)
    static int binomialCoeff(int n, int k)
    {
         
        // Base Cases
        if (k == 0 || k == n)
            return 1;
 
        // Recurrence relation
        return binomialCoeff(n - 1, k - 1) + 
                         binomialCoeff(n - 1, k);
    }
 
    // Return Recontres number D(n, m)
    static int RencontresNumber(int n, int m)
    {
         
        // base condition
        if (n == 0 && m == 0)
            return 1;
 
        // base condition
        if (n == 1 && m == 0)
            return 0;
 
        // base condition
        if (m == 0)
            return (n - 1) * (RencontresNumber(n - 1, 0) 
                          + RencontresNumber(n - 2, 0));
 
        return binomialCoeff(n, m) * 
                             RencontresNumber(n - m, 0);
    }
 
    // Driver Program
    public static void main(String[] args)
    {
        int n = 7, m = 2;
        System.out.println(RencontresNumber(n, m));
    }
}
 
// This code is contributed by vt_m.

Python3

# Recursive CPP program to find
# n-th Rencontres Number
 
# Returns value of Binomial Coefficient C(n, k)
def binomialCoeff(n, k):
 
    # Base Cases
    if (k == 0 or k == n):
        return 1
 
    # Recurrence relation
    return (binomialCoeff(n - 1, k - 1) 
          + binomialCoeff(n - 1, k))
 
# Return Recontres number D(n, m)
def RencontresNumber(n, m):
 
    # base condition
    if (n == 0 and m == 0):
        return 1
 
    # base condition
    if (n == 1 and m == 0):
        return 0
 
    # base condition
    if (m == 0):
        return ((n - 1) * (RencontresNumber(n - 1, 0) 
                         + RencontresNumber(n - 2, 0)))
 
    return (binomialCoeff(n, m) *
            RencontresNumber(n - m, 0))
 
# Driver Program
n = 7; m = 2
print(RencontresNumber(n, m))
 
# This code is contributed by Smitha Dinesh Semwal.

C#

// Recursive C# program to find n-th Rencontres
// Number
using System;
 
class GFG {
     
    // Returns value of Binomial Coefficient
    // C(n, k)
    static int binomialCoeff(int n, int k)
    {
         
        // Base Cases
        if (k == 0 || k == n)
            return 1;
 
        // Recurrence relation
        return binomialCoeff(n - 1, k - 1) + 
                     binomialCoeff(n - 1, k);
    }
 
    // Return Recontres number D(n, m)
    static int RencontresNumber(int n, int m)
    {
         
        // base condition
        if (n == 0 && m == 0)
            return 1;
 
        // base condition
        if (n == 1 && m == 0)
            return 0;
 
        // base condition
        if (m == 0)
            return (n - 1) * 
                (RencontresNumber(n - 1, 0) 
                + RencontresNumber(n - 2, 0));
 
        return binomialCoeff(n, m) * 
                 RencontresNumber(n - m, 0);
    }
 
    // Driver Program
    public static void Main()
    {
        int n = 7, m = 2;
         
        Console.Write(RencontresNumber(n, m));
    }
}
 
// This code is contributed by 
// Smitha Dinesh Semwal

PHP

<?php
// Recursive PHP program to
// find n-th Rencontres 
// Number
 
// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff($n, $k)
{
     
    // Base Cases
    if ($k == 0 || $k == $n)
        return 1;
 
    // Recurrence relation
    return binomialCoeff($n - 1,$k - 1) +
              binomialCoeff($n - 1, $k);
}
 
// Return Recontres number D(n, m)
function RencontresNumber($n, $m)
{
     
    // base condition
    if ($n == 0 && $m == 0)
        return 1;
 
    // base condition
    if ($n == 1 && $m == 0)
        return 0;
 
    // base condition
    if ($m == 0)
        return ($n - 1) * (RencontresNumber($n - 1, 0) +
                           RencontresNumber($n - 2, 0));
 
    return binomialCoeff($n, $m) * 
           RencontresNumber($n - $m, 0);
}
 
    // Driver Code
    $n = 7; 
    $m = 2;
    echo RencontresNumber($n, $m),"\n";
     
// This code is contributed by ajit. 
?>

Javascript

<script>
// Recursive Javascript program to
// find n-th Rencontres 
// Number
 
// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff(n, k)
{
     
    // Base Cases
    if (k == 0 || k == n)
        return 1;
 
    // Recurrence relation
    return binomialCoeff(n - 1,k - 1) +
              binomialCoeff(n - 1, k);
}
 
// Return Recontres number D(n, m)
function RencontresNumber(n, m)
{
     
    // base condition
    if (n == 0 && m == 0)
        return 1;
 
    // base condition
    if (n == 1 && m == 0)
        return 0;
 
    // base condition
    if (m == 0)
        return (n - 1) * (RencontresNumber(n - 1, 0) +
                           RencontresNumber(n - 2, 0));
 
    return binomialCoeff(n, m) * 
           RencontresNumber(n - m, 0);
}
 
    // Driver Code
    let n = 7; 
    let m = 2;
    document.write(RencontresNumber(n, m) + "<br>");
     
// This code is contributed by _saurabh_jaiswal. 
</script>

Output:

Time Complexity: O(n * m), where n and m represents the given integers.
Auxiliary Space: O(n*m), due to recursive stack space.

Below is the implementation using Dynamic Programming:

C++

// DP based CPP program to find n-th Rencontres 
// Number
#include <bits/stdc++.h>
using namespace std;
#define MAX 100
 
// Fills table C[n+1][k+1] such that C[i][j]
// represents table of binomial coefficient
// iCj
int binomialCoeff(int C[][MAX], int n, int k)
{
    // Calculate value of Binomial Coefficient
    // in bottom up manner
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i, k); j++) {
 
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            // Calculate value using previously
            // stored values
            else
                C[i][j] = C[i - 1][j - 1] + 
                          C[i - 1][j];
        }
    }
}
 
// Return Recontres number D(n, m)
int RencontresNumber(int C[][MAX], int n, int m)
{
    int dp[n+1][m+1] = { 0 };
 
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (j <= i) {
 
                // base case
                if (i == 0 && j == 0)
                    dp[i][j] = 1;
 
                // base case
                else if (i == 1 && j == 0)
                    dp[i][j] = 0;
 
                else if (j == 0)
                    dp[i][j] = (i - 1) * (dp[i - 1][0] + 
                                          dp[i - 2][0]);
                else
                    dp[i][j] = C[i][j] * dp[i - j][0];
            }
        }
    }
 
    return dp[n][m];
}
 
// Driver Program
int main()
{
    int n = 7, m = 2;
 
    int C[MAX][MAX];
    binomialCoeff(C, n, m);
 
    cout << RencontresNumber(C, n, m) << endl;
    return 0;
}

Java

// DP based Java program to find n-th Rencontres
// Number
 
import java.io.*;
 
class GFG {
 
    static int MAX = 100;
 
    // Fills table C[n+1][k+1] such that C[i][j]
    // represents table of binomial coefficient
    // iCj
    static void binomialCoeff(int C[][], int n, int k)
    {
 
        // Calculate value of Binomial Coefficient
        // in bottom up manner
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= Math.min(i, k); j++)
            {
 
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;
 
                // Calculate value using previously
                // stored values
                else
                    C[i][j] = C[i - 1][j - 1] + 
                                         C[i - 1][j];
            }
        }
    }
 
    // Return Recontres number D(n, m)
    static int RencontresNumber(int C[][], int n, int m)
    {
        int dp[][] = new int[n + 1][m + 1];
 
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (j <= i) {
 
                    // base case
                    if (i == 0 && j == 0)
                        dp[i][j] = 1;
 
                    // base case
                    else if (i == 1 && j == 0)
                        dp[i][j] = 0;
 
                    else if (j == 0)
                        dp[i][j] = (i - 1) * (dp[i - 1][0] 
                                           + dp[i - 2][0]);
                    else
                        dp[i][j] = C[i][j] * dp[i - j][0];
                }
            }
        }
 
        return dp[n][m];
    }
 
    // Driver Program
    public static void main(String[] args)
    {
        int n = 7, m = 2;
 
        int C[][] = new int[MAX][MAX];
        binomialCoeff(C, n, m);
 
        System.out.println(RencontresNumber(C, n, m));
    }
}
 
// This code is contributed by vt_m.

Python 3

# DP based Python 3 program to find n-th
# Rencontres Number
 
MAX = 100
 
# Fills table C[n+1][k+1] such that C[i][j]
# represents table of binomial coefficient
# iCj
def binomialCoeff(C, n, k) :
     
    # Calculate value of Binomial Coefficient
    # in bottom up manner
    for i in range(0, n + 1) :
        for j in range(0, min(i, k) + 1) :
             
            # Base Cases
            if (j == 0 or j == i) :
                C[i][j] = 1
 
            # Calculate value using previously
            # stored values
            else :
                C[i][j] = (C[i - 1][j - 1] 
                               + C[i - 1][j])
                 
 
# Return Recontres number D(n, m)
def RencontresNumber(C, n, m) :
    w, h = m+1, n+1
    dp= [[0 for x in range(w)] for y in range(h)] 
     
 
    for i in range(0, n+1) :
        for j in range(0, m+1) :
            if (j <= i) :
                 
                # base case
                if (i == 0 and j == 0) :
                    dp[i][j] = 1
 
                # base case
                elif (i == 1 and j == 0) :
                    dp[i][j] = 0
 
                elif (j == 0) :
                    dp[i][j] = ((i - 1) *
                     (dp[i - 1][0] + dp[i - 2][0]))
                else :
                    dp[i][j] = C[i][j] * dp[i - j][0]
                     
    return dp[n][m]
 
 
# Driver Program
n = 7
m = 2
C = [[0 for x in range(MAX)] for y in range(MAX)] 
 
binomialCoeff(C, n, m)
 
print(RencontresNumber(C, n, m))
 
# This code is contributed by Nikita Tiwari.

C#

// DP based C# program 
// to find n-th Rencontres 
// Number
using System;
 
class GFG
{
    static int MAX = 100;
 
    // Fills table C[n+1][k+1]
    // such that C[i][j]
    // represents table of 
    // binomial coefficient iCj
    static void binomialCoeff(int [,]C, 
                              int n, int k)
    {
 
        // Calculate value of 
        // Binomial Coefficient
        // in bottom up manner
        for (int i = 0; i <= n; i++) 
        {
            for (int j = 0; 
                     j <= Math.Min(i, k); j++)
            {
 
                // Base Cases
                if (j == 0 || j == i)
                    C[i,j] = 1;
 
                // Calculate value using 
                // previously stored values
                else
                    C[i, j] = C[i - 1, j - 1] + 
                              C[i - 1, j];
            }
        }
    }
 
    // Return Recontres 
    // number D(n, m)
    static int RencontresNumber(int [,]C, 
                                int n, int m)
    {
        int [,]dp = new int[n + 1, 
                            m + 1];
 
        for (int i = 0; i <= n; i++) 
        {
            for (int j = 0; j <= m; j++) 
            {
                if (j <= i) 
                {
 
                    // base case
                    if (i == 0 && j == 0)
                        dp[i, j] = 1;
 
                    // base case
                    else if (i == 1 && j == 0)
                        dp[i, j] = 0;
 
                    else if (j == 0)
                        dp[i, j] = (i - 1) * 
                                   (dp[i - 1, 0] + 
                                    dp[i - 2, 0]);
                    else
                        dp[i, j] = C[i, j] *
                                  dp[i - j, 0];
                }
            }
        }
 
        return dp[n, m];
    }
 
    // Driver Code
    static public void Main ()
    {
        int n = 7, m = 2;
        int [,]C = new int[MAX, MAX];
        binomialCoeff(C, n, m);
     
        Console.WriteLine(RencontresNumber(C, n, m));
    }
}
 
// This code is contributed
// by akt_mit

PHP

<?php
// DP based PHP program to find n-th Rencontres 
// Number
$MAX=100;
 
// Fills table C[n+1][k+1] such that C[i][j]
// represents table of binomial coefficient
// iCj
function binomialCoeff(&$C, $n, $k)
{
    // Calculate value of Binomial Coefficient
    // in bottom up manner
    for ($i = 0; $i <= $n; $i++) {
        for ($j = 0; $j <= min($i, $k); $j++) {
 
            // Base Cases
            if ($j == 0 || $j == $i)
                $C[$i][$j] = 1;
 
            // Calculate value using previously
            // stored values
            else
                $C[$i][$j] = $C[$i - 1][$j - 1] + 
                        $C[$i - 1][$j];
        }
    }
}
 
// Return Recontres number D(n, m)
function RencontresNumber($C, $n, $m)
{
    $dp=array_fill(0,$n+1,array_fill(0,$m+1,0));
 
    for ($i = 0; $i <= $n; $i++) {
        for ($j = 0; $j <= $m; $j++) {
            if ($j <= $i) {
 
                // base case
                if ($i == 0 && $j == 0)
                    $dp[$i][$j] = 1;
 
                // base case
                else if ($i == 1 && $j == 0)
                    $dp[$i][$j] = 0;
 
                else if ($j == 0)
                    $dp[$i][$j] = ($i - 1) * ($dp[$i - 1][0] + 
                                        $dp[$i - 2][0]);
                else
                    $dp[$i][$j] = $C[$i][$j] * $dp[$i - $j][0];
            }
        }
    }
 
    return $dp[$n][$m];
}
 
// Driver Program
 
    $n = 7;
    $m = 2;
 
    $C=array(array());
    binomialCoeff($C, $n, $m);
 
    echo RencontresNumber($C, $n, $m);
 
// This code is contributed
// by mits
?>

Javascript

<script>
 
// DP based JavaScript program to find n-th
// Rencontres Number
const MAX = 100
 
// Fills table C[n+1][k+1] such that C[i][j]
// represents table of binomial coefficient
// iCj
function binomialCoeff(C, n, k){
     
    // Calculate value of Binomial Coefficient
    // in bottom up manner
    for(let i=0;i<n+1;i++){
        for(let j=0;j< Math.min(i, k) + 1;j++){
             
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1
 
            // Calculate value using previously
            // stored values
            else
                C[i][j] = (C[i - 1][j - 1]
                            + C[i - 1][j])
        }
    }
}
 
// Return Recontres number D(n, m)
function RencontresNumber(C, n, m){
    let w = m+1,h = n+1
    let dp= new Array(h).fill(0).map(()=>new Array(w).fill(0))
     
 
    for(let i=0;i<n+1;i++){
        for(let j=0;j<m+1;j++){
            if (j <= i) {
             
                // base case
                if (i == 0 && j == 0)
                    dp[i][j] = 1
 
                // base case
                else if (i == 1 && j == 0)
                    dp[i][j] = 0
 
                else if (j == 0){
                    dp[i][j] = ((i - 1) *
                    (dp[i - 1][0] + dp[i - 2][0]))
                }
                else
                    dp[i][j] = C[i][j] * dp[i - j][0]
            }
        }
    }
                     
    return dp[n][m]
}
 
 
// Driver Program
let n = 7
let m = 2
let C = new Array(MAX).fill(0).map(()=>new Array(MAX).fill(0))
 
binomialCoeff(C, n, m)
 
document.write(RencontresNumber(C, n, m),"</br>")
 
// This code is contributed by shinjanpatra
 
</script>

Output:

Time Complexity: O(n * m), where n and m represents the given integers.
Auxiliary Space: O(n * m), where n and m represents the given integers.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!