Possible multiplications of k distinct factors with largest possible factor n

Question

Let M(n,k) be the sum of all possible multiplications of k distinct factors with largest possible factor n, where order is irrelevant.

For example, M(5,3) = 225 , because:

• 1*2*3 = 6
• 1*2*4 = 8
• 1*2*5 = 10
• 1*3*4 = 12
• 1*3*5 = 15
• 1*4*5 = 20
• 2*3*4 = 24
• 2*3*5 = 30
• 2*4*5 = 40
• 3*4*5 = 60

6+8+10+12+15+20+24+30+40+60 = 225.

One can easily notice that there are C(n,k) such multiplications, corresponding to the number of ways one can pick k objects out of n possible objects. In the example above, C(5,3) = 10 and there really are 10 such multiplications, stated above.

The question can also be visualized as possible n-sized sets containing exactly k 0's, where each cell that does not contain 0 inside it, has the value of its index+1 inside it. For example, one possible such set is {0,2,3,0,5}. From here on, one needs to multiply the values in the set that are different than 0.

My approach is a recursive algorithm. Similiarly to the above definition of M(n,k), I define M(n,j,k) to be the sum of all possible multiplications of exactly k distinct factors with largest possible factor n, AND SMALLEST possible factor j. Hence, my approach would yield the desired value if ran on M(n,1,k). So I start my recursion on M(n,1,k), with the following code, written in Java:

public static long M (long n, long j, long k)
{
    if (k==1)
        return usefulFunctions.sum(j, n);
    for (long i=j;i<=n-k+1+1;i++)
        return i*M(n,i+1,k-1);
}

Explanation to the code:

Starting with, for example, n=5 , j=1, k=3, the algorithm will continue to run as long as we need more factors, (k>=1), and it is made sure to run only distinct factors thanks to the for loop, which increases the minimal possible value j as more factors are added. The loop runs and decreases the number of needed factors as they are 'added', which is achieved through applying M(n,j+1,k-1). The j+1 assures that the factors will be distinct because the minimal value of the factor increases, and k-1 symbolizes that we need 1 less factor to add.

The function 'sum(j,n)' returns the value of the sum of all numbers starting from j untill n, so sum(1,10)=55. This is done with a proper, elegant and simple mathematical formula, with no loops: sum(j,n) = (n+1)*n/2 - (i-1)*i/2

public static long sum (long i, long n)
{
    final long s1 = n * (n + 1) / 2;
    final long s2 = i * (i - 1) / 2;
    return s1 - s2 ;
}

The reason to apply this sum when k=1, I will explain with an example: Say we have started with 1*2. Now we need a third factor, which can be either of 3,4,5. Because all multiplications: 1*2*3, 1*2*4, 1*2*5 are valid, we can return 1*2*(3+4+5) = 1*2*sum(3,5) = 24.

Similiar logic explains the coefficient "i" next to the M(n,j+1,k-1). say we have now the sole factor 2. Hence we need 2 more factors, so we multiply 2 by the next itterations, which should result in: 2*(3*sum(4,5) + 4*sum(5,5))

However, for a reason I can't explain yet, the code doesn't work. It returns wrong values and also has "return" issues that cause the function not to return anything, don't know why.

This is the reason i'm posting this question here, in hope someone will aid me. Either by fixing this code or sharing a code of his own. Explaining where I'm going wrong will be most appreciable.

Thanks a lot in advance, and sorry for this very long question, Matan.

-----------------------EDIT------------------------

Below is my fixed code, which solves this question. Posting it incase one should ever need it :) Have fun !

public static long  M(long n, long j, long k)
{
    if (k == 0)
        return 0;
    if (k == 1)
        return sum(j,n);
    else 
    {
        long summation = 0;
        for (long i=j; i<=n; i++)
            summation += i*M(n, i+1, k-1);
        return summation;
    }
}

Answer 1

I see that u got ur answer and i really like ur algorithm but i cant control myself posting a better algorithm . here is the idea

M(n,k) = coefficient of x^k in (1+x)(1+2*x)(1+3*x)...(1+n*x)

u can solve above expression by divide and conquer algorithm Click Here to find how to multiply above expression and get polynomial function in the form of ax^n + bx^(n-1)....+c

overall algorithm time complexity is O(n * log^2 n)

and best part of above algorithm is

in the attempt of finding solution for M(n,k) , u will find solution for M(n,x) where 1<=x<=n

i hope it will be useful to know :)

Answer 2

I am not sure about your algorithm, but you certainly messed up with your sum function. The problem you have is connected to type casting and division of integer numbers. Try something like this:

public static long sum (long i, long n)
{
    final long s1 = n * (n + 1) / 2;
    final long s2 = (i * i - i) / 2;
    return s1 - s2 ;
}