# 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}]]


@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. –  Szabolcs Mar 8 '14 at 0:48
<< DiscreteMathCombinatorica;