javaalgorithmcatalan

Number of ways to form a mountain ranges

I am looking at an application of catalan numbers:

Number of ways to form a “mountain ranges” with n upstrokes and n down-strokes that all stay above the original line.

enter image description here

Now given a number n, find the number of mountain ranges.

public int countMountainRanges(int n) {

}

What logic or formula can we use here to get the number of ways for input n.

I tried the formula F(n) = F(n-1) + F(n-2), but it does not work in this case.

Solution

  • F(n) = F(n-1) + F(n-2) is the formula for the nth Fibonacci number. The nth Catalan number, on the other hand, is given by (2n choose n) / (n + 1).

    public static int countMountainRanges(int n) {
    return choose(2 * n , n) / (n + 1);
}
private static int choose(int n, int k){
    int res = 1;
    k = Math.min(k, n - k);
    for (int i = 0; i < k; i++) {
        res = res * (n - i) / (i + 1);
    }
    return res;
}