Lobb Number in C++

In 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_formula

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

Your email address will not be published. Required fields are marked *