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?

  • $\begingroup$ 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/… $\endgroup$
    – jVincent
    Commented Mar 1, 2013 at 8:43
  • $\begingroup$ @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. $\endgroup$
    – rainer
    Commented Mar 2, 2013 at 9:29
  • $\begingroup$ There was a syntax change in the length test. You should be able to run it now. $\endgroup$
    – jVincent
    Commented Mar 4, 2013 at 8:48
  • $\begingroup$ 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? $\endgroup$
    – rainer
    Commented Mar 5, 2013 at 8:06
  • $\begingroup$ 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]. $\endgroup$
    – jVincent
    Commented Mar 5, 2013 at 9:12

1 Answer 1


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}  *)
  • $\begingroup$ Nice work! (But you don't need me to tell you that, do you.) $\endgroup$
    – Mr.Wizard
    Commented Mar 1, 2013 at 10:40
  • $\begingroup$ Good point @Mr.Wizard. Oh, and congratulations on passing 50k! $\endgroup$ Commented Mar 1, 2013 at 20:14
  • $\begingroup$ Thank you. Truly nice performance improvement! For the code to work for large n, I think I need to think about an iterative approach $\endgroup$
    – rainer
    Commented Mar 2, 2013 at 9:31

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.