# Sum over multiple indices

I would like to be able to enter the following left hand side of an identity. I can write the right hand side (i think) but am not sure about the left. The Left hand side is

$$\sum_{i_1+i_2+...+i_n=k}\binom{k}{i_1,i_2,...,i_n}\frac{f(i_1)f(i_2)...f(i_n)}{k!}$$

where is a function that extracts coefficients from a previously defined generating function. How do you implement this summation with a sum of multiple indicies equal to a particular $k$?

My particular $\,f$ are called Hypergeometric Bernoulli Numbers. The code I have to generate the numbers is below:

 T[m_, x_] = Sum[x^j/j!, {j, 0, m}];
g[m_, x_] = x^m/(m! (E^x - T[m - 1, x]));


The hypergeometric bernoulli numbers are extracted using the following

 b[m_, n_, M_] := b[m, n, M] = Coefficient[n! Normal[Series[g[m, x], {x, 0, M}]], x, n];


Now I want to sum over the $n$ term defined in the bernoulli number, so I basically want the $\,f$ I wrote in the formula to be replaced by b[m,i[j],M].

• I have merged your follow-up question with this one; and have also incorporated changes suggested by @BobHanlon . Dec 27 '14 at 15:57

I'm not entirely sure what Eleven-eleven is asking, but I think I can write a function that gives his type-set expression (requiring two input variables n and k).

The first step is to do the math problem. How do you write the sum in a computer-friendly way? Like this: $$\sum_{i_1+i_2+\ldots +i_n = k} = \sum_{i_1=0}^k \sum_{i_2=0}^{k-i_1} \cdots\sum_{i_{n-1}=0}^{k-i_1-i_2\ldots-i_{n-2}}\,,$$ and $i_n = k - i_1 - i_2 -\ldots i_{n-1}$ is fixed.

Now proceed with the sum.

elevenEleven[n_, k_, m_, M_] :=
Module[{i},
With[{sumIt =
Sequence @@ Table[{i[a], 0, k - Sum[i[b], {b, 1, a - 1}]}, {a, 1, n - 1}]},
i[n] = k - Sum[i[e], {e, 1, n - 1}];
Sum[Multinomial @@ Table[i[c], {c, 1, n}] * Product[b[m,i[d],M], {d, 1, n}]/k!,
sumIt]
]
]


Here sumItwill basically generate the iterators for the multi-dimensional Sum in the main body. The statement i[n] = k - Sum[i[e], {e, 1, n - 1}] appearing in the main body enforces $i_n = k - i_1 - i_2 -\ldots i_{n-1}$.

Let's test it for $n=4$, $k=2$, $m=4$ and $M=5$:

elevenEleven[3, 2, 4, 5]


7/50

• I'm not entirely sure that belasarius is what I need. Dec 21 '14 at 23:53
• @Eleven-Eleven I finished my answer. Please check if the result is correct. Dec 21 '14 at 23:57
• @Eleven-Eleven I fixed a typo in my answer: 1/n! to 1/k!. Dec 22 '14 at 0:05
• I have replaced with what I needed and It seems that my sum is always 0 Dec 22 '14 at 1:41
• @Eleven-Eleven I have edited my answer: please review. Dec 27 '14 at 16:01

Interesting problem. Following is cleaner IMO, and quite a bit faster on larger cases than accepted ans. (e.g. over 1000X faster on {n, k, m, M} = {7, 20, 5, 6}, ~5000X faster on {n, k, m, M} = {8, 21, 6, 7}) :

Module[{f, jp, n = #1, k = #2, m = #3, M = #4},
jp = IntegerPartitions[k, {n}, Range[0, k]];
f[x_] := f[x] = b[m, x, M];
Tr[Multinomial @@@ (Tally /@ jp)[[All, All, 2]]*Multinomial @@@ jp*
Times @@@ Map[f, jp, {2}]]/(k!)] &[n, k, m, M]

• Nicely done! Alternatively, one could have used FrobeniusSolve[] to generate the indices… Aug 14 '15 at 2:19
• @J. M.: Thanks, coming from you means extra. I find using IntegerPartitions with specified domain faster than FrobeniusSolve for these kind of weak composition problems, In any case, had the "DOH!" moment at dinner, see update that is vastly more efficient...
– ciao
Aug 14 '15 at 5:45
• I see what you mean; not using Permutations[] helps quite a bit. :) Aug 14 '15 at 5:54

If the indices run from zero:

n = 4; k = 3;
idxs = Join @@ (Permutations /@ (PadRight[#, n] & /@  IntegerPartitions[k]));
Sum[whatever[i], {i, idxs}]
whatever[s_List] := ( Multinomial @@ s) Times @@ ( f /@ s) / k!

(*

4 f f^3 + 6 f^2 f f + 2/3 f^3 f

*)


If you want to sum up k from 0 to n:

ClearAll["Global*"]
n = 4;
idxs[n_, k_] := Join @@ (Permutations /@ (PadRight[#, n] & /@ IntegerPartitions[k]));
whatever[s_List, k_] := ( Multinomial @@ s) Times @@ ( f /@ s)/k!
Sum[whatever[i, k], {k, 0, n}, {i, idxs[n, k]}]

(*

f^4 + 4 f^3 f + 6 f^2 f^2 + 4 f f^3 + f^4 +
2 f^3 f + 6 f^2 f f + 6 f f^2 f +
3/2 f^2 f^2 + 2/3 f^3 f + 2 f^2 f f +
1/6 f^3 f
*)
`
• The indices would run from 0. But i'm a little confused about how to implement this with the multinomial coefficient and the function f... Dec 21 '14 at 23:52
• @Eleven-Eleven Give me a few minutes Dec 21 '14 at 23:53
• Okay thanks @belisarius! Dec 21 '14 at 23:55
• @belisarius is there not a $1/k!$ missing? Dec 21 '14 at 23:58
• @QuantumDot yup, editing, thanks Dec 21 '14 at 23:59