list manipulation - Sum of Multinomial Coefficients

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

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.