I am interesting in finding if the sum of the products of all possible tuples of positive integers with replacement is computable without simply iterating through the tuples and computing directly.

It is similar to this question except I am interested in combinations with replacement.

Here is what I mean:

Let n be the highest number allowed. Therefore the set of numbers to be used is (1,2,3,...,n).

Let r be the number of numbers in each tuple.

Repetition is allowed but order does not matter. Therefore there are $ n+r-1 \choose r $ possible tuples.

I am interested in the sum of the product of all possible tuples for a generic n and r. I think it could be written equivalently like so:

$$ \sum_{A\in {n+r-1 \choose r}} \prod_{x \in A} x = \sum_{i_1\leq i_2\leq i_3...\leq i_r\leq n}\prod_{j=1}^ri_j$$

  • $\begingroup$ Similar tricks should work as in the other question. You want the coefficient of $x^r$ in the polynomial $\prod_{i = 1}^n(1 + ix + i^2x^2 + \ldots + i^r x^r)$. You can do fast polynomial multiplication and get the coefficient. $\endgroup$ – Sasho Nikolov Sep 6 '17 at 18:46
  • $\begingroup$ @SashoNikolov thank you!! That's exactly what I was looking for. I'd love to understand why it works. Would you please point me in the direction of a reference that might help me understand? $\endgroup$ – adamwlev Sep 6 '17 at 22:00
  • $\begingroup$ I am not sure of a particular reference. Having some experience with how generating functions are used in combinatorics would help a lot in coming up with and understanding these sorts of tricks, I think. Check these lecture notes, for example ocw.mit.edu/courses/electrical-engineering-and-computer-science/… $\endgroup$ – Sasho Nikolov Sep 7 '17 at 10:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.