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 Dn, 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) = nCk * 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 Programint main(){ int n = 7, m = 2; cout << RencontresNumber(n, m) << endl; return 0;} |
Java
// Recursive Java program to find n-th Rencontres// Numberimport 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 Programn = 7; m = 2print(RencontresNumber(n, m))# This code is contributed by Smitha Dinesh Semwal. |
C#
// Recursive C# program to find n-th Rencontres// Numberusing 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:
924
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// iCjint 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 Programint 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// Numberimport 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 NumberMAX = 100# Fills table C[n+1][k+1] such that C[i][j]# represents table of binomial coefficient# iCjdef 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 Programn = 7m = 2C = [[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 // Numberusing 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// iCjfunction 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 Numberconst MAX = 100// Fills table C[n+1][k+1] such that C[i][j]// represents table of binomial coefficient// iCjfunction 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 Programlet n = 7let m = 2let 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:
924
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
