1

Suppose n=10,r=3,then i want to find the sum of the products of numbers taken 3 at a time from 1 to 10 and all the combinations considered.There will be nCr possible products and i want their sum.

Gaurav Singla
  • 41
  • 1
  • 4
  • 1
    Can you provide an example? "products of numbers taken 3 at a time" is a bit vague. – Scott Hunter Feb 03 '16 at 19:42
  • 1
    This question is more suitable for math.stackexchange.com. Also, you should show some effort to solve the problem yourself; people won't want to help you if it looks like you just want them to give you the answer. – Robert Dodier Feb 03 '16 at 20:04
  • @ScottHunter suppose n=4 and r=2,then I want to find: [1.2+1.3+1.4+1.5+2.3+2.4+2.5+3.4+3.5+4.5] i.e. sum of all product combinations of first 5 natural numbers taken 2 at a time – Gaurav Singla Feb 04 '16 at 05:58
  • @RobertDodier I tried this problem for hours by myself and when I couldn't solve only then I asked it here. – Gaurav Singla Feb 04 '16 at 06:01
  • @RobertDodier I tried this problem for hours by myself and when I couldn't solve only then I asked it here. – Gaurav Singla Feb 04 '16 at 06:07
  • OK. I believe you but it would help others if you put some note in the problem description about what you tried to do. After looking at this a little, it occurs to me to try to find a recurrence on n, that is, some formula like S(n + 1, m) = S(n, m) + (terms involving n and m) -- basically you just need to count up the new terms introduced each time you increase n. If you find a recurrence, you might be able to derive an explicit formula for S(n, m). – Robert Dodier Feb 04 '16 at 06:34
  • Your base case is S(m, m) which is m!. Note that S(m + 1, m) = m! + (m + 1)!/1 + (m + 1)!/2 + ... + (m + 1)!/m = m! times (1 + (m + 1) times (1/1 + 1/2 + ... + 1/m)) which you might simplify further if it matters. You could derive S(m + 2, m) etc, but I don't know if that's useful. – Robert Dodier Feb 04 '16 at 06:35

2 Answers2

2

What you want is the degree 7 coefficient of

(x+1)(x+2)·…·(x+10)

You can compute all coefficients of that polynomial in O(n²) operations by adding one factor after the other.

For the computation of coefficients from roots see How to efficiently find coefficients of a polynomial from its roots?, Efficient calculation of polynomial coefficients from its roots, Find the coefficients of the polynomial given its roots

Lutz Lehmann
  • 25,219
  • 2
  • 22
  • 51
1

A recurrence for S(n, m) where S is the sum you want is: S(n + 1, m) = S(n, m) + (n + 1)*S(n, m - 1), with S(n, 1) = n*(n + 1)/2 and S(m, m) = m!.

The term (n + 1)*S(n, m - 1) comes from the additional terms in the sum which are created by increasing n by 1: these terms are all the ones you get for S(n, m - 1) (i.e. take one fewer term in the product) and append n + 1 to each one.

I don't know how to solve recurrences like that in general. In this case, I would build a table of terms S(n, m) which would look like a triangle. The bottom row would be for S(n, 1) which is n*(n + 1)/2. The diagonal would be S(m, m) which is m!. So you could try to guess a formula which gives general entries in the table and then add them all up.

A Python program to compute S(n, m) for specific values of n and m might look like:

import math
def S(n, m):
  if m == 1:
    return n*(n + 1)/2
  elif n == m:
    return math.factorial(m)
  else:
    return S(n - 1, m) + n*S(n - 1, m - 1)

which requires, I believe, approximately m*n unique calls to S (but there are many duplicates). Of course it's easy to write this in some other language.

For example, S(10, 3) = 18150.

EDIT: revised the estimated number of operations.

Robert Dodier
  • 16,905
  • 2
  • 31
  • 48