3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Define functions like f[m_, bigL_] for a start. $\endgroup$ Commented Feb 14, 2013 at 20:48
  • 4
    $\begingroup$ Take a look at Defining functions in the docs. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented Feb 14, 2013 at 21:35

3 Answers 3

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Feb 15, 2013 at 17:21
5
$\begingroup$

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
Improve this answer
$\endgroup$
2
$\begingroup$

(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
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.