Basically, I want to write a function to compute the following sum

$f(m,L):=\sum_{0\leq k_1,\cdots, k_n\leq m} \binom{m}{k_1,k_2,\cdots k_n}$ and $\mathrm{supp}(k)=L \subseteq \left \{ 1,...,n \right \}$

I wrote the following function but it doesn't work:

L = {1, 2, 4, 5};
f[m, L] := Return[For[i = 1, i <= m, i++, Total[Multinomial@@Take[L, i]]]];
f[3, L]
(*f[3, {1, 2, 4, 5}]*)

What am I missing? Thank you

EDIT: I added a condition to the indices $k$, which I forgot to mention earlier. $\mathrm{supp}(k)=L$ means that $L$ is the set of indices such that the components of the vector $k=(k_1,...,k_n)$ are nonzero.

  • 1
    $\begingroup$ Define functions like f[m_, bigL_] for a start. $\endgroup$ Feb 14, 2013 at 20:48
  • 4
    $\begingroup$ Take a look at Defining functions in the docs. $\endgroup$
    – Szabolcs
    Feb 14, 2013 at 20:49
  • 1
    $\begingroup$ It's rude to delete a question I just took the time to answer. Do you find no value in what I wrote? (I undeleted this to comment but if you insist I will delete it again.) $\endgroup$
    – Mr.Wizard
    Feb 14, 2013 at 21:19
  • $\begingroup$ I'm so sorry I didnt saw that you wrote an answer! I wouldnt have deleted the question. I figured out the same solution as you posted myself. Anyway I'll keep the question! I apologize once more! $\endgroup$
    – rainer
    Feb 14, 2013 at 21:30
  • $\begingroup$ Okay, no problem. I'm glad you found your solution. Please consider the bulleted points in my answer as well because they can save you a lot of of future frustration and/or wasted effort. All but the use of Total are common beginner problems. As for Total I'm not sure what you intended but either you don't understand what the Total function does or you placed it without thinking. If you want a function that will add up any values that are given to it and then return that total when requested I can show you how. $\endgroup$
    – Mr.Wizard
    Feb 14, 2013 at 21:35

3 Answers 3


The sum is a little strange, because the multinomial coefficient makes sense only when $k_1+k_2+\ldots+k_n=m$. I will assume this restriction is (implicitly) intended and that $n$ is fixed. (If not, a variation of the following solution will work.)

Notice that the set

$$\{0 \le k_1 \le k_2 \le \ldots \le k_n \le m\}$$

is in one-to-one correspondence with the $n$ differences

$$(k_1, k_2-k_1, \ldots, k_n - k_{n-1}, m-k_n).$$

The elements of the latter are non-negative integers summing to $m$. If we add $1$ to each, they will be positive and sum (obviously) to $m+n$. The set of such sequences is obtained with IntegerPartitions.

Working backwards, then, we can invoke IntegerPartitions, subtract $1$ from all elements, apply Multinomial, and Sum what we have obtained. This leads to the efficient and straightforward solution:

