Sum of Multinomial Coefficients

Question

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.

Answer 1

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. }$$

---

Edit

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.

Examples

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

$\{126,\{\{\{5,0,0,0\},\{4,1,0,0\},\{3,2,0,0\},\{3,1,1,0\},\{2,2,1,0\},\{2,1,1,1\}\}\}\}$

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}]

$\{3696,\{\{\{5,1,1,1\},\{4,2,1,1\},\{2,2,2,2\}\}\}\}$

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.

Answer 2

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]

109

Answer 3

(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] &] &]}]

Test:

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

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