En matemáticas, un número de Motzkin para un número dado n es el número de formas diferentes de dibujar cuerdas que no se cortan entre n puntos en un círculo (no necesariamente tocando cada punto por una cuerda).
Por ejemplo, para n = 3, M 4 = 9.
La relación de recurrencia con el número N de Motzkin es:
El número de Motzkin se puede utilizar para encontrar:
- El número de secuencias enteras positivas de longitud n – 1 en las que los elementos de apertura y finalización son 1 o 2, y la diferencia entre dos elementos consecutivos es -1, 0 o 1.
- El número de rutas en el cuadrante superior derecho de una cuadrícula desde la coordenada (0, 0) hasta la coordenada (n, 0) en n pasos si uno puede moverse solo hacia la derecha (hacia arriba, hacia abajo o en línea recta) en cada paso pero prohibido sumergirse por debajo del eje y = 0.
Por ejemplo-
La siguiente figura muestra los 9 caminos Motzkin válidos desde (0, 0) hasta (4, 0).
Ejemplos:
Input : n = 4 Output : 9 Input : n = 5 Output : 21
A continuación se muestra el programa para encontrar el enésimo número de Motzkin:
C++
// CPP Program to find Nth Motzkin Number.
#include <bits/stdc++.h>
using namespace std;
// Return the nth Motzkin Number.
int motzkin(int n)
{
// Base Case
if (n == 0 || n == 1)
return 1;
// Recursive step
return ((2 * n + 1) * motzkin(n - 1) +
(3 * n - 3) * motzkin(n - 2)) / (n + 2);
}
// Driven Program
int main()
{
int n = 8;
cout << motzkin(n) << endl;
return 0;
}
Java
// Java Program to find Nth Motzkin Number.
import java.util.*;
class Digits
{
// Return the nth Motzkin Number.
public static int motzkin(int n)
{
// Base Case
if (n == 0 || n == 1)
return 1;
// Recursive step
return ((2 * n + 1) * motzkin(n - 1) +
(3 * n - 3) * motzkin(n - 2)) / (n + 2);
}
// driver code
public static void main(String[] args)
{
int n = 8;
System.out.print( motzkin(n) );
}
}
// This code is contributed by rishabh_jain
Python3
# Python3 program to find Nth Motzkin Number. # Return the nth Motzkin Number. def motzkin(n) : # Base Case if (n == 0 or n == 1) : return 1 # Recursive step return ((2 * n + 1) * motzkin(n - 1) + (3 * n - 3) * motzkin(n - 2)) / (n + 2) # Driver code n = 8 print( motzkin(n) ) # This code is contributed by rishabh_jain
C#
// C# Program to find Nth Motzkin Number.
using System;
class GFG {
// Return the nth Motzkin Number.
public static int motzkin(int n)
{
// Base Case
if (n == 0 || n == 1)
return 1;
// Recursive step
return ((2 * n + 1) * motzkin(n - 1) +
(3 * n - 3) * motzkin(n - 2)) / (n + 2);
}
// driver code
public static void Main()
{
int n = 8;
Console.WriteLine( motzkin(n) );
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP Program to find
// Nth Motzkin Number.
// Return the nth Motzkin Number.
function motzkin($n)
{
// Base Case
if ($n == 0 || $n == 1)
return 1;
// Recursive step
return ((2 * $n + 1) *
motzkin($n - 1) +
(3 * $n - 3) *
motzkin($n - 2)) /
($n + 2);
}
// Driven Code
$n = 8;
echo(motzkin($n));
// This code is contributed by Ajit.
?>
Javascript
<script>
// javascript Program to find Nth Motzkin Number.
// Return the nth Motzkin Number.
function motzkin( n)
{
// Base Case
if (n == 0 || n == 1)
return 1;
// Recursive step
return ((2 * n + 1) * motzkin(n - 1) +
(3 * n - 3) * motzkin(n - 2)) / (n + 2);
}
// driver code
var n = 8;
document.write( motzkin(n) );
</script>
Producción :
323
Usando Programación Dinámica:
A continuación se muestra la solución de programación dinámica para encontrar el n-ésimo número de Motzkin:
C++
// CPP Program to find Nth Motzkin Number.
#include <bits/stdc++.h>
using namespace std;
// Return the nth Motzkin Number.
int motzkin(int n)
{
int dp[n + 1];
// Base case
dp[0] = dp[1] = 1;
// Finding i-th Motzkin number.
for (int i = 2; i <= n; i++)
dp[i] = ((2 * i + 1) * dp[i - 1] +
(3 * i - 3) * dp[i - 2]) / (i + 2);
return dp[n];
}
// Driven Program
int main()
{
int n = 8;
cout << motzkin(n) << endl;
return 0;
}
Java
// Java Program to find Nth Motzkin Number.
import java.util.*;
class Digits
{
// Return the nth Motzkin Number.
public static int motzkin(int n)
{
int[] dp = new int[n+1];
// Base case
dp[0] = dp[1] = 1;
// Finding i-th Motzkin number.
for (int i = 2; i <= n; i++)
dp[i] = ((2 * i + 1) * dp[i - 1] +
(3 * i - 3) * dp[i - 2]) / (i + 2);
return dp[n];
}
// driver code
public static void main(String[] args)
{
int n = 8;
System.out.print( motzkin(n) );
}
}
// This code is contributed by rishabh_jain
Python3
# Python3 program to find Nth Motzkin Number. # Return the nth Motzkin Number. def motzkin(n) : dp = [None] * (n+1) # Base case dp[0] = dp[1] = 1; i = 2 # Finding i-th Motzkin number. while i <= n : dp[i] = ((2 * i + 1) * dp[i - 1] + (3 * i - 3) * dp[i - 2]) / (i + 2); i = i + 1 return dp[n]; # Driver code n = 8 print( motzkin(n) ) # This code is contributed by rishabh_jain
C#
// C# Program to find Nth Motzkin Number.
using System;
class GFG {
// Return the nth Motzkin Number.
public static int motzkin(int n)
{
int[] dp = new int[n+1];
// Base case
dp[0] = dp[1] = 1;
// Finding i-th Motzkin number.
for (int i = 2; i <= n; i++)
dp[i] = ((2 * i + 1) * dp[i - 1] +
(3 * i - 3) * dp[i - 2]) / (i + 2);
return dp[n];
}
// driver code
public static void Main()
{
int n = 8;
Console.WriteLine( motzkin(n) );
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP Program to find
// Nth Motzkin Number.
// Return the nth Motzkin Number.
function motzkin($n)
{
// Base case
$dp[0] = $dp[1] = 1;
// Finding i-th Motzkin number.
for ($i = 2; $i <= $n; $i++)
$dp[$i] = ((2 * $i + 1) *
$dp[$i - 1] +
(3 * $i - 3) *
$dp[$i - 2]) /
($i + 2);
return $dp[$n];
}
// Driven Code
$n = 8;
echo(motzkin($n));
// This code is contributed by Ajit.
?>
Javascript
// JavaScript Program to find Nth Motzkin Number.
// Return the nth Motzkin Number.
function motzkin(n)
{
let dp = new Array(n+1).fill(0);
// Base case
dp[0] = dp[1] = 1;
// Finding i-th Motzkin number.
for (let i = 2; i <= n; i++)
dp[i] = ((2 * i + 1) * dp[i - 1] +
(3 * i - 3) * dp[i - 2]) / (i + 2);
return dp[n];
}
// Driven Program
let n = 8;
console.log(motzkin(n));
// The code is contributed by Nidhi goel
Producción:
323