5

How can I get a closed form for the sum of all products of $k$ distinct members of the set $\{1, 2, 3, \cdots, n\}$? I can see that for $k = 2$, the answer is $$\sum\limits_{i = 1}^{n-1}\sum\limits_{j = i+1}^nij$$ and this can be solved for an explicit formula. Is there a way to get this for arbitrary $k$?

b_pcakes
  • 1,501
  • 2
    It's the coefficient of the $(n-k)$'th degree term of $(x+1)(x+2)\cdots(x+n)$, but I don't think that helps much. – Arthur Sep 30 '16 at 19:30
  • 5
    There's an answer here. I'm flagging the question as a duplicate, but I predict that I'm wrong, and will have to apologise - it's been one of those days! (This comment will shortly self-destruct ... as indeed will I, at this rate.) – Calum Gilhooley Sep 30 '16 at 19:46
  • @Arthur: actually that proves the answer is given by a Stirling number of the first kind. – Jack D'Aurizio Sep 30 '16 at 20:30
  • @JackD'Aurizio While it does help in looking up references, it does not help the concrete calculation. That problem remained unchanged after my comment. That's what I meant. – Arthur Sep 30 '16 at 20:44
  • But a lookup at Wikipedia (https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind) does. Stirling numbers can be computed in a efficient way since they fulfill a great number of combinatorial identities. – Jack D'Aurizio Sep 30 '16 at 20:46
  • @Arthur In fact, your comment is in fact how I even arrived at this question in the first place, as I was trying to figure out what the $(n-k)$th degree term is. – b_pcakes Sep 30 '16 at 22:56

0 Answers0