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.

This is a follow-up question from Sum of Multinomial Coefficients

I have thought about the meaning of the formula I mentioned and, with help, I implemented the following code:

supp[vec_] := Module[{support = {}, i},
  Do[If[vec[[i]] != 0, AppendTo[support, i]], {i, 1, Length[vec]}];

calctrafo[n_, func_] := Module[{vecs, trafo = 0, i},
  vecs = Tuples[Range[0, (n - 1)], n];
  vecs = Select[vecs, Total[#] == (n - 1) &];
  Do[trafo += (Multinomial @@ vecs[[i]])*func[supp[vecs[[i]]]], {i, 1, Length[vecs]}];

calctrafo[7, func]

The function supp gives me the support of the lists and func is a arbitrary function. This code works well for me, but I need the code to work for large n, n >= 100. The problem lies in the function Tuples, which crashes for n > 6. Is there a way to make this work for large n?

share|improve this question
As I understand you the problem is that your very large result list from tuples will not fit in memory. If that is the case, you could perhaps use an iterative approach and something like mathematica.stackexchange.com/questions/9554/… –  jVincent Mar 1 '13 at 8:43
@jVincent Thanks for the Link. But do I miss something, because I tried the first code in your answer but that it did not work. –  rainer Mar 2 '13 at 9:29
There was a syntax change in the length test. You should be able to run it now. –  jVincent Mar 4 '13 at 8:48
Thanks! I edited my code and tried to create the tuples "on the fly" but for let's say for Tuples[Range[0,20],19] I loop through all possible Tuples. But there are approx. 19^20 Tuples and mathematica can't handle such a large number. Is there any other way? –  rainer Mar 5 '13 at 8:06
Yes. If you go from the code in that question you could simply do allmyTuples=lazyTuples[Range@20,19]; which will not actually calculate them all yet, then if you call for instance allmyTuples[[21312312841789283727]] it will return only that one tuple, without having calculated all the others. If you want to iteraet over the tuples, the length can be found by calling Length[allmyTuples]. –  jVincent Mar 5 '13 at 9:12
show 6 more comments

1 Answer

Instead of creating a list of all tuples and then selecting those whose total is n-1, you could start with the IntegerPartitions of n-1, pad them to length n with zeroes, and create all the permutations:

getvecs[n_] := Flatten[Permutations[PadRight[#, n]] & /@ IntegerPartitions[n - 1], 1]

I would also suggest using Position for the support function:

supp2[vec_] := Flatten @ Position[Unitize @ vec, 1]

and replacing the Do loop with Dot:

calctrafo2[n_, func_] := With[{vecs = getvecs[n]},
  (Multinomial @@@ vecs).(func[supp2[#]] & /@ vecs)]

This is considerably faster:

Timing[calctrafo[7, Total]]
(*  {4.375, 1987804}  *)

Timing[calctrafo2[7, Total]]
(*  {0.031, 1987804}  *)
share|improve this answer
Nice work! (But you don't need me to tell you that, do you.) –  Mr.Wizard Mar 1 '13 at 10:40
Good point @Mr.Wizard. Oh, and congratulations on passing 50k! –  Simon Woods Mar 1 '13 at 20:14
Thank you, Simon. –  Mr.Wizard Mar 1 '13 at 20:14
Thank you. Truly nice performance improvement! For the code to work for large n, I think I need to think about an iterative approach –  rainer Mar 2 '13 at 9:31
add comment

Your Answer


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.