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 109using 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 Programint main(){ int n = 5, m = 3; cout << lobb(n, m) << endl; return 0;} |
Java
// JAVA Code For Lobb Numberimport 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 Programn = 5m = 3print(int(lobb(n, m)))# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# Code For Lobb Numberusing 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 109using 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 Programint 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 Programif __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 Coefficientfor (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 answerreturn C[k];}function lobb(n, m) {return ((2 * m + 1) * binomialCoeff(2 * n, m + n)) / (m + n + 1);}// Driven Programlet n = 5, m = 3;console.log(lobb(n, m)); |
Output
35
Time Complexity: O(n^2)
Auxiliary Space: O(k)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
