Lobb Number
In combinatorial mathematics, the Lobb number Lm, n counts the number of ways that n + m open parentheses can be arranged to form the start of a valid sequence of balanced parentheses.
The Lobb number are parameterized by two non-negative integers m and n with n >= m >= 0. It can be obtained by:
Lobb Number is also used to count the number of ways in which n + m copies of the value +1 and n – m copies of the value -1 may be arranged into a sequence such that all of the partial sums of the sequence are non- negative.
Examples :
Input : n = 3, m = 2 Output : 5 Input : n =5, m =3 Output :35
The idea is simple, we use a function that computes binomial coefficients for given values. Using this function and above formula, we can compute Lobb numbers.
C++
// CPP Program to find Ln, m Lobb Number. #include <bits/stdc++.h> #define MAXN 109 using namespace std; // Returns value of Binomial Coefficient C(n, k) int binomialCoeff( int n, int k) { int C[n + 1][k + 1]; // 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 C[n][k]; } // Return the Lm, n Lobb Number. int lobb( int n, int m) { return ((2 * m + 1) * binomialCoeff(2 * n, m + n)) / (m + n + 1); } // Driven Program int main() { int n = 5, m = 3; cout << lobb(n, m) << endl; return 0; } |
Java
// JAVA Code For Lobb Number import java.util.*; class GFG { // Returns value of Binomial // Coefficient C(n, k) static int binomialCoeff( int n, int k) { int C[][] = new int [n + 1 ][k + 1 ]; // 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 C[n][k]; } // Return the Lm, n Lobb Number. static int lobb( int n, int m) { return (( 2 * m + 1 ) * binomialCoeff( 2 * n, m + n)) / (m + n + 1 ); } /* Driver program to test above function */ public static void main(String[] args) { int n = 5 , m = 3 ; System.out.println(lobb(n, m)); } } // This code is contributed by Arnav Kr. Mandal. |
Python 3
# Python 3 Program to find Ln, # m Lobb Number. # Returns value of Binomial # Coefficient C(n, k) def binomialCoeff(n, k): C = [[ 0 for j in range (k + 1 )] for i in range (n + 1 )] # 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 C[n][k] # Return the Lm, n Lobb Number. def lobb(n, m): return ((( 2 * m + 1 ) * binomialCoeff( 2 * n, m + n)) / (m + n + 1 )) # Driven Program n = 5 m = 3 print ( int (lobb(n, m))) # This code is contributed by # Smitha Dinesh Semwal |
C#
// C# Code For Lobb Number using System; class GFG { // Returns value of Binomial // Coefficient C(n, k) static int binomialCoeff( int n, int k) { int [, ] C = new int [n + 1, k + 1]; // 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 C[n, k]; } // Return the Lm, n Lobb Number. static int lobb( int n, int m) { return ((2 * m + 1) * binomialCoeff( 2 * n, m + n)) / (m + n + 1); } /* Driver program to test above function */ public static void Main() { int n = 5, m = 3; Console.WriteLine(lobb(n, m)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP Program to find Ln, // m Lobb Number. $MAXN =109; // Returns value of Binomial // Coefficient C(n, k) function binomialCoeff( $n , $k ) { $C = array ( array ()); // 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 p // reviously stored values else $C [ $i ][ $j ] = $C [ $i - 1][ $j - 1] + $C [ $i - 1][ $j ]; } } return $C [ $n ][ $k ]; } // Return the Lm, n Lobb Number. function lobb( $n , int $m ) { return ((2 * $m + 1) * binomialCoeff(2 * $n , $m + $n )) / ( $m + $n + 1); } // Driven Code $n = 5; $m = 3; echo lobb( $n , $m ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // javascript code for Lobb Number // Returns value of Binomial // Coefficient C(n, k) function binomialCoeff(n, k) { let C = new Array(n + 1); // Loop to create 2D array using 1D array for ( var i = 0; i < C.length; i++) { C[i] = new Array(2); } // Calculate value of Binomial // Coefficient in bottom up manner for (let i = 0; i <= n; i++) { for (let 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 C[n][k]; } // Return the Lm, n Lobb Number. function lobb(n, m) { return ((2 * m + 1) * binomialCoeff(2 * n, m + n)) / (m + n + 1); } // Driver code let n = 5, m = 3; document.write(lobb(n, m)); // This code is contributed by sanjoy_62. </script> |
Output
35
Time Complexity: O(2*n*(m+n))
Auxiliary Space: O((2*n)*(m+n))
Efficient approach: Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector C of size K+1.
- Set a base case by initializing the values of C.
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- At last return and print the final answer stored in C[K].
Implementation:
C++
// CPP Program to find Ln, m Lobb Number. #include <bits/stdc++.h> #define MAXN 109 using namespace std; // Returns value of Binomial Coefficient C(n, k) int binomialCoeff( int n, int k) { int C[k+1]; memset (C, 0, sizeof (C)); C[0] = 1; // nC0 is 1 // Calculate value of Binomial Coefficient for ( int i = 1; i <= n; i++) { for ( int j = min(i, k); j > 0; j--) C[j] = C[j] + C[j-1]; } //return final answer return C[k]; } // Return the Lm, n Lobb Number. int lobb( int n, int m) { return ((2 * m + 1) * binomialCoeff(2 * n, m + n)) / (m + n + 1); } // Driven Program int main() { int n = 5, m = 3; // function call cout << lobb(n, m) << endl; return 0; } |
Java
import java.util.Arrays; public class LobbNumber { // Returns value of Binomial Coefficient C(n, k) static int binomialCoeff( int n, int k) { int [] C = new int [k + 1 ]; Arrays.fill(C, 0 ); C[ 0 ] = 1 ; // nC0 is 1 // Calculate value of Binomial Coefficient for ( int i = 1 ; i <= n; i++) { for ( int j = Math.min(i, k); j > 0 ; j--) { C[j] = C[j] + C[j - 1 ]; } } //return final answer return C[k]; } // Return the Lm, n Lobb Number. static int lobb( int n, int m) { return (( 2 * m + 1 ) * binomialCoeff( 2 * n, m + n)) / (m + n + 1 ); } // Driven Program public static void main(String[] args) { int n = 5 , m = 3 ; // function call System.out.println(lobb(n, m)); } } |
Python3
# Returns value of Binomial Coefficient C(n, k) def binomialCoeff(n, k): C = [ 0 ] * (k + 1 ) C[ 0 ] = 1 # nC0 is 1 # Calculate value of Binomial Coefficient for i in range ( 1 , n + 1 ): j = min (i, k) while j > 0 : C[j] = C[j] + C[j - 1 ] j - = 1 # return final answer return C[k] # Return the Lm, n Lobb Number. def lobb(n, m): return (( 2 * m + 1 ) * binomialCoeff( 2 * n, m + n)) / / (m + n + 1 ) # Driven Program if __name__ = = "__main__" : n = 5 m = 3 # function call print (lobb(n, m)) |
C#
using System; public class Program { // Returns value of Binomial Coefficient C(n, k) static int binomialCoeff( int n, int k) { int [] C = new int [k + 1]; Array.Fill(C, 0); C[0] = 1; // nC0 is 1 // Calculate value of Binomial Coefficient for ( int i = 1; i <= n; i++) { for ( int j = Math.Min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } //return final answer return C[k]; } // Return the Lm, n Lobb Number. static int lobb( int n, int m) { return ((2 * m + 1) * binomialCoeff(2 * n, m + n)) / (m + n + 1); } // Driven Program public static void Main() { int n = 5, m = 3; // function call Console.WriteLine(lobb(n, m)); } } |
Javascript
function binomialCoeff(n, k) { let C = new Array(k + 1).fill(0); C[0] = 1; // nC0 is 1 // Calculate value of Binomial Coefficient for (let i = 1; i <= n; i++) { for (let j = Math.min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } //return final answer return C[k]; } function lobb(n, m) { return ((2 * m + 1) * binomialCoeff(2 * n, m + n)) / (m + n + 1); } // Driven Program let n = 5, m = 3; console.log(lobb(n, m)); |
Output
35
Time Complexity: O(n^2)
Auxiliary Space: O(k)
Contact Us