Count mountain arrays

Question

A mountain array has below features:

• all items in array are different
• size of array is A which is odd
• the items from 1 to A/2 are increasing
• the remaining items to right are decreasing
• the item at position (A/2 +1) is maximum

For given size of array A, and range of numbers from [1, B] inclusive, count how many mountain arrays are possible.

Count all possible distinct mountain arrays for given A and B.

For example:

A = 3, B = 4

possible arrays are: 8

1 3 2
2 3 1
1 4 3
3 4 1
2 4 3
3 4 2
1 4 2
2 4 1

We have 8 possible mountain arrays.

so result is 8.

My idea is to generate all possible arrays of size A using digits 1 to B, and finding if it is mountain array or not. But my approach takes lot of time. What is the correct approach to solve this problem.

This is my code to generate all possible permutaions:

import java.util.ArrayList; import java.util.List;

public class Main {

    public static void kSubsetPermutations(String partial, List<Integer> set, int k) {
        for (int element : set) {
            if (k == 1) {
                System.out.println(partial + element);
            } else {
                List<Integer> copyOfSet = new ArrayList<>(set);
                copyOfSet.remove(Integer.valueOf(element));
                kSubsetPermutations(partial + element, copyOfSet, k - 1);
            }
        }
    }
    public static void solve(int A, int B) {
        List<Integer> list = new ArrayList<>();
        for(int i=1; i<=B; i++) {
            list.add(i);
        }
        kSubsetPermutations("", list, A);
    }
    public static void main(String[] args) {
        solve(3,4);
    }
}

Result can be large so use mod 10^9 while getting the count. So brute force approach is not the right way to solve this.

Answer 1

The number of combinations of B things (the integers 1,2,...,B) taken A at a time is given by the binomial coefficient, whose equation is given by

_BC_A = B!/(A!*(B-A)!)

For each of these combinations of size A (an odd integer) one element is the largest. The number of ways (A-1)/2 of the remaining A-1 elements can be selected to precede the largest element is given by

_A-1C_(A-1)/2

For each of these combinations of (A-1)/2 elements that are to precede the largest value the remaining (A-1)/2 (unselected) elements are to follow the largest element.

For the (A-1)/2 elements that precede the largest value there is but one ordering (smallest to largest) that satisfies the definition of a "mountain array". The same is of course true for the (A-1)/2 elements that follow the largest element, except that ordering is largest to smallest.

The total number of mountain arrays that can be formed is therefore equal to

_BC_A * _A-1C_(A-1)/2

---

Suppose A = 3 and B = 4. The number of mountain arrays is seen to equal

_BC_A * _A-1C_(A-1)/2 = 4!/(3!*1!) * (A-1)!/((A-1/2)!^2) = 4 * 2!/1 = 8