Magnificent necklace combinatorics problem

Question

We have the following problem:

You have to make a necklace with pearls.
Minimum number of pearls that can be used is 1 and maximum is n.
Each pearl has a magnificence coefficient and the necklace should be such that the pearls are in strict ascending order of their magnificence.
Find the number of necklaces that can be formed with such condition.
Input given is n (no of pearls), lowest magnificence lm and highest magnificence hm.

Example:
n = 1
LM = 8
HM =9

Answer = 2

There can be 2 cases, one necklace with pearl 8 and one with pearl 9.

One solution that I can think of is as follows:

Let ans(n, lm, hm) be the answer for n pearls such that all pearls are in the range lm - hm.

Now, ans(n, lm, hm) = ans(n-1, lm+1, hm) + ans(n-1, lm+2, hm) +ans(n-1, lm+3, hm) + ans(n-1, lm+1, hm) + ... ans(n-1, hm-1, hm)

Because in the first slot, we can either put pearl lm or lm+1 or lm+2 ... till hm-1.

And of course ans(n, lm, hm) would be 0 if n > hm - lm + 1.

My question is that is there a closed-form solution to this problem?

Answer 1

let us take a good example to work with n = 3,LM = 6,HM = 9. from the question we can deduce one thing that we'll have to find the necklace combinations for each n ie n -> 1 to 3 and them add them together. lets do this for n = 1 and n = 2 manually and look for a pattern

I'm going to list out all combinations grouped by their first number

for n = 1

6 : {6}
7 : {7}
8 : {8}
9 : {9}

for n = 2 

6 : {6,6} {6,7} {6,8} {6,9}
7 : {7,7} {7,8} {7,9}
8 : {8,8} {8,9}
9 : {9,9}

did you see it ? for n = 2, 7 only combined with numbers in the previous group which are smaller or equal Than it ie 7,8,9. since the ans of our current state can be generated by the previous state we use dp. here is the dp table for the given example

   6  7  8  9

1  1  1  1  1

2  1  2  3  4

3  1  3  6  10

here the row's represent the necklace length and column's represent unique pearl number. for example dp(2,8) represent the combinations of a necklace of size 2 and having 8 as the last element which is generated by adding dp[2-1][6]...dp[2-1][8]. here is the code

int sol(int n, int lm,int hm){
    
    vector<vector<int>> dp(n,vector<int>(hm-lm+1,1));
    int ans = hm-lm+1 + n-1;

    for(int i=1;i<dp[0].size();i++){
        dp[0][i]+=dp[0][i-1];
    }

    for(int i=1;i<n;i++){
        for(int j=1;j<dp[0].size();j++ ){
            ans += dp[i-1][j];
            dp[i][j] = dp[i-1][j]+dp[i][j-1];
        }
    }

    return ans;
}