2
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – WillO
    Commented Mar 8, 2014 at 0:23
  • $\begingroup$ @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. $\endgroup$
    – Szabolcs
    Commented Mar 8, 2014 at 0:48
1
$\begingroup$ 
<< DiscreteMath`Combinatorica`;  
g[f_,n_,s_]:=Plus@@Apply[f,PadRight[TransposePartition[#],s]&/@Partitions[n,s],1];

should even work in version 4.0

Improve this answer
$\endgroup$
2
  • $\begingroup$ @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. $\endgroup$
    – WillO
    Commented Mar 9, 2014 at 21:15
  • $\begingroup$ @WillO I've just edited the question :) Credits to Wouter :) $\endgroup$
    – Kuba
    Commented Mar 9, 2014 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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