Tutorialspoint.dev

Delannoy Number

In mathematics, a Delannoy number D describes the number of paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (m, n), using only single steps north, northeast, or east.
For Example, D(3, 3) equals 63.

Delannoy Number can be calculated by:

Delannoy number can be used to find:

  • Counts the number of global alignments of two sequences of lengths m and n.
  • Number of points in an m-dimensional integer lattice that are at most n steps from the origin.
  • In cellular automata, the number of cells in an m-dimensional von Neumann neighborhood of radius n.
  • Number of cells on a surface of an m-dimensional von Neumann neighborhood of radius n.

Examples :

Input : n = 3, m = 3
Output : 63

Input : n = 4, m = 5
Output : 681



Below is the implementation of finding Delannoy Number:

C++

// CPP Program of finding nth Delannoy Number.
#include <bits/stdc++.h>
using namespace std;
  
// Return the nth Delannoy Number.
int dealnnoy(int n, int m)
{
    // Base case
    if (m == 0 || n == 0)
        return 1;
  
    // Recursive step.
    return dealnnoy(m - 1, n) + 
           dealnnoy(m - 1, n - 1) +
           dealnnoy(m, n - 1);
}
  
// Driven Program
int main()
{
    int n = 3, m = 4;
    cout << dealnnoy(n, m) << endl;
    return 0;
}

Java

// Java Program for finding nth Delannoy Number.
import java.util.*;
import java.lang.*;
  
public class GfG{
      
    // Return the nth Delannoy Number.
    public static int dealnnoy(int n, int m)
    {
        // Base case
        if (m == 0 || n == 0)
            return 1;
  
        // Recursive step.
        return dealnnoy(m - 1, n) + 
            dealnnoy(m - 1, n - 1) +
            dealnnoy(m, n - 1);
    }
      
    // driver function
    public static void main(String args[]){
        int n = 3, m = 4;
        System.out.println(dealnnoy(n, m));
    }
}
  
/* This code is contributed by Sagar Shukla. */

Python3

# Python3 Program for finding 
# nth Delannoy Number.
  
# Return the nth Delannoy Number.
def dealnnoy(n, m):
      
    # Base case
    if (m == 0 or n == 0) :
        return 1
  
    # Recursive step.
    return dealnnoy(m - 1, n) + dealnnoy(m - 1, n - 1) + dealnnoy(m, n - 1)
  
# Driven code
n = 3
m = 4;
print( dealnnoy(n, m) )
  
# This code is contributed by "rishabh_jain".

C#

// C# Program for finding nth Delannoy Number.
using System;
  
public class GfG {
  
    // Return the nth Delannoy Number.
    public static int dealnnoy(int n, int m)
    {
  
        // Base case
        if (m == 0 || n == 0)
            return 1;
  
        // Recursive step.
        return dealnnoy(m - 1, n) + 
               dealnnoy(m - 1, n - 1) + 
                     dealnnoy(m, n - 1);
    }
  
    // driver function
    public static void Main()
    {
        int n = 3, m = 4;
        Console.WriteLine(dealnnoy(n, m));
    }
}
  
/* This code is contributed by vt_m. */

PHP

<?php
// PHP Program of finding nth
// Delannoy Number.
  
// Return the nth Delannoy Number.
function dealnnoy( $n, $m)
{
      
    // Base case
    if ($m == 0 or $n == 0)
        return 1;
  
    // Recursive step.
    return dealnnoy($m - 1, $n) + 
           dealnnoy($m - 1, $n - 1) +
           dealnnoy($m, $n - 1);
}
  
    // Driver Code
    $n = 3; 
    $m = 4;
    echo dealnnoy($n, $m);
  
// This code is contributed by anuj_67.
?>


Output:

129

Below is the Dynamic Programming program to find nth Delannoy Number:

C++

// CPP Program of finding nth Delannoy Number.
#include <bits/stdc++.h>
using namespace std;
  