f[m_Integer, n_Integer] := 
   Sum[Multinomial @@ k, {k, # - ConstantArray[1, n] & /@ IntegerPartitions[m + n, {n}]}]

(Including {n} as an argument to IntegerPartitions causes the number of $k_i$ to be fixed at $n$.)

For example, f[5,4] adds up all such multinomial coefficients having $n=4$ terms summing to $m=5$:

$$\eqalign{ &\sum_{0 \le k_1\le k_2\le k_3\le k_4 \le 5}\binom{5}{k_1\ k_2\ k_3\ k_4} \\ &= \binom{5}{0\ 0\ 0\ 5} + \binom{5}{0\ 0\ 1\ 4} + \binom{5}{0\ 0\ 2\ 3}+ \binom{5}{0\ 1\ 1\ 3}+ \binom{5}{0\ 1\ 2\ 2}+ \binom{5}{1\ 1\ 1\ 2} \\ &= 1 + 5 + 10 + 20 + 30 + 60 \\ & = 126. }$$


I have speculated (in comments below) that the role of L might be to limit the possible values of the $k_i$ to a set. Specifically, this interpretation asks for the calculation of

$$\sum_{k_i \in L: 0\le k_1\le \ldots \le k_n \le m} \binom{m}{k_1\ k_2\ \ldots\ k_n}$$

where $m$, $n$, and $L$ are given. When $m$ is not too large, a simple way is to modify the preceding solution to include only those index vectors $(k_i)$ whose components lie in $L$:

f[m_Integer, n_Integer, support_List] := 
 With[{indexes = 
    Select[# - ConstantArray[1, n] & /@ IntegerPartitions[m + n, {n}], 
      Complement[#, support] == {} &]}, 
  Reap[Sum[Multinomial @@ Sow[k], {k, indexes}]]]

The inclusion of Sow and Reap (which can readily be removed after testing is complete) provides a method to monitor the calculation: each set of indexes is saved by Sow and all are returned via Reap after the calculation is complete.


f[5, 4, Range[0, 5]] (* Reproduce the preceding example *)


It obtains the same answer of $126$, followed by the detailed list of indexes contributing to that value.

f[8, 4, {1, 2, 4, 5}]


The indexes clearly are limited to the set $\{1,2,4,5\}$ in this calculation. Without that limitation, we would invoke f[8, 4, Range[0,8]], obtaining $8143$ instead of $3696$; $15$ different index vectors contribute to this sum.

  • $\begingroup$ thank you, I also do need a variation of that. Do you have an idea how to get only that coefficients where $k_i$ is not 0. In your example above it would be just the last term $\binom{5}{1\ 1\ 1\ 2}$? $\endgroup$
    – rainer
    Feb 15, 2013 at 11:40
  • $\begingroup$ It's even simpler: $(1\ 1\ 1\ 2)$ is the output of IntegerPartitions[5, {4}]. In other words, there's no need to add n to m and afterwards subtract $1$ from each member of the partition. An expression like Total[Multinomial @@@ IntegerPartitions[m, {n}]]] should work fine. $\endgroup$
    – whuber
    Feb 15, 2013 at 15:53
  • $\begingroup$ Thank you. But it's actually more complicated. I'm still not 100% sure if i got how one calculates the sum. I updated my question. I think it means that if $L=(1,2,4,5)$ that the third element can be zero. I'm sorry I haven't seen such a notation. $\endgroup$
    – rainer
    Feb 15, 2013 at 16:44
  • $\begingroup$ Your modification to the question does not make sense because it is now internally contradictory or ambiguous. If, for example, "the third element can be zero," that doesn't add any restrictions to the $k_i$. If it means the third element must be zero, then obviously the first two elements must be zero as well, so you might as well just forget about them and reduce $n$ by $3$ and use the existing solution. It sounds to me like you need to return to your references and research exactly what your problem is so that you can communicate it adequately. $\endgroup$
    – whuber
    Feb 15, 2013 at 17:10
  • $\begingroup$ I does not make sense to me either, until now I haven't seen such an expression. These sum is an input into another function. I wrote down exactly how it is formulated in the paper. I'm sorry $\endgroup$
    – rainer
    Feb 15, 2013 at 17:21

You seem to be writing a tortured definition.

  • As already commented you need Pattern in the left-hand-side of the definition.
  • There are better tools than For in nearly all cases.
  • Return is misapplied and unnecessary.
  • As far as I can tell Total is dropped into the middle of things with no particular consideration.

You probably want something like this:

L = {1, 2, 4, 5};

f[m_, L_] := Sum[Multinomial @@ Take[L, i], {i, m}]

f[3, L]

(This was supposed to be a comment, but it got too long.)

whuber's solution is nice, but I believe it can be compacted quite a fair bit:

g[n_Integer, m_Integer] := Sum[Multinomial @@ PadRight[ip, m],
                               {ip, IntegerPartitions[n, m]}]

As he notes in his answer, you can restrict the summation to nonnegative m-partitions of n. However, since IntegerPartitions[] returns only positive partitions, the way to go about it is to allow $1,2,\dots m$ partitions, and use PadRight[] to tack on the needed zeroes before applying Multinomial[] and summing.

In trying to write a version where the partitions are restricted, I seem to be unable to reproduce whuber's results:

Select[IntegerPartitions[8, 4], VectorQ[#, MatchQ[#, 1 | 2 | 4 | 5] &] &]
   {{5, 2, 1}, {5, 1, 1, 1}, {4, 4}, {4, 2, 2}, {4, 2, 1, 1}, {2, 2, 2, 2}}

where it would seem that all of these partitions satisfy the constraint that the components lie in the set {1, 2, 4, 5}, but only a few of these are counted in whuber's solution.

In any event, here's how to write a restricted partition version:

g[n_Integer, m_Integer, idx : {__Integer}] := 
  Sum[Multinomial @@ PadRight[ip, m],
      {ip, Select[IntegerPartitions[n, m],
                  VectorQ[#, MatchQ[#, Alternatives @@ idx] &] &]}]


g[8, 4, {1, 2, 4, 5}]

Total[Multinomial @@ PadRight[#, 4] & /@
      {{5, 2, 1}, {5, 1, 1, 1}, {4, 4}, {4, 2, 2}, {4, 2, 1, 1}, {2, 2, 2, 2}}]

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.