java - Possible multiplications of k distinct factors with largest possible factor n -

let m(n,k) sum of possible multiplications of k distinct factors largest possible factor n, order 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 notice there c(n,k) such multiplications, corresponding number of ways 1 can pick k objects out of n possible objects. in example above, c(5,3) = 10 , there 10 such multiplications, stated above.

the question can visualized possible n-sized sets containing k 0's, each cell not contain 0 inside it, has value of index+1 inside it. example, 1 possible such set {0,2,3,0,5}. here on, 1 needs multiply values in set different 0.

my approach recursive algorithm. similiarly above definition of m(n,k), define m(n,j,k) sum of possible multiplications of k distinct factors largest possible factor n, and smallest possible factor j. hence, approach yield desired value if ran on m(n,1,k). start recursion on m(n,1,k), following code, written in java:

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

explanation code:

starting with, example, n=5 , j=1, k=3, algorithm continue run long need more factors, (k>=1), , made sure run distinct factors loop, increases minimal possible value j more factors added. loop runs , decreases number of needed factors 'added', achieved through applying m(n,j+1,k-1). j+1 assures factors distinct because minimal value of factor increases, , k-1 symbolizes need 1 less factor add.

the function 'sum(j,n)' returns value of sum of numbers starting j untill n, sum(1,10)=55. done proper, elegant , simple mathematical formula, 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 - 1) / 2;     return s1 - s2 ; } 

the reason apply sum when k=1, explain example: have started 1*2. need third factor, can either of 3,4,5. because multiplications: 1*2*3, 1*2*4, 1*2*5 valid, can return 1*2*(3+4+5) = 1*2*sum(3,5) = 24.

similiar logic explains coefficient "i" next m(n,j+1,k-1). have sole factor 2. hence need 2 more factors, multiply 2 next itterations, should result in: 2*(3*sum(4,5) + 4*sum(5,5))

however, reason can't explain yet, code doesn't work. returns wrong values , has "return" issues cause function not return anything, don't know why.

this reason i'm posting question here, in hope aid me. either fixing code or sharing code of own. explaining i'm going wrong appreciable.

thanks lot in advance, , sorry long question, matan.

-----------------------edit------------------------ 

below fixed code, solves question. posting incase 1 should ever need :) 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;         (long i=j; i<=n; i++)             summation += i*m(n, i+1, k-1);         return summation;     } } 

i see u got ur answer , ur algorithm cant control myself posting better algorithm . here 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 divide , conquer algorithm click here find how multiply above expression , polynomial function in form of ax^n + bx^(n-1)....+c

overall algorithm time complexity o(n * log^2 n)

and best part of above algorithm

in attempt of finding solution m(n,k) , u find solution m(n,x) 1<=x<=n

i hope useful know :)