// Return the nth Delannoy Number.
int dealnnoy(int n, int m)
{
    int dp[m + 1][n + 1];
  
    // Base cases
    for (int i = 0; i <= m; i++) 
        dp[i][0] = 1;
    for (int i = 0; i <= m; i++) 
        dp[0][i] = 1;    
  
    for (int i = 1; i <= m; i++) 
        for (int j = 1; j <= n; j++) 
            dp[i][j] = dp[i - 1][j] +
                       dp[i - 1][j - 1] + 
                       dp[i][j - 1];
  
    return dp[m][n];
}
  
// Driven Program
int main()
{
    int n = 3, m = 4;
    cout << dealnnoy(n, m) << endl;
    return 0;
}

Java

// Java Program of finding nth Delannoy Number.
  
import java.io.*;
  
class GFG {
      
    // Return the nth Delannoy Number.
    static int dealnnoy(int n, int m)
    {
        int dp[][]=new int[m + 1][n + 1];
       
        // Base cases
        for (int i = 0; i <= m; i++) 
            dp[i][0] = 1;
        for (int i = 0; i < m; i++) 
            dp[0][i] = 1;    
       
        for (int i = 1; i <= m; i++) 
            for (int j = 1; j <= n; j++) 
                dp[i][j] = dp[i - 1][j] +
                           dp[i - 1][j - 1] + 
                           dp[i][j - 1];
       
        return dp[m][n];
    }
       
    // Driven Program
    public static void main(String args[])
    {
        int n = 3, m = 4;
        System.out.println(dealnnoy(n, m));
          
    }
}
  
// This code is contributed by Nikita Tiwari.

Python3

# Python3 Program for finding nth
# Delannoy Number.
  
# Return the nth Delannoy Number.
def dealnnoy (n, m):
    dp = [[0 for x in range(n+1)] for x in range(m+1)]
  
    # Base cases
    for i in range(m):
        dp[0][i] = 1
      
    for i in range(1, m + 1):
        dp[i][0] = 1
  
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + dp[i][j - 1];
  
    return dp[m][n]
  
# Driven code
n = 3
m = 4
print(dealnnoy(n, m))
  
# This code is contributed by "rishabh_jain".

C#

// C# Program of finding nth Delannoy Number.
using System;
  
class GFG {
  
    // Return the nth Delannoy Number.
    static int dealnnoy(int n, int m)
    {
          
        int[, ] dp = new int[m + 1, n + 1];
  
        // Base cases
        for (int i = 0; i <= m; i++)
            dp[i, 0] = 1;
        for (int i = 0; i < m; i++)
            dp[0, i] = 1;
  
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i, j] = dp[i - 1, j]
                     + dp[i - 1, j - 1]
                         + dp[i, j - 1];
  
        return dp[m, n];
    }
  
    // Driven Program
    public static void Main()
    {
        int n = 3, m = 4;
          
        Console.WriteLine(dealnnoy(n, m));
    }
}
  
// This code is contributed by vt_m.

PHP

<?php
// PHP Program of finding
// nth Delannoy Number.
  
// Return the nth Delannoy Number.
function dealnnoy($n, $m)
{
    $dp[$m + 1][$n + 1] = 0;
  
    // Base cases
    for ($i = 0; $i <= $m; $i++) 
        $dp[$i][0] = 1;
    for ( $i = 0; $i <= $m; $i++) 
        $dp[0][$i] = 1; 
  
    for ($i = 1; $i <= $m; $i++) 
        for ($j = 1; $j <= $n; $j++) 
            $dp[$i][$j] = $dp[$i - 1][$j] +
                      $dp[$i - 1][$j - 1] + 
                           $dp[$i][$j - 1];
  
    return $dp[$m][$n];
}
  
// Driven Code
$n = 3; $m = 4;
echo dealnnoy($n, $m) ;
  
// This code is contributed by SanjuTomar 
?>

Output :

129


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter