Dados dos números, n >= 0 y 0 <= k <= n, cuente el número de trastornos con k puntos fijos.
Ejemplos:
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
En matemáticas combinatorias, el número de rencontres < o D(n, k) representa el recuento de desarreglos parciales.
La relación de recurrencia para encontrar Rencontres Number D n, k :
re (0, 0) = 1
re (0, 1) = 0
re (n+2, 0) = (n+1) * (re (n+1, 0) + re (n, 0) )
re ( norte, k) = norte C k * D (nk, 0) )
Dados los dos enteros positivos n y k . La tarea es encontrar el número de rencontres D(n, k) para el dador n y k.
A continuación se muestra la solución recursiva de este enfoque:
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>
Producción:
924
Complejidad de tiempo: O(n * m), donde n y m representan los números enteros dados.
Espacio auxiliar: O(n*m), debido al espacio de pila recursivo.
A continuación se muestra la implementación usando Programación Dinámica:
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>
Producción:
924
Complejidad de tiempo: O(n * m), donde n y m representan los números enteros dados.
Espacio Auxiliar: O(n * m), donde n y m representan los enteros dados.