En matemáticas, los números de involución de los números telefónicos son una secuencia de números enteros que cuentan el número de patrones de conexión en un sistema telefónico con n suscriptores, donde las conexiones se realizan entre pares de suscriptores. Estos números también describen el número de coincidencias de un gráfico completo de n vértices, el número de permutaciones en n elementos que son involuciones, la suma del valor absoluto de los coeficientes de los polinomios de Hermite, el número de cuadros estándar de Young con n celdas y la suma de los grados de las representaciones irreducibles del grupo simétrico.
Los números de teléfono también se utilizan para contar el número de formas de colocar n torres en un nxntablero de ajedrez de manera que no se ataquen dos torres y de tal manera que la configuración de las torres sea simétrica bajo una reflexión diagonal del tablero.
El número de teléfono se puede evaluar mediante la siguiente relación de recurrencia:
Dado un entero positivo n . La tarea es encontrar el enésimo número de teléfono.
Ejemplos:
Input : n = 4 Output : 10 Input : n = 6 Output : 76
A continuación se muestra una implementación ingenua de encontrar el número de teléfono enésimo basado en la fórmula recursiva anterior.
C++
// CPP Program to find the nth telephone number.
#include <bits/stdc++.h>
using namespace std;
// return the nth telephone number
int telephonenumber(int n)
{
// base step
if (n == 0 || n == 1)
return 1;
// recursive step
return telephonenumber(n - 1) +
(n - 1) * telephonenumber(n - 2);
}
// Driven Program
int main()
{
int n = 6;
cout << telephonenumber(n) << endl;
return 0;
}
Java
// JAVA Code to find the nth
// telephone number.
import java.util.*;
class GFG {
// return the nth telephone number
static int telephonenumber(int n)
{
// base step
if (n == 0 || n == 1)
return 1;
// recursive step
return telephonenumber(n - 1) +
(n - 1) * telephonenumber(n - 2);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int n = 6;
System.out.println(telephonenumber(n));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 code to find the # nth telephone number. # return the nth telephone number def telephonenumber (n): # base step if n == 0 or n == 1: return 1 # recursive step return (telephonenumber(n - 1) + (n - 1) * telephonenumber(n - 2)) # Driven Program n = 6 print(telephonenumber(n)) # This code is contributed by "Sharad_Bhardwaj".
C#
// C# Code to find the nth
// telephone number.
using System;
class GFG {
// return the nth telephone number
static int telephonenumber(int n)
{
// base step
if (n == 0 || n == 1)
return 1;
// recursive step
return telephonenumber(n - 1) +
(n - 1) * telephonenumber(n - 2);
}
/* Driver program to test above function */
public static void Main()
{
int n = 6;
Console.Write(telephonenumber(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to find
// the nth telephone number
// return the nth
// telephone number
function telephonenumber( $n)
{
// base step
if ($n == 0 or $n == 1)
return 1;
// recursive step
return telephonenumber($n - 1) +
($n - 1) * telephonenumber($n - 2);
}
// Driven Code
$n = 6;
echo telephonenumber($n) ;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript Program to find
// the nth telephone number.
// return the nth telephone number
function telephonenumber(n)
{
// base step
if (n == 0 || n == 1)
return 1;
// recursive step
return telephonenumber(n - 1) +
(n - 1) * telephonenumber(n - 2);
}
// Driven Program
var n = 6;
document.write( telephonenumber(n));
</script>
Producción:
76
Complejidad del tiempo: O(2 n )
Espacio auxiliar: O(2 n )
A continuación se muestra una implementación eficiente para encontrar el número de teléfono n mediante la programación dinámica:
C++
// CPP Program to find the nth telephone number.
#include <bits/stdc++.h>
using namespace std;
// return the nth telephone number
int telephonenumber(int n)
{
int dp[n + 1];
memset(dp, 0, sizeof(dp));
// Base case
dp[0] = dp[1] = 1;
// finding ith telephone number, where 2 <= i <= n.
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
return dp[n];
}
// Driver Program
int main()
{
int n = 6;
cout << telephonenumber(n) << endl;
return 0;
}
Java
// JAVA Code to find nth Telephone Number
import java.util.*;
class GFG {
// return the nth telephone number
static int telephonenumber(int n)
{
int dp[] = new int[n + 1];
// Base case
dp[0] = dp[1] = 1;
// finding ith telephone number,
// where 2 <= i <= n.
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
return dp[n];
}
/* Driver program to test above function */
public static void main(String[] args)
{
int n = 6;
System.out.println(telephonenumber(n));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 code to find the # nth telephone number. # return the nth telephone number def telephonenumber (n): dp = [0] * (n + 1) # Base case dp[0] = dp[1] = 1 # finding ith telephone number, # where 2 <= i <= n. for i in range(2, n + 1): dp[i] = dp[i - 1] + (i - 1) * dp[i - 2] return dp[n] # Driver Code n = 6 print(telephonenumber(n)) # This code is contributed by "Sharad_Bhardwaj".
C#
// C# Code to find nth Telephone Number
using System;
class GFG {
// return the nth telephone number
static int telephonenumber(int n)
{
int[] dp = new int[n + 1];
// Base case
dp[0] = dp[1] = 1;
// finding ith telephone number,
// where 2 <= i <= n.
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
return dp[n];
}
/* Driver program to test above function */
public static void Main()
{
int n = 6;
Console.Write(telephonenumber(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to find
// the nth telephone number.
// return the nth telephone number
function telephonenumber($n)
{
$dp = array();
// Base case
$dp[0] = $dp[1] = 1;
// finding ith telephone number,
// where 2 <= i <= n.
for ( $i = 2; $i <= $n; $i++)
$dp[$i] = $dp[$i - 1] +
($i - 1) *
$dp[$i - 2];
return $dp[$n];
}
// Driver Code
$n = 6;
echo telephonenumber($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript Program to find nth Telephone Number
// return the nth telephone number
function telephonenumber(n)
{
let dp = [];
// Base case
dp[0] = dp[1] = 1;
// finding ith telephone number,
// where 2 <= i <= n.
for (let i = 2; i <= n; i++)
dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
return dp[n];
}
// Driver code
let n = 6;
document.write(telephonenumber(n));
// This code is contributed by sanjoy_62.
</script>
Producción:
76
Complejidad temporal: O(n)
Espacio auxiliar: O(n)