Narayana Number In C++

In this guide, we will explore Narayana numbers in C++ along with their formulas, characteristics, pseudocode, and illustrations.

What are the Narayana Numbers in C++?

Narayana values form a mathematical sequence utilized across various mathematical areas, named after the Indian mathematician Narayana Pandit. They represent specific configurations like parenthetical arrangements, non-crossing partitions, or lattice paths through the formula N(n,k) = (1/n)( n k )( n k-1 ). When all N(n,k) values are summed for a given n, the result is the n-th Catalan number, closely linked to Catalan numbers. In C++, Narayana numbers can be computed using factorial-based approaches to determine binomial coefficients. These numbers are of interest for investigating solutions in scenarios involving structural constraints, given their relevance in combinatorics, graph theory, and computer science.

Formulae:

N(n, k)= (1/n)(n k)(n k-1 )

Where ( n k ) represents the binomial coefficient, n denotes the total count of steps, and k is associated with a specific combinatorial characteristic (such as the peaks in a lattice path).

Properties:

Several characteristics of Narayana Numbers in C++ include:

• ✅ Catalan Connection: When considering a specific value n, the n-th Catalan number is the total of all Narayana numbers.
• ✅ Applications: These numbers are commonly found in combinatorics, particularly in scenarios like tallying distinct lattice path divisions without intersections and particular parenthetical setups.

Algorithm: Compute Narayana Number N(n,k)

Two whole numbers n (representing the total number of steps) and k (indicating a particular property value).

Output: The Narayana number N(n,k).

Steps:

1. Verify the validity: Return 0 as the outcome if k = 0 or k > n, as these are invalid situations.
2. Calculate the binomial Coefficient:

Compute the ( n k ) using:

Alternatively, use an iterative approach:

Initialize result=1.

For every iteration from i=0 to k-1:

1. Calculate the value of the second binomial coefficient:

Calculate the value of \( \binom{n}{k-1} \).

Apply the following mathematical formulas:

Display the outcome:

Return the computed value of N(n,k).

Pseudo code:

Initialize and Validate Input:

If n=0 or k=0 or k>n, return 0.

Define Helper Function for Binomial Coefficient:

Function binomialCoefficient(n, r):

1. r>n−r, set r=n−r (use symmetry).
2. Initialize result=1.
3. For i=0 to r−1:

result=result×(n−i)/(i+1)

1. Return result.

Calculate First Binomial Coefficient:

binom1=binomialCoefficient(n,k).

Calculate Second Binomial Coefficient:

binom2=binomialCoefficient(n,k−1).

Compute Narayana Number:

narayana=(binom1×binom2)/n.

Return the Result:

Output: narayana.

Example 1:

Let's consider an example to demonstrate the Narayana Number in C++.

#include <iostream>
using namespace std;
//This function computes the binomial coefficient C(n, k). 
unsigned long long binomialCoefficient(int n, int k) {
    unsigned long long result = 1;
    if (k > n - k) k = n - k; // Take advantage of symmetry
    for (int i = 0; i < k; ++i) {
        result *= (n - i);
        result /= (i + 1);
    }
    return result;
}

// Function to calculate Narayana number N(n, k)
unsigned long long narayanaNumber(int n, int k) {
    if (n == 0 || k == 0 || k > n) return 0;
    return binomialCoefficient(n, k) * binomialCoefficient(n, k - 1) / n;
}

int main() {
    int n, k;
    cout << "Enter n and k: ";
    cin >> n >> k;

    unsigned long long result = narayanaNumber(n, k);
    if (result == 0)
        cout << "Invalid input or no valid paths for N(" << n << ", " << k << ")." << endl;
    else
        cout << "Narayana Number N(" << n << ", " << k << ") = " << result << endl;

    return 0;
}

Output:

Enter n and k: 4  2
Narayana Number N(4, 2) = 6
Enter n and k: 6 3
Narayana Number N(6, 3) = 20
Enter n and k: 5 6
Invalid input or no valid paths for N(5, 6).

Explanation:

• ✅ Iterative Binomial Coefficient: By calculating binomial coefficients without factorials or recursion, this implementation prevents overflow for big values.
• ✅ Resolving Errors: It includes simple checks for incorrect inputs in cases where k = 0 or k > n.
• ✅ Easy to Read and Effective: It simplified reasoning that guarantees improved performance and numerical stability for bigger values of n and k.

Example 2:

Let's consider another instance to demonstrate the Narayana Number concept in the C++ programming language.

#include <iostream>
#include <vector>
using namespace std;

// Function to calculate Narayana number using dynamic programming
unsigned long long narayanaNumber(int n, int k) {
    if (n == 0 || k == 0 || k > n) return 0;

    // Create a DP table for binomial coefficients
    vector<vector<unsigned long long>> binomial(n + 1, vector<unsigned long long>(k + 1, 0));

    // Calculate binomial coefficients using Pascal's triangle
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= min(i, k); ++j) {
            if (j == 0 || j == i)
                binomial[i][j] = 1;
            else
                binomial[i][j] = binomial[i - 1][j - 1] + binomial[i - 1][j];
        }
    }

    // Compute Narayana number
    return binomial[n][k] * binomial[n][k - 1] / n;
}

int main() {
    int n, k;
    cout << "Enter n and k: ";
    cin >> n >> k;

    unsigned long long result = narayanaNumber(n, k);
    if (result == 0)
        cout << "Invalid input or no valid paths for N(" << n << ", " << k << ")." << endl;
    else
        cout << "Narayana Number N(" << n << ", " << k << ") = " << result << endl;

    return 0;
}

Output:

Enter n and k: 8 4
Narayana Number N(8, 4) = 490

Conclusion:

In conclusion, the Narayana number is a fascinating combinatorial concept with significant mathematical and practical implications. It is based on combinatorial principles and counts specific configurations such parenthetical arrangements, non-crossing divisions, and lattice paths. Narayana numbers, which are closely connected to Catalan numbers, offer a deeper comprehension of structural patterns and groupings. Their computation, which makes use of binomial coefficients, produces an advanced formula for solving combinatorial problems efficiently. Implementing the computation in C++ or any other programming language improves basic programming and mathematical skills because it requires logical reasoning and algorithmic correctness. This concept shows how elegantly mathematics may be applied to resolve theoretical and real-world problems.