Efficient algorithm to print sum of elements at all possible subsequences of length 2 to n+1

Question

I will start with an example. Suppose we have an array of size 3 with elements a, b and c like: (where a, b and c are some numerical values)

|1 | 2| 3|
|a | b| c|

(Assume index starts from 1 as shown in the example above)

Now all possible increasing sub-sequence of length 2 are:

12 23 13

so the sum of product of elements at those indexes is required, that is, ab+bc+ac

For length 3 we have only one increasing sub-sequence, that is, 123 so abc should be printed.
For length 4 we have no sequence so 0 is printed and the program terminates.

So output for the given array will be:

ab+bc+ac,abc,0

So for example if the elements a, b and c are 1, 2 and 3 respectively then the output should be 11,6,0

Similarly, for an array of size 4 with elements a,b,c,d the output will be:

ab+ac+ad+bc+bd+cd,abc+abd+acd+bcd,abcd,0

and so on...

Now obviously brute force will be too inefficient for large value of array size. I was wondering if there is an efficient algorithm to compute the output for an array of given size?

Edit 1: I tried finding a pattern. For example for an array of size 4:

The first value we need is :(ab+ac+bc)+d(a+b+c)= ab+ac+ad+bc+bd+cd (Take A=ab+ac+bd) then the second value we need is:(abc) +d(A) = abc+abd+acd+bcd(B=abc) then the third value we need is : (0) +d(B) = abcd(Let's take 0 as C) then the fourth value we need is: +d(C) = 0

But it still requires a lot of computation and I can't figure out an efficient way to implement this.

Edit 2: My question is different then this since:

1. I don't need all possible permutations. I need all possible increasing sub-sequences from length 2 to n+1.
2. I also don't need to print all possible such sequences, I just need the value thus obtained (as explained above) and hence I am looking for some maths concept or/and some dynamic programming approach to solve this problem efficiently.
3. Note I am finding the set of all possible such increasing sub-sequences based on the index value and then computing based on the values at those index position as explained above.

Answer 1

As a post that seems to have disappeared pointed out one way is to get a recurrence relation. Let S(n,k) be the sum over increasing subsequences (of 1..n) of length k of the product of the array elements indexed by the sequence. Such a subsequence either ends in n or not; in the first case it's the concatenation of a subsequence of length k-1 of 1..n-1 and {n}; in the second case it's a subsequence of 1..n-1 of length k. Thus:

S(n,k) = S(n-1,k) + A[n] * S(n-1,k-1)

For this always to make sense we need to add:

S(n,0) = 1
S(n,m) = 0 for m>n