Lobb Number in C++
By Abinash ReddyIn this article, we will learn about Lobb Numbers and how to find Lobb Number of m,n in C++.
What is Lobb Number?
Lobb number (Lm,n) calculates the number of ways that n+m open parentheses and n-m close parentheses can be positioned to form the start of a valid sequence of balanced parentheses. Lobb number is defined by two non-negative integers m and n, where n ≥ m ≥ 0. (m, n)th Lobb number is given by the equation.
Lobb Number in C++
1. Create a function binomialCoeff to calculate the binomial coefficient(2*n, m+n).
2. Now Directly apply the formula ((2*m+1) * binomialCoeff(2*n, m+n))/(m+n+1);
#include <bits/stdc++.h>
using namespace std;
int binomialCoeff(int n, int k){
int coeff[n+1][k+1];
for (int i=0;i<=n;i++){
for (int j =0;j<=min(i, k);j++){
if (j == 0 || j == i)
coeff[i][j] = 1;
else
coeff[i][j] = coeff[i-1][j-1] + coeff[i-1][j];
}
}
return coeff[n][k];
}
int lobb_number(int n, int m){
return ((2*m+1) * binomialCoeff(2*n, m+n))/(m+n+1);
}
int main(){
int m, n;
cout<<"Enter the n value: ";
cin>>n;
cout<<"Enter the m value: ";
cin>>m;
cout<<lobb_number(n, m)<<endl;
return 0;
}Output
Enter the n value: 6 Enter the m value: 4 54 Enter the n value: 10 Enter the m value: 5 10659
Also, read
Leave a Reply