Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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?

share|improve this answer
    
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! –  WillO Mar 8 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. –  Szabolcs Mar 8 at 0:48
<< DiscreteMath`Combinatorica`;  
g[f_,n_,s_]:=Plus@@Apply[f,PadRight[TransposePartition[#],s]&/@Partitions[n,s],1];  

should even work in version 4.0

share|improve this answer
    
@Kuba: Thank you Kuba. I had managed to write something similar to this myself before your answer appeared. But it turns out that the code I posted in the original question, which I was trying to replace because I thought it was slow, actually runs much faster than this or anything like it. –  WillO Mar 9 at 21:15
    
@WillO I've just edited the question :) Credits to Wouter :) –  Kuba Mar 9 at 21:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.