# Summing Over a Variable Number of Indices

I am trying to figure out the best way to include a variable number of indexes of summation in a program.

For example: Suppose I want to define a function $g[n,s]$ that returns the sum $$\sum_{a_1+...+a_s=n}\hbox{Multinomial}[a_1,\ldots, a_s]$$

I can do this with the following code:

vv[n_,s_,0]:=Multinomial @@ Flatten[{Array[p,s],n-Sum[p[k],{k,1,s}]}];

vv[n_,s_,k_]:=Sum[Evaluate[vv[n,s,k-1]],{p[s-k+1],1,n-Sum[p[j],{j,1,s-k-1}]}];

g[n_,s_]:=First[{Clear[p];vv[n,s,s]}]


But this runs very slowly, presumably because it spends a lot of time computing big symbolic expressions. (That is, the value of vv[n,s,k] is a big symbolic expression, not a number, at least as long as $k\neq s$.)

I feel like there must be a more efficient way to do this. If $s$ were fixed I wouldn't have to form the big expression; I'd just keep a running total of the summands as I iterated through their values. But in this case, I don't know in advance how many iterating indices I need, so I've resorted to the above.

Is there some standard and/or obvious trick for handling this?

In case it's relevant for efficiency issues, the function I'm actually interested in is not Multinomial but a function that takes on real numbers as values.

The function g you describe can be implemented in a simple way like this:

g[n_, s_] := Total[Multinomial @@@ IntegerPartitions[n, {s}]]


I'll admit I didn't go through your code. Is the above helpful?

• Szabolcs: I am working with an old version of Mathematica and don't have IntegerPartitions, but your answer led me to discover Compositions, which, together with the @@@ sign, does the trick. Thank you! Mar 8, 2014 at 0:23
• @WillO If you do need integer partitions in an old version, the Combinatorica package includes this functionality as Parititons. Unfortunately it may not be very fast. Mar 8, 2014 at 0:48
<< DiscreteMathCombinatorica